How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Design LCA and find K closest points

Quick Overview

This question evaluates understanding of tree algorithms (LCA using parent pointers) and selection algorithms (sorting, max-heap, quickselect), emphasizing data structures, algorithmic correctness, and time/space complexity within the Coding & Algorithms domain.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Part A — LCA with parent pointers: You are given two nodes a and b in a rooted tree where each node has a parent pointer (you may or may not have direct access to the root). Design and implement lowestCommonAncestor(a, b) that returns their lowest common ancestor without modifying the nodes. Aim for O(h) time and O( 1) extra space, where h is the height of the tree. Follow-up: State the time and space complexity of your approach. Part B — Return k closest points: You are given an array of n 2D integer points and an integer k (1 ≤ k ≤ n). Return any order of the k points closest to the origin by Euclidean distance (you may compare squared distances). Tasks: 1) Implement a baseline that sorts all points by distance and returns the first k. 2) Propose and implement a more efficient method when k ≪ n using either: - A size-k max-heap maintained while scanning the points, or - Quickselect partitioning to position the kth smallest distance and then collect any k closest points. 3) Define the minimal heap interface you will use (e.g., insert, peek, pop, size, comparator) and show how your solution uses it. Follow-up: For each approach, analyze time and space complexity and compare the trade-offs.

Quick Answer: This question evaluates understanding of tree algorithms (LCA using parent pointers) and selection algorithms (sorting, max-heap, quickselect), emphasizing data structures, algorithmic correctness, and time/space complexity within the Coding & Algorithms domain.

Lowest Common Ancestor with Parent Pointers

You are given a rooted tree encoded as a parent array. `parent[i]` is the index of node `i`'s parent, and the root has `parent = -1`. Given two node indices `a` and `b`, return the index of their lowest common ancestor (LCA) — the deepest node that is an ancestor of both `a` and `b` (a node is considered an ancestor of itself). You must not modify the tree. Aim for O(h) time and O(1) extra space, where h is the height of the tree. Approach: compute the depth of each node by walking up via parent pointers, advance the deeper node up until both are at the same depth, then advance both pointers in lockstep until they meet. Follow-up: state the time and space complexity. Walking to the root is O(h) per node and the lockstep walk is O(h), so total time is O(h); only a few integer variables are used, so extra space is O(1).

Constraints

1 <= number of nodes <= 10^5
parent[i] is a valid node index or -1 (exactly one node is the root)
The structure is a valid rooted tree (no cycles)
0 <= a, b < number of nodes; a and b may be equal
a is an ancestor of b (or vice versa) is allowed, in which case the ancestor itself is the LCA

Examples

Input: ([-1, 0, 0, 1, 1, 2], 3, 4)

Expected Output: 1

Explanation: Nodes 3 and 4 are siblings; both children of node 1, which is their LCA.

Input: ([-1, 0, 0, 1, 1, 2], 3, 5)

Expected Output: 0

Explanation: Node 3's ancestors are {3,1,0}; node 5's are {5,2,0}. The deepest shared ancestor is the root 0.

Input: ([-1, 0, 0, 1, 1, 2], 4, 4)

Expected Output: 4

Explanation: Identical nodes: a node is its own ancestor, so the LCA is the node itself.

Input: ([-1, 0, 0, 1, 1, 2], 1, 3)

Expected Output: 1

Explanation: Node 1 is an ancestor of node 3, so node 1 is the LCA.

Input: ([-1], 0, 0)

Expected Output: 0

Explanation: Single-node tree: the root is the LCA of itself.

Input: ([-1, 0, 1, 2, 3], 4, 1)

Expected Output: 1

Explanation: A linear chain 0->1->2->3->4; node 1 is an ancestor of node 4, so the LCA is 1.

Hints

A node is its own ancestor — if a == b, the answer is that node.
First make the two pointers the same depth by advancing the deeper one upward, then advance both in lockstep until they collide.
Compute depth by counting how many parent hops reach the root (the node whose parent is -1).

K Closest Points to the Origin

You are given an array of n 2D integer points and an integer k (1 <= k <= n). Return the k points closest to the origin (0, 0) by Euclidean distance. Because the square root is monotonic, you may compare squared distances x*x + y*y to avoid floating point. The problem allows the k closest points in any order; this reference returns them sorted by squared distance (ties broken by x then y) so the result is deterministic and easy to grade. The straightforward baseline sorts all n points by distance and takes the first k in O(n log n). When k << n, a size-k max-heap maintained while scanning gives O(n log k), and Quickselect gives expected O(n). A minimal max-heap interface would expose insert(item), peek() (the current farthest), pop(), and size(), with the comparator ordering by squared distance. Follow-up: compare trade-offs — sort is simplest and cache-friendly but O(n log n); the heap is O(n log k) time and O(k) space and streams well; Quickselect is expected O(n) time and O(1) extra space but worst-case O(n^2) and reorders the input.

Constraints

1 <= k <= n <= 10^4
Each point is [x, y] with -10^4 <= x, y <= 10^4
Distances are compared via squared Euclidean distance to avoid floating point
The k closest points may be returned in any order (this reference returns them sorted by distance, then x, then y)
Duplicate points are allowed

Examples

Input: ([[1, 3], [-2, 2]], 1)

Expected Output: [[-2, 2]]

Explanation: Squared distances: [1,3]->10, [-2,2]->8. The single closest point is [-2, 2].

Input: ([[3, 3], [5, -1], [-2, 4]], 2)

Expected Output: [[3, 3], [-2, 4]]

Explanation: Squared distances: [3,3]->18, [5,-1]->26, [-2,4]->20. The two closest are [3,3] and [-2,4].

Input: ([[0, 0]], 1)

Expected Output: [[0, 0]]

Explanation: Single point at the origin; it is trivially the closest.

Input: ([[1, 0], [0, 1], [-1, 0], [0, -1]], 4)

Expected Output: [[-1, 0], [0, -1], [0, 1], [1, 0]]

Explanation: All four points are at distance 1; k equals n so all are returned, sorted by (dist, x, y).

Input: ([[2, 2], [2, 2], [1, 1]], 2)

Expected Output: [[1, 1], [2, 2]]

Explanation: Duplicates allowed: [1,1] (dist 2) is closest, then one copy of [2,2] (dist 8).

Input: ([[5, 5], [1, 1], [-3, -3], [0, 0]], 3)

Expected Output: [[0, 0], [1, 1], [-3, -3]]

Explanation: Squared distances: origin->0, [1,1]->2, [-3,-3]->18, [5,5]->50. The three closest are [0,0], [1,1], [-3,-3].

Hints

Compare x*x + y*y instead of sqrt(x*x + y*y); the ordering is identical and stays in integer arithmetic.
Baseline: sort all points by squared distance and slice the first k.
For k << n, maintain a size-k max-heap keyed on squared distance, or use Quickselect to position the kth smallest and collect everything to its left.

Quick Overview