Write a functionThe great thing is, everyone understands it, and everyone thinks they can easily do it. But the answers I get are always non-working, off-by-1, sub-optimal in asymptotic runtime, inelegant, and/or not so good with edge cases. And that is why we're using it to screen programmer applicants at Quixey.findInSorted(arr, x). It’s supposed to return the smallest index of a valuexin an arrayarrwhich, as a precondition, must be sorted from least to greatest. Or, ifarrdoesn’t contain an element equal tox, the function returns-1.
Wednesday, December 16, 2009
Programmer Interview Question
I have a favorite interview question I always ask programmers on a written test or in person (not so much on the phone). I just posted it on the Quixey blog:
Subscribe to:
Post Comments (Atom)
2 comments:
This is a classic, and even experienced programmers get it wrong. I'm only being careful because I know it's tricky. Of course, that's why there's std::binary_search().
Here's my attempt... hopefully my logic is documented, though naturally this isn't a full proof. I know the asymptotic complexity is right, but one could do better in practice in terms of early outs, small arrays, last iteration, etc.
int findInSorted(T arr, V x)
{
lo=0; hi=arr.length(arr)-1;
// not found if zero elements or x outside end ranges
if (hi<0 || xarr[high])
return -1;
// loop invariant: arr[lo]<=x<=arr[hi]
while (lo!=hi) {
mid = floor((lo+hi)/2);
if (arr[mid] <= x)
lo=mid; // results in arr[lo] <= x
else
hi=mid; // results in x < arr[hi]
}
// lo==hi here, so we've either found it or it's not there
if (arr[lo]==x)
return lo;
else
return -1;
}
Ah... I failed too... as coded this will return the largest index when there are dupes. Guess I don't get hired ;)
Post a Comment