Design LCA and find K closest points
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.
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(
- 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:
- Implement a baseline that sorts all points by distance and returns the first k.
-
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.
- 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.