Software Engineer · Phone Screen · Coding

Databricks — Software Engineer ✅ Passed

Level: Mid-Level

Round: Phone Screen · Type: Coding · Difficulty: 6/10 · Duration: 60 min · Interviewer: Unfriendly

Topics: Binary Tree, Recursion, Tree Traversal

Location: San Francisco Bay Area

Interview date: 2026-02-15

Summary

I had a technical phone screen where I was asked to find the path between two nodes in a Fibonacci tree.

Details

I was asked the following question during the phone screen:

You are given a special family of binary trees called Fibonacci trees. The k?th order Fibonacci tree T(k) is defined recursively:

T(1) is a single node. T(2) is a single node. For k ≥ 3 , T(k) is a tree whose root has: left subtree T(k ? 1) and right subtree T(k ? 2) . Let size(k) be the number of nodes in T(k). You can compute size(k) from the definition above:

size(1) = 1 size(2) = 1 size(k) = 1 + size(k ? 1) + size(k ? 2) for k ≥ 3 Now, imagine we number the nodes of T(k) in preorder (root, then left subtree, then right subtree), using 1?based indices from 1 to size(k).

You are given:

An integer k (the order of the Fibonacci tree), with 1 ≤ k ≤ 60 . Two integers a and b , such that 1 ≤ a, b ≤ size(k) ; these are indices of two nodes in the preorder numbering of T(k) . The tree can be very large for big k, so you must not construct it explicitly in memory.

Task Design and implement a function:

List<Long> pathInFibonacciTree(long k, long a, long b) that returns the sequence of node indices (in preorder numbering) along the simple path from node a to node b in T(k).

The path should start with a and end with b . Indices in the returned list should be the preorder indices in T(k) .