Databricks Coding Interview: Fibonacci Tree Paths
Based on a candidate's reported Databricks interview
The interviewer opens
Hi, and thanks for joining. Welcome to your interview for the Senior Engineer role at Databricks. We'll work through one coding problem together, and I'd like you to think out loud as you go. If you need to step out or take a break, the Pause button at the top right will stop the interview.
The problem is about finding a node's path in a recursively defined tree, which is the kind of implicit-structure navigation that shows up in large-scale data systems. It's in the Problem tab now, so please read it through and ask me any questions before you start.
The problem
A Fibonacci tree of order k: order 0 is empty, order 1 is a single node, and order k ≥ 2 is a root with a left subtree of order k-2 and a right subtree of order k-1. Nodes are labeled 0, 1, 2, … in preorder (root, left subtree, right subtree).
order: the tree's orderlabel: a node's label
Return the path from the root to that node as a string of 'L' (left child) and 'R' (right child); the root's path is "".
Example: order = 5, label = 7 → "RLR"
Sizes: 1 ≤ order ≤ 75; the tree has up to about 5.5×10^15 nodes.