I'd ground the recent high-frequency questions down to nothing, and then they hit me with an old, unprepared-for question: find path within Fibonacci tree.
The problem doesn't give you a node structure, and you're not even allowed to write your own.
The input is order: int, start: int, end: int. Find the shortest path from start to end.
Right away I explained a brute force approach, and the interviewer told me to use the tree's properties to come up with an optimal solution... I was confused for a good while because the node values in the example didn't equal left node + right node either... so where exactly is the "Fibonacci" in this? Only after he gave me a hint did I realize it's in the tree size, not the node value.
Basically: each tree's size is left child tree size + right child tree size + 1.
For example: size(T_5) = size(T_4) + size(T_3) + 1 (here 3, 4, 5 are the order).
So... why is this even called a Fibonacci tree? Isn't the size of every binary tree just left size + right size + 1? Change the name!
There's another genuinely key property: each tree is pre-order labeled from 0 to n-1 (n being the size of the tree).
Only after figuring out these two properties was I able to explain the correct approach, O(order) in both time and space, and understand why you don't need the node structure at all — you can just work directly with ints. By this point I'd already spent over 20 minutes.
The idea is roughly: build an array of size O(order) that stores the size of each subtree, then find the path to start and the path to end. Finally, process those two paths.
Writing the code was rocky. I figured recursion usually passes in curr_node, so that's how I wrote it, but he kept saying I didn't need to. I tried to understand his approach instead (as I understood it, you roughly subtract the subtree size from the target on each recursive call)... and after I followed his hint, that was pretty much it — my brain short-circuited after switching approaches, and I ran out of time. I never got working code out. Hard fail.
Afterward I found the exact same problem on Stack Overflow, and the top-voted answer does pass in current node. His hints up to that point had all been helpful, so I didn't dare ignore this last one either — I think he was also trying to help me get it working faster... but honestly I could've just stuck with my own approach. There's more than one correct answer.
Takeaway: when you see a question you haven't prepped for, don't panic! Don't rush! Read the problem carefully! Ask if there's something you don't understand.
Lastly, I want to ask everyone: what do you do when the hint you're given doesn't match your own approach?
Discussion
Loading comments…