Depth first failure

Well for all we say “Third time’s a charm” I managed to fumble a depth-first search question on my third coding interview. Unfortunately I’m seeing a pattern here. As with the Facebook interview which first prompted me to do a “gah DFS” post, I began to do a Clojure implementation for my interviewer(s), switched to python in a panic when no solution came to mind and just stalled in general. So here I am ranting about it after the fact and writing both implementations for my own sanity.

The first question I got asked was “how can I determine the index of some value K in a sorted sequence S?”. The answer to which is patently obvious: do a binary search tree traversal. That is we take the sequence, compare the “middle” value to the desired key and based on the relative values of the two (less than, equal, greater than) a case is evaluated which restricts the search domain and repeats the question on a subset of the problem space or you have reached a terminal case and return a value.

Graphically, this means that for a sequence such as [0 1 2 ... 16] if I want to find the value 5 I perform the following sequence of operations and comparisons.

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16], 9 gt. 5
[0 1 2 3 4 5 6 7 8 - -  -  -  -  -  -  - ], 4 lt. 5
[- - - - - 5 6 7 8 - -  -  -  -  -  -  - ], 6 gt. 5
[- - - - - 5 - - - - -  -  -  -  -  -  - ], 5 is the 6th index

The value - simply means that I and consequently my solution program know that the value for which I am searching cannot exist there due to the lemma of a strictly increasing key set. As long as that lemma holds the BST traverse will eventually find the sought value. This “sliding window” approach can be coded in Python as

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bst_address(value, sequence):
    upper, middle, delta, lower = len(sequence), 0, 0, 0
    while(true):
        delta  = upper - lower // 2
        middle = lower + delta
        if(lower >= upper):
            return -1
        elif(sequence[middle] == value):
            return middle
        elif(sequence[middle] > value):
            upper -= delta
        else:
            # implicitly sequence[middle] < value
            upper += delta

which is all well and good and I know now it that I’m out of the interview, but what’s the idiomatic and obvious way that I could get to this quickly so that the interviewer doesn’t have to suggest the key insight I use upper and lower cursors?

Well, I can simply have implemented this as the literal Clojure translation being

1
2
3
4
5
6
7
8
9
10
11
(defn bst_index [col val]
    (loop [left 0
           right (count col)]
        (let [delta  (/ (- right left) 2)
              center (+ left delta)
              cval   (nth col center)]
            (cond
                (<= right left) -1
                (= val cval)    center
                (> val cval)    (recur (+ left delta 1) right)
                (< val cval)    (recur left (- right delta 1))))))

But to be perfectly honest I don’t think that I would have come up with the index-manipulation scheme given any amount of time and the choice that I had made to work in Clojure. Perhaps had I chosen to work in Python or some other more C-like language this solution would have come to mind.