How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Find Path Between Fibonacci Tree Nodes | Databricks Coding Question

Find Path Between Fibonacci Tree Nodes

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a special family of binary trees called **Fibonacci trees**. Define the tree `T(k)` recursively: - `T(1)` is a single node. - `T(2)` is a single node. - For `k >= 3`, `T(k)` consists of a root node whose: - left subtree is `T(k - 1)` - right subtree is `T(k - 2)` Let `size(k)` be the number of nodes in `T(k)`: - `size(1) = 1` - `size(2) = 1` - `size(k) = 1 + size(k - 1) + size(k - 2)` for `k >= 3` Now number all nodes of `T(k)` using **preorder traversal** (`root -> left -> right`) with **1-based indices** from `1` to `size(k)`. Given: - an integer `k` where `1 <= k <= 60` - two preorder indices `a` and `b` such that `1 <= a, b <= size(k)` Implement a function: `List<Long> pathInFibonacciTree(long k, long a, long b)` Return the sequence of preorder indices along the unique simple path from node `a` to node `b` in `T(k)`. Requirements: - The returned list must start with `a` and end with `b`. - The tree may be extremely large, so you must **not** construct the full tree explicitly in memory. - Your algorithm should determine the path using only the recursive structure of the Fibonacci tree.

Quick Answer: This question evaluates a candidate's ability to reason about recursive tree structures, map preorder indices to positions in a recursively defined Fibonacci tree, and design space-efficient algorithms for large inputs.

A Fibonacci tree T(k) is defined recursively: T(1) and T(2) each consist of a single node. For k >= 3, T(k) has a root whose left subtree is T(k - 1) and whose right subtree is T(k - 2). Let size(k) be the number of nodes in T(k), so size(1) = 1, size(2) = 1, and size(k) = 1 + size(k - 1) + size(k - 2). The nodes of T(k) are numbered in preorder (root, then left subtree, then right subtree) using 1-based indices from 1 to size(k). Given k and two valid preorder indices a and b, return the sequence of preorder indices along the unique simple path from node a to node b. The path must start with a and end with b. You must not construct the tree explicitly in memory.

Constraints

1 <= k <= 60
1 <= a, b <= size(k), where size(1) = 1, size(2) = 1, and size(i) = 1 + size(i - 1) + size(i - 2)
Do not construct the full tree explicitly; solve using subtree sizes and preorder index ranges

Examples

Input: (1, 1, 1)

Expected Output: [1]

Explanation: T(1) has only one node, so the path from 1 to 1 is just [1].

Input: (3, 2, 3)

Expected Output: [2, 1, 3]

Explanation: In T(3), node 2 is the left child of root 1 and node 3 is the right child, so the path goes through the root.

Input: (5, 5, 6)

Expected Output: [5, 3, 2, 6]

Explanation: In T(5), node 5 lies under node 3, while node 6 is the right child of node 2. Their lowest common ancestor is node 2.

Input: (6, 7, 10)

Expected Output: [7, 3, 2, 8, 10]

Explanation: Both nodes are inside the left subtree of the root. The path climbs from 7 to 2, then descends to 10.

Input: (6, 6, 13)

Expected Output: [6, 4, 3, 2, 1, 11, 12, 13]

Explanation: Node 6 is deep in the left side of T(6), while node 13 is in the right subtree of the root, so the path passes through node 1.

Input: (5, 7, 7)

Expected Output: [7]

Explanation: When a and b are the same node, the path contains only that node.

Hints

For a subtree T(m) whose root has preorder index s, its left subtree occupies indices [s + 1, s + size(m - 1)] and its right subtree starts at s + 1 + size(m - 1).
Find the root-to-a path and the root-to-b path using only subtree ranges, then combine them at their lowest common ancestor.

Quick Overview

This question evaluates a candidate's ability to reason about recursive tree structures, map preorder indices to positions in a recursively defined Fibonacci tree, and design space-efficient algorithms for large inputs.