Katkat
Back

Implement frequency + distance top‑K queries

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This pair of problems evaluates algorithmic and data-structure skills including frequency counting, multi-criteria ordering and selection for top-K results, geometric distance computation for tie-breaking, and time-indexed storage with nearest-timestamp retrieval.

You will implement solutions for two coding interview questions.

Question 1: Return the top‑K points by frequency (with distance tie‑break)

You are given an array points of 2D integer points, where each point is represented as [x, y]. The array may contain duplicates (the same [x, y] can appear multiple times).

Define:

  • freq(p) = number of times point p appears in the array.
  • dist(p) = squared Euclidean distance to the origin, x^2 + y^2.

Return k distinct points sorted by the following priority:

  1. Higher frequency first (freq descending)
  2. If frequencies tie, smaller distance first (dist ascending)
  3. If still tied, sort by x ascending, then y ascending

Input

  • points: list of length n, each element [x, y]
  • k: integer, 1 <= k <= (# of distinct points)

Output

  • A list of k distinct points following the ranking above.

Constraints (typical interview assumptions)

  • 1 <= n <= 2 * 10^5
  • -10^4 <= x, y <= 10^4

Question 2: Time-based key-value store with “closest timestamp” lookup

Design a data structure supporting the following operations:

  • set(key, value, timestamp): store the string value for string key at integer timestamp.
  • Assume timestamps for the same key are inserted in non-decreasing order.
  • getClosest(key, timestamp) -> value or "":
  • If key has no stored values, return "".
  • Otherwise, return the value whose stored timestamp is closest to the query timestamp.
  • If there is a tie (equal distance to two timestamps), return the value with the smaller timestamp.

Example

If for key "a" you stored timestamps [2, 10, 15] with values ["x", "y", "z"]:

  • getClosest("a", 11) returns "y" (10 is closest)
  • getClosest("a", 14) returns "z" (15 is closest)
  • getClosest("a", 12) returns "y" (10 and 15 are equally far; choose smaller timestamp)

What to discuss

  • Time and space complexity of your approach
  • How you would improve a “naive” solution (e.g., linear scan) to a more optimal one

Constraints (typical interview assumptions)

  • Up to 2 * 10^5 total operations
  • Keys and values are strings; timestamps are integers within typical 32-bit range