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 Google.

What role is this question designed for?

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

Implement frequency + distance top‑K queries

Quick Overview

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.

Implement frequency + distance top‑K queries

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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

Quick Answer: 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.

Part 1: Top-K Points by Frequency with Distance Tie-Break

Given a list of 2D integer points, where duplicate points may appear, return the top `k` distinct points ranked by these rules: (1) higher frequency first, (2) if frequencies tie, smaller squared distance to the origin first, and (3) if still tied, smaller `x` first, then smaller `y`. The result must contain exactly `k` distinct points in ranked order.

Loading coding console...

Examples

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

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

Explanation: Point [2,2] appears 3 times and [1,1] appears 2 times, so they are the top 2 distinct points.

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

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

Explanation: The points [0,2], [1,2], and [2,1] each appear twice. Their squared distances are 4, 5, and 5, so [0,2] comes first. Between [1,2] and [2,1], x is smaller for [1,2].

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

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

Explanation: [-1,0] and [0,-1] both appear twice and both have squared distance 1. Since x is smaller for [-1,0], it comes first.

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

Expected Output: [[5, -5]]

Explanation: There is only one distinct point, so it must be returned.

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

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

Explanation: All points appear once and all have the same squared distance 2, so ordering is determined by x first, then y.

Part 2: Time-Based Key-Value Store with Closest Timestamp Queries

Process a sequence of operations for a time-based key-value store. Each operation is either `['set', key, value, timestamp]` or `['getClosest', key, timestamp]`. For every `getClosest` operation, return the stored value whose timestamp is closest to the query timestamp. If two timestamps are equally close, choose the value with the smaller timestamp. If the key does not exist, return an empty string `""`. Timestamps for the same key are given in non-decreasing order. If the same key is set multiple times at the same timestamp, the latest value replaces the earlier one.

Constraints

0 <= number of operations <= 2 * 10^5
Keys and values are strings
Timestamps fit in a 32-bit signed integer range
For the same key, `set` operations arrive in non-decreasing timestamp order

Examples

Input: [['set', 'foo', 'x', 5], ['set', 'foo', 'y', 10], ['set', 'foo', 'z', 15], ['getClosest', 'foo', 11], ['getClosest', 'foo', 14], ['getClosest', 'foo', 12]]

Expected Output: ['y', 'z', 'y']

Explanation: For 11, timestamp 10 is closest. For 14, timestamp 15 is closest. For 12, timestamp 10 is closer than 15.

Input: [['set', 'a', 'one', 1], ['set', 'a', 'two', 3], ['set', 'b', 'bee', 2], ['getClosest', 'a', 2], ['getClosest', 'a', 4], ['getClosest', 'b', 10], ['getClosest', 'c', 5]]

Expected Output: ['one', 'two', 'bee', '']

Explanation: For key 'a' at time 2, timestamps 1 and 3 are equally close, so choose the smaller timestamp 1. Key 'c' does not exist, so return an empty string.

Input: [['set', 'k', 'old', 7], ['set', 'k', 'new', 7], ['getClosest', 'k', 7], ['getClosest', 'k', 6], ['getClosest', 'k', 8]]

Expected Output: ['new', 'new', 'new']

Explanation: The second set at timestamp 7 replaces the earlier value. Since only timestamp 7 exists, every query returns 'new'.

Input: []

Expected Output: []

Explanation: No operations means there are no query results.

Solution

def solution(operations):
    from bisect import bisect_left

    store = {}
    result = []

    for op in operations:
        if op[0] == 'set':
            _, key, value, timestamp = op
            if key not in store:
                store[key] = [[], []]

            times, values = store[key]

            if times and times[-1] == timestamp:
                values[-1] = value
            else:
                times.append(timestamp)
                values.append(value)
        else:
            _, key, timestamp = op

            if key not in store:
                result.append("")
                continue

            times, values = store[key]
            i = bisect_left(times, timestamp)

            if i < len(times) and times[i] == timestamp:
                result.append(values[i])
            elif i == 0:
                result.append(values[0])
            elif i == len(times):
                result.append(values[-1])
            else:
                left_diff = timestamp - times[i - 1]
                right_diff = times[i] - timestamp
                if left_diff <= right_diff:
                    result.append(values[i - 1])
                else:
                    result.append(values[i])

    return result

Time complexity: O(n log n). Space complexity: O(n).

Hints

Because timestamps for each key are already ordered, you can store them in arrays and avoid re-sorting.
For a query timestamp, binary search gives the insertion point. The answer must be one of the neighboring timestamps.