Yesterday I had an interesting phone screen with someone, and the seemingly common practice of asking a candidate to code on the phone - in a shared web-based environment again came up. I recognize that any employer can have any legal criteria for employment, and the "Coding Phonescreen" is a very common one. You get to see if the person can write code in a few minutes as opposed to inviting them for a day-long interview cycle that can cost considerably more. It's decent logic.
But it really doesn't tell the story, does it?
Speed Coding has about the same relationship to real development as a college classroom has to Jeopardy!... yeah, the material is the same, but the skills to be able to do well in one do not necessarily translate to the other. And the most critical skill in the speed forms is pattern recognition of the problem.
If you've seen this problem before, and written a simple solution to it, then you're in good shape. You know the flow, you know the pitfalls, and you can talk your way through it - like you're talking your way through directions to a local restaurant. No pressure, you're showing someone something you know, and it happens to take a few steps. No biggie.
But if you're at all unsure, then you're not going to get time to think about the solution before being expected to answer it. This is the problem with Speed Coding - if you know the answer, it's fine. But then it's not really seeing if you can think on your feet... if you don't know the answer, you're likely going to make one or two edge-case mistakes, and those will be clearly visible to the person that knows the solution.
The problem I ran into was a binary tree issue, and while I had been practicing my Speed Coding in Clojure, the nature of the binary tree really leaned towards a C++ solution, and that was not horrible, but it was a lot less friendly to edge-conditions.
I ended up writing something like this:
struct Node { int value; Node *left; Node *right };
bool stored(Node *me, op) {
bool retval = true;
if (retval && (me->left != NULL) && (me->left op me->value)) {
retval = stored(me->left, op);
}
if (retval && (me->right != NULL) && (me->value op me->right->value)) {
retval = stored(me->right, op);
}
return retval;
}
and the missed edge-case is that once you are one, or more, steps down in the tree, it's possible to have the relative position of the values be correct, but the absolute position to be false. There are two ways to solve this, in this code:
- Pass limits down with the call - this could be done with max and min arguments and then in the recursive calls, place the correct values there, and test them as well.
- Scan up the tree on each check - this could be a walk-up the tree and check to see that you aren't in violation of the location you have. This would take more time because of all the walking, but it'd work.
But what I'd wanted to do was to write it in Clojure, but the data structure didn't jump out at me. Until this morning. 🙂 This morning I spent the minute or two thinking about the data structure, and then formulated the following solution:
;; [val left right]
;; 10
;; 5 15
;; 1 7 12 20
(def good [10 [5 [1] [7]] [15 [12] [20]]])
;; 10
;; 5 15
;; 1 17 12 20 -- the 17 is out of place
(def bad [10 [5 [1] [17]] [15 [12] [20]]])
(defn sorted?
"Function to check a binary tree to see if it's sorted for proper
searching."
[[v lt rt] op]
(let [ltv (first lt)
rtv (first rt)]
(and (or (nil? lt) (and (every? identity (map #(op % v) (flatten lt)))
(check lt op)))
(or (nil? rt) (and (every? identity (map #(op v %) (flatten rt)))
(check rt op))))))
What I really like about this solution is that it checks the entire subtree with the operation. This means that the effort to do one, is really checking all of them. This is what I wanted to write, and it works perfectly.
But I didn't force the issue, and pull back and take the time to think. My mistake. I won't make it again.
UPDATE: a friend and I were talking about this same problem, and he came up with a solution that was very clever - the structure can be validated by simply assuming that the structure is a sorted binary tree, and then calculating the min and max values of the tree.
The catch being that if you get to a node where the current value isn't within the min and max, then you have to fail, and return nil. It's really quite amazingly simple in that it's very fast, very easy to understand and adds the additional benefit of returning the extremum of the tree.
(defn bst-rx*
"returns extent [min max] of valid bst or nil if invalid"
[t]
(cond
(nil? t) nil
(vector? t) (let [[v l r] t
lx (if l (bst-rx* l) [v v])
rx (if r (bst-rx* r) [v v])]
(when (and lx rx (<= (lx 1) v (rx 0)))
[(lx 0) (rx 1)]))
:else [t t]))
(defn bst-rx?
[t]
(boolean (bst-rx* t)))
