Optiver·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Optiver software engineer interview with a probability and data structures question that had more depth to it than it first appeared. No frills, just math and reasoning under pressure.

Questions Asked (1)

You're given a binary search tree where finding node A takes 1 comparison and finding node D takes 3 comparisons. What's the expected number of comparisons to find a uniformly random node? State your assumptions.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew expected value meant summing (probability * cost) over all nodes, but the catch is you only know the depth of two nodes, not the whole tree.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify that the expected number of comparisons is the average depth of all nodes in the BST, assuming uniform random selection. Then, use the given depths of nodes A and D to infer the tree structure and compute the average depth, stating any assumptions about the tree's shape and node distribution.

Pro tip: Explicitly state your assumptions about the tree's structure and node set, as interviewers value clarity and the ability to reason under uncertainty. Also, mention that in a balanced BST, the expected depth is O(log n), but here the small example suggests a specific small tree.

1. Define expected comparisons

Explain that the expected number of comparisons for a uniformly random node is the sum of depths of all nodes divided by the number of nodes.

2. Infer tree structure from given depths

Use the facts that node A is at depth 1 (1 comparison) and node D is at depth 3 (3 comparisons) to deduce possible tree shapes and the positions of other nodes.

3. List all nodes and their depths

Enumerate the nodes in the tree and assign depths based on the inferred structure, ensuring consistency with the given depths for A and D.

4. Compute average depth

Sum the depths of all nodes and divide by the total number of nodes to get the expected number of comparisons.

5. State assumptions and discuss trade-offs

Clearly state assumptions about the tree (e.g., number of nodes, shape) and discuss how the expected comparisons would change if the tree were balanced or skewed.

Key Points to Mention

Expected comparisons = average depth of nodes under uniform distribution.
Depth of a node equals number of comparisons to find it (root at depth 1).
Given depths: A at depth 1, D at depth 3, so A is likely the root or a child of root, and D is deeper.
Assumptions: number of nodes, tree shape (e.g., complete, balanced, or specific structure), and that all nodes are equally likely.
Calculation: sum of depths / number of nodes.
Trade-off: In a balanced BST, expected depth is O(log n), but in a skewed tree it's O(n).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.