Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Google SWE coding round with one tree problem. Pretty focused session, just the one question but they pushed on edge cases and complexity.

Questions Asked (1)

Given a tree where each node has a price and references to its parent and children, find the lowest-cost common ancestor of two given nodes.

Algorithms & Data Structures

Author's notes

My first instinct was to just collect all ancestors of both nodes into sets and intersect them, which works, but then you still have to find the minimum price among the common ones.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that the tree is not necessarily a BST and that 'lowest-cost' means minimizing the sum of prices along the path from the root to the common ancestor. Then propose an algorithm that computes the path from the root to each node, finds the deepest common node, and among all common ancestors selects the one with the minimum cumulative cost.

Pro tip: Mention that if the tree is static, you can preprocess it with binary lifting to answer LCA queries in O(log n) time, but for the cost-minimizing variant you need to store prefix sums and then either scan all common ancestors or use a more advanced technique like heavy-light decomposition with segment trees.

1. Clarify the problem

Ask whether the tree is rooted, whether prices are non-negative, and confirm that 'lowest-cost' refers to the minimum sum of prices along the path from the root to the common ancestor. Also check if multiple queries will be made.

2. Outline a baseline approach

Explain that you can find the path from the root to each node, identify all common ancestors, and then compute the cumulative cost for each common ancestor to pick the minimum. This is O(n) per query in the worst case.

3. Optimize with preprocessing

Propose preprocessing the tree to compute prefix sums from the root to every node and to support fast LCA queries (e.g., binary lifting). Then, to find the minimum-cost common ancestor, you can traverse the common ancestor chain or use a data structure to query the minimum prefix sum among them.

4. Analyze complexity and trade-offs

Compare the time and space complexity of the baseline versus the optimized approach. Discuss when each is appropriate, e.g., for a single query vs. many queries.

5. Handle edge cases

Consider cases where one node is an ancestor of the other, where the root is the only common ancestor, and where prices can be negative (which would change the optimization).

Key Points to Mention

The tree is not necessarily a binary search tree, so you cannot rely on ordering properties.
The lowest-cost common ancestor is not necessarily the lowest (deepest) common ancestor; you must compare cumulative costs.
Preprocessing with prefix sums from the root allows O(1) cost calculation for any ancestor.
Binary lifting can find the LCA in O(log n) time, but finding the minimum-cost ancestor may require additional steps.
If prices are non-negative, the root has cost 0 and costs increase along paths, but the minimum-cost common ancestor could still be deeper if prices are zero or negative.
For multiple queries, consider more advanced data structures like heavy-light decomposition or Euler tour + segment trees to answer minimum prefix sum queries on ancestor paths.

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