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 shortest path in a Fibonacci-ordered tree

Q: Find shortest path in a Fibonacci-ordered tree

This question evaluates understanding of recursive binary tree structures, preorder indexing, Fibonacci-like size relations, and arithmetic-based navigation for computing paths in an implicitly defined tree.

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a recursively-defined binary tree **T(order)** whose **shape depends only on `order`** (not on node values). Nodes are labeled **0..N-1** using **preorder traversal** (root, then left subtree, then right subtree), where **N = size(T(order))**. ## Tree definition Let `size(k)` be the number of nodes in `T(k)`. - Base cases: `T(0)` and `T(1)` each consist of a **single node**. - Therefore: `size(0) = 1`, `size(1) = 1`. - Recursive case: for `k >= 2`, `T(k)` has: - a root node, - a **left** subtree `T(k-1)`, - a **right** subtree `T(k-2)`. This implies: - `size(k) = 1 + size(k-1) + size(k-2)` ## Task Given integers: - `order` — which tree `T(order)` to use - `start` — a node label in `T(order)` - `end` — a node label in `T(order)` Return the **shortest path** from `start` to `end` as a sequence of node labels, inclusive (i.e., the unique simple path in the tree). You are **not** given a node/edge structure and should solve the problem using only arithmetic on integers plus `order`. ## Input / Output - **Input:** `order: int`, `start: int`, `end: int` - **Output:** `path: int[]` (labels from `start` to `end`, inclusive) ## Constraints - `0 <= order` - `0 <= start, end < size(order)` - Aim for an algorithm that runs in **O(order)** time and uses **O(order)** extra space. ## Example For `order = 2`: - `size(0)=1, size(1)=1, size(2)=3` - Preorder labels are: root `0`, left child `1`, right child `2` If `start=1, end=2`, the output path is: - `[1, 0, 2]` (Any equivalent representation of the same path is acceptable if the problem statement in an interview clarifies formatting.)

Quick Answer: This question evaluates understanding of recursive binary tree structures, preorder indexing, Fibonacci-like size relations, and arithmetic-based navigation for computing paths in an implicitly defined tree.

You are given an implicit binary tree T(order). T(0) and T(1) each contain a single node. For k >= 2, T(k) consists of a root, a left subtree T(k-1), and a right subtree T(k-2). Nodes are labeled from 0 to size(order)-1 using preorder traversal: root, then the entire left subtree, then the entire right subtree. The sizes satisfy size(0) = 1, size(1) = 1, and size(k) = 1 + size(k-1) + size(k-2). Given order, start, and end, return the unique shortest path from start to end as a list of node labels, without explicitly constructing the tree.

Constraints

0 <= order
size(0) = 1 and size(1) = 1
For k >= 2, size(k) = 1 + size(k-1) + size(k-2)
0 <= start, end < size(order)
Aim for O(order) time and O(order) extra space

Examples

Input: (2, 1, 2)

Expected Output: [1, 0, 2]

Explanation: In T(2), node 1 is the left child and node 2 is the right child of root 0.

Input: (0, 0, 0)

Expected Output: [0]

Explanation: T(0) has exactly one node, so the path starts and ends at 0.

Input: (3, 3, 2)

Expected Output: [3, 1, 2]

Explanation: In T(3), nodes 3 and 2 are both under node 1, so the shortest path goes through 1.

Input: (4, 4, 5)

Expected Output: [4, 2, 1, 5]

Explanation: Both nodes are in the left subtree of T(4); their lowest common ancestor is node 1.

Input: (5, 9, 14)

Expected Output: [9, 7, 1, 0, 10, 14]

Explanation: The nodes lie in different major branches of T(5), so the path passes through the overall root 0.

Input: (4, 0, 8)

Expected Output: [0, 6, 8]

Explanation: Node 8 is in the right subtree of the root in T(4), specifically under node 6.

Input: (4, 7, 7)

Expected Output: [7]

Explanation: When start and end are the same node, the shortest path contains only that label.

Solution

def solution(order, start, end):
    sizes = [1] * max(2, order + 1)
    for k in range(2, order + 1):
        sizes[k] = 1 + sizes[k - 1] + sizes[k - 2]

    def root_path(label):
        base = 0
        k = order
        path = []

        while True:
            path.append(base)
            if label == base:
                return path
            if k < 2:
                raise ValueError("Invalid label for the given order")

            left_size = sizes[k - 1]
            left_root = base + 1
            right_root = base + 1 + left_size

            if left_root <= label < left_root + left_size:
                base = left_root
                k -= 1
            else:
                base = right_root
                k -= 2

    path_start = root_path(start)
    path_end = root_path(end)

    i = 0
    limit = min(len(path_start), len(path_end))
    while i < limit and path_start[i] == path_end[i]:
        i += 1

    return path_start[i - 1:][::-1] + path_end[i:]

Time complexity: O(order). Space complexity: O(order).

Hints

Precompute size(k). In preorder, every subtree occupies one contiguous range of labels.
Find the path from the root to start and to end using only range checks, then combine them through their lowest common ancestor.

Quick Overview

This question evaluates understanding of recursive binary tree structures, preorder indexing, Fibonacci-like size relations, and arithmetic-based navigation for computing paths in an implicitly defined tree.