First time, huh?
It was that time of the life when I found myself at the business end of an interview “table”.
At the <data structures and algorithms> section, I got the problem to check if a binary tree is a BST. Now, every responsible and down-to-earth engineer would have refreshed the “How to crack the coding interview” book or something similar. Well, obviously, not me!
After some back and forth questioning, the interviewer managed to pull from me the two answers: The one in which we keep track of the min/max values and the 2nd, with inorder parsing. Being hyped by a previous question about python iterators [that, obviously, I didn’t aced] I said: Well, we can write an iterator that parses the tree in inorder so there is no need to keep track of all the nodes!
The interview kept on going for a while, but, now, I wanted to check if one can reaaaly:
- Make a recursive iterator (bc well, tree)
- Use it to check if tree is BST
- Overhead? Too much code?
The search
First step, google the problem, found a lot of sites with the two solutions, but, at least in first 1-2 pages, no iterator solutions for inorder traversal. Static variables (ugh), classes and objects, etc. Even for python code. Hmmm. . .
Next step, primer on iterators and generators! I didn’t quite used them in production. To my surprise, smack down in the Python documentation about generators, Guido’s binary tree example!
Ok, wow! So not only that I can use recursive iterators, Guido himself showed off a tree example.
The code
No more googling, this is my take on the problem:
Lessons learned?
I was again amazed by how powerful the Python language is. All the bookkeeping and recursive mambo-jambo, state keeping between calls, neatly handled! The language that keeps on giving! [Except async, but this is another story]. Oh and let’s not forget about functional programming, which is the actual source of this potent magic.
So, next time will I read the How to crack … book? Probably not. Why? Because I don’t like overfitting! I mean, if both the interviewer and interviewee are using the same fixed sets of problem/answer to train/evaluate, well, 100% accuracy! Hired on the spot! Max out on the offer!
Is this good? For the interviewee, on the short term, yes! On the long term, if their colleagues have been hired with the same “high bar”, it will be a sad company. Who is going to solve the actual issues? I mean how often a binary tree problem surfaces in everyday job?
[TODO: Add story when I needed a binary search to implement a hardware driver]