HardCoding

Cycle Length Queries in a Tree

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Use parent(x) = floor(x/2).
02For each pair, start answer at one edge for the added connection.
03Move the larger node upward until labels meet.
04Increment for each tree edge traversed.
05Return the accumulated cycle length.

Reference answer

The implicit tree labels follow heap parenting: parent(x) = floor(x/2). Adding an edge between nodes a and b creates a cycle whose length is the existing tree distance between a and b plus one. Find that distance without constructing the tree: while a differs from b, divide the larger label by two and increment a counter. This moves each node toward their lowest common ancestor; when they meet, the counter is the tree path length, so return counter + 1 for the added edge. Starting the answer at one makes the extra edge explicit. Test equal nodes if the input allows them and ancestor-descendant pairs. Each query takes O(log(max(a,b))) time and O(1) space.

Then expect these follow-ups

How would binary lifting change this for a non-implicit tree?
Tests: constraint adaptation
Why does moving the larger heap label preserve the path to the LCA?
Tests: correctness reasoning

Hiring now

Get the Microsoft interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question