Atlassian Coding Interview: Page Tree Common Ancestor

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the P40 role at Atlassian. We'll work through one coding problem together, and I'd like you to think out loud as you code. If you need to step out or take a break, you can pause any time with the Pause button at the top right.

The problem is about finding shared ancestors in a Confluence-style page hierarchy, and it's up in your Problem tab now. Please read it through, take your time, and ask me any questions before you start.

The problem

Confluence pages form a hierarchy in which every page except the root has exactly one parent page.

• parent: parent[i] is the parent of page i; the root's entry is -1.
• queries: each [a, b] is a pair of distinct leaf pages (pages with no children).

For each query, return the lowest common ancestor of a and b: the deepest page whose subtree contains both. Return the answers in query order. Pages are numbered 0..n-1 in any order, so the root need not be page 0.

Example: parent = [-1,0,0,1,1,2,2,4,4], queries = [[7,8],[3,7],[7,6],[5,6]] → [4,1,0,2]

Sizes: up to 10^5 pages and 10^5 queries; the tree may be very deep.