Uber·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026

Summary

Uber SWE interview that went deep on tree algorithms, specifically LCA. The whole session felt like a mini lecture on graph theory tradeoffs, which I wasn't fully prepared for.

Questions Asked (1)

Given two nodes in a binary tree, find their lowest common ancestor. Walk through multiple approaches and compare their time and space complexities, then recommend which to use depending on the situation.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with the recursive DFS approach because that's what everyone knows, O(N) time, O(H) space for the call stack.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying assumptions (e.g., whether parent pointers exist, if nodes are guaranteed present) and then present multiple approaches: recursive traversal for a general binary tree, parent-pointer based, and Euler tour + RMQ for frequent queries. Compare their time and space complexities, and recommend the recursive approach for a single query on a general tree, or the Euler tour + RMQ for multiple queries.

Pro tip: Mention that the recursive approach can be optimized to stop early when both nodes are found, and that handling edge cases like one node being an ancestor of the other is crucial. Also, discuss how the approach changes if the tree is a BST, where you can use value comparisons to guide the search.

1. Clarify the problem and constraints

Ask whether the tree is binary, if nodes have parent pointers, if the nodes are guaranteed to be in the tree, and if multiple queries will be made. This determines the best approach.

2. Present the recursive traversal approach

Explain the standard recursive solution: traverse the tree, and if the current node is one of the targets, return it; otherwise, recurse left and right. If both return non-null, the current node is the LCA. Analyze time O(n) and space O(h) for recursion stack.

3. Discuss alternative approaches

Cover the parent-pointer approach (if available): find paths from root to each node, then find the last common node. Also mention the Euler tour + RMQ approach for O(1) query time after O(n) preprocessing, suitable for multiple queries.

4. Compare complexities and trade-offs

Compare time and space: recursive O(n) time, O(h) space; parent-pointer O(n) time, O(n) space for paths; Euler tour O(n) preprocessing, O(1) query, O(n) space. Discuss when each is preferable.

5. Recommend based on situation

For a single query on a general binary tree without parent pointers, recommend the recursive approach. For multiple queries, recommend Euler tour + RMQ. If parent pointers exist, the parent-pointer approach is simple and efficient.

Key Points to Mention

Time and space complexity of each approach: recursive O(n) time, O(h) space; parent-pointer O(n) time, O(n) space; Euler tour O(n) preprocessing, O(1) query, O(n) space.
Handling edge cases: one node is ancestor of the other, nodes not present, empty tree.
Optimization: early termination in recursion when both nodes found.
Special case: if the tree is a BST, LCA can be found in O(h) time by comparing values.
Trade-offs: recursive is simple but may cause stack overflow for deep trees; iterative with parent pointers avoids recursion; Euler tour is best for frequent queries.
Real-world application: Uber might use LCA in routing or hierarchical data structures, so scalability matters.

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