Top k points by frequency, and a closest-timestamp key-value store

Two coding problems in one round, both about picking the top k items by a ranking rule.

Part 1: top k points by frequency, with distance as tie-break

You get a list of 2D integer points [x, y] that may contain duplicates. Return k distinct points ranked by: higher frequency first; then smaller squared distance to the origin (x^2 + y^2); then smaller x; then smaller y.

Unless you agree on a different interface with the interviewer, assume:

• top_k_points(points: list[list[int]], k: int) -> list[list[int]]

points = [[1,1],[2,2],[2,2],[1,1],[2,2],[3,3]], k = 2
    ->  [[2,2], [1,1]]                   # frequencies 3 and 2
points = [[1,2],[0,2],[1,2],[2,1],[0,2],[2,1],[3,0]], k = 3
    ->  [[0,2], [1,2], [2,1]]            # all appear twice; distances 4, 5, 5; then x

Constraints: 1 <= len(points) <= 2 * 10^5, -10^4 <= x, y <= 10^4, 1 <= k <= number of distinct points.

Part 2: key-value store that returns the closest timestamp

Build a store with:

• set(key: str, value: str, timestamp: int) -> None — timestamps for one key arrive in non-decreasing order; a second set at the same timestamp replaces the value.
• get_closest(key: str, timestamp: int) -> str — the value whose timestamp is closest to the query; on a tie, the smaller timestamp; "" if the key is unknown.

set("a", "x", 2); set("a", "y", 10); set("a", "z", 15)
get_closest("a", 11)  ->  "y"
get_closest("a", 14)  ->  "z"
get_closest("a", 12)  ->  "y"     # 10 and 15 are equally close; the smaller wins
get_closest("b", 5)   ->  ""

Constraints: up to 2 * 10^5 operations; timestamps fit in 32 bits.

Clarifying questions

• Part 1: can k exceed the number of distinct points?
• Part 2: can timestamps for a key arrive out of order?
• Part 2: what happens on a query before the first or after the last timestamp?

What a strong answer covers

• Part 1: count with a hash map, then sort distinct points by the key (-freq, dist, x, y) in O(d log d), or keep a heap of size k for O(d log k); quickselect as an O(d) average alternative.
• Part 2: per key, parallel lists of timestamps and values; binary search for the insertion point and compare the two neighbours; O(log n) per query and O(1) amortized per set.
• Improving on the naive linear scans and stating the complexity of each step.

Follow-ups

• Part 1: points stream in and k is fixed; keep the answer current.
• Part 2: timestamps may arrive out of order.
• Part 2: return the closest value at or before the timestamp only.