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:
Write a function findInSorted(arr, x). It’s supposed to return the smallest index of a value x in an array arr which, as a precondition, must be sorted from least to greatest. Or, if arr doesn’t contain an element equal to x, the function returns -1.
The 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.
at

2 comments:

  1. UnknownMon Jan 04, 05:55:00 AM PST

    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;
    }

    ReplyDelete
  2. UnknownMon Jan 04, 06:00:00 AM PST

    Ah... I failed too... as coded this will return the largest index when there are dupes. Guess I don't get hired ;)

    ReplyDelete