Constrained min/max value of an array
Another puzzle courtesy the Daily Coding Problem email list.
Daily Coding Problem: Problem #1578 [Hard]
This problem was asked by Facebook.
Given an array of numbers of length N,
find both the minimum and maximum using less than 2 * (N - 2) comparisons.
Github repo for my solution.
Development journey
These interview problems often have a catch for length zero or one inputs. This one seems to have that catch:
| N | 2(N - 2) |
|---|---|
| 0 | -4 |
| 1 | -2 |
| 2 | 0 |
| 3 | 2 |
| 4 | 4 |
| 5 | 6 |
What is a program going to do, give back some comparisons for 0-length arrays? For single element arrays, min and max values are just that of the only element, but a program still has to make a comparison of the array length to 1.
For arrays of length 2, zero comparisons doesn’t make sense.
At least 1 comparison has to be done to check if array[0] is less than array[1].
Should the interview candidate point this out?
I’ll assume arrays of more than 2 elements.
The obvious algorithm sets variables minimum and maximum to the smallest number and largest number
representable by whatever type the variables possess,
then plows through all of the array one element at a time comparing variables minimum and
maximum to each element.
That would require 2N comparisons,
one to check if array element is less than current value of minimum
one to check if array element is greater than current value of maximum.
The first change to make to get to the goal is to observe
that you can set minimum and maximum to the value of the first
element of the array instead of smallest and largest representable values.
You can start comparing with the second element of the array.
You’ve avoided 2 comparisons, so exactly 2(N - 1) comparisons.
The second change to make to get to the goal is to observe
that variables min and max always contain values that at least equate.
If some array value compares less than min value,
it won’t compare greater than max value.
The program can skip some comparisons: if an array value is less than min,
the program does not have to compare that array value to max.
The problem is not all arrangements of values in the array cause the skip to happen.
To make less than 2(N-2) comparisons, at least 2 array values have to
compare less than min.
Third change: eliminate 1 comparison by checking 1st and 2nd array
values, and setting min and max appropriately,
then iterating through array values starting with the third element.
The program makes one comparison to set min and max,
but it skips two comparisons, so 2(N - 2) + 1 comparisons total.
Here’s where my ideas ran out, and I googled for an answer. I didn’t figure it out on my own, I guess I would not get a job at Facebook.
I did try one of the less abstruse solutions from a
stackexchange.
My implementation of that algorithm does indeed use 3N/2 - 2
comparisons.
The stackexchange algorithm steps through the array by 2, but uses an index and index+1 values, which usually causes developers to fall prey to a very common off-by-one bug. When the array is an odd length, stepping through the array by 2 leaves one unexamined element at the end of the array. As in most cases, this involves some unavoidable code repetition to examine that final value. Any maintainer will have to figure that out, and make changes in two places.
Interview analysis
This strikes me as a dumb interview question:
it won’t let an interviewer see much of a candidate’s coding style or ability.
There’s a fairly simple flow-of-control for the obvious, 2N comparison program,
and none of the “optimizations” change it much.
The interviewer won’t see much programming.
If the candidate realizes that one comparison gets made every time through a for-loop, the candidate may spend time trying to puzzle out a recursive solution, to avoid the comparisons made in the for-loop test. Candidates might decide they’re spending N (or so) comparisons on the for-loop, then trying to figure out a probably impossible N-comparison method of setting min and max variables.
Some bright spark candidate might think of a way to set min and max with an esoteric combination of bitwise and arithmetic operators, but without an explicit less-than operator. This subverts the interviewer’s ability to judge the candidate’s programming ability.
Beyond that, even the 3N/2-2 comparison solution is still O(N).
Any of these “optimizations” affect run time only very slightly,
and only in some arrangements of array values.
If you’re interested in your developers creating “business logic” as quickly as possible, you really don’t want them to do this kind of “optimization”. If you’re interested in human-readable programs that don’t create cognitive load on the readers, and cause fewer bugs on modification, you don’t want this kind of “optimization”.
This is not a good question for an interview.