← Google Interview Insights

Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Google SWE interview with a tree problem that looked straightforward but had enough moving parts to keep me on my toes for the whole session.

Questions Asked (1)

Q1

Given a tree where each node has a price, a parent pointer, and a list of children, find the cheapest common ancestor of two distinct nodes a and b.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

My first instinct was to walk up from both nodes and collect ancestors, then find the minimum price among the shared ones.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints (e.g., tree size, whether parent pointers are available, if nodes are distinct) and then propose an efficient algorithm. A common optimal approach is to find the lowest common ancestor (LCA) using parent pointers and then traverse the path from the LCA to each node to find the minimum price. Alternatively, use binary lifting for O(log n) LCA queries if multiple queries are expected.

Pro tip: Discuss trade-offs between preprocessing time and query time: if only one query, a simple two-pointer approach from the nodes upward is O(h); if many queries, invest in binary lifting or Euler tour + RMQ for O(1) or O(log n) per query. Also, mention that the cheapest common ancestor might not be the LCA itself but could be an ancestor of the LCA, so you need to consider all common ancestors.

1. Clarify the problem

Ask about tree size, number of queries, whether parent pointers are given, and if nodes are guaranteed to be in the same tree. Confirm that 'cheapest common ancestor' means the common ancestor with the minimum price.

2. Identify common ancestors

Explain that common ancestors are nodes on the intersection of the paths from root to a and root to b. The set includes the LCA and all its ancestors up to the root.

3. Find the LCA efficiently

Use parent pointers to move up from a and b to find the LCA. For a single query, use a two-pointer technique: equalize depths, then move both up until they meet. For multiple queries, consider binary lifting or Euler tour + RMQ.

4. Compute minimum price on path

Once the LCA is found, traverse from the LCA up to the root (or from a and b up to the LCA) to find the minimum price among all common ancestors. Alternatively, precompute prefix minima if many queries.

5. Analyze complexity and trade-offs

State the time and space complexity of your approach. Discuss alternatives like using a hash set to store ancestors of a and then checking b's ancestors, and when each is preferable.

Key Points to Mention

  • Definition of common ancestor and how it relates to the LCA.
  • Two-pointer technique for finding LCA with parent pointers.
  • Binary lifting for O(log n) LCA queries with O(n log n) preprocessing.
  • Euler tour + RMQ for O(1) LCA queries after O(n log n) preprocessing.
  • Trade-offs between preprocessing time and query time based on number of queries.
  • Edge cases: a is ancestor of b, b is ancestor of a, nodes not in same tree, negative prices.

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