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

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Zillow during technical interviews.

Implement k-th largest in a number stream

Company: Zillow

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are designing a small library to monitor statistics over a stream of integers. Implement a data structure that, given an integer `k` and an initial list of integers, supports the following operation: - `add(val)`: insert the integer `val` into the stream and return the **k-th largest** element among all elements seen so far (including the new one). More formally, after each call to `add`, if you took all numbers that have been provided (both the initial list and all numbers added so far), sorted them in **non-decreasing** order, you should return the element that is `k` positions from the end (the k-th largest). You may assume that `k` is always valid (i.e., there are at least `k` elements after each `add` call). ### API to implement Define a class or type with: - A constructor that takes: - `k` (an integer) - `nums` (a list/array of integers, possibly empty) - A method: - `add(val: int) -> int` that inserts `val` and returns the current k-th largest element. ### Constraints - You may assume: - `1 \le k \le 10^4` - At most `10^4` calls to `add` will be made. - Each integer value fits in a standard 32-bit signed integer. - Your design should be efficient enough to handle the worst-case number of `add` calls within typical interview time complexity expectations. Describe only the code-level behavior and interface; you do **not** need to provide a working implementation here.

Quick Answer: This question evaluates proficiency with data structures and order-statistics in a streaming context, focusing on API design and time/space complexity trade-offs within the Coding & Algorithms domain.

You are designing a small library to monitor statistics over a stream of integers. Implement a data structure that, given an integer `k` and an initial list of integers, supports inserting new values and querying the **k-th largest** element seen so far. Because the online grader calls a single function, you implement the stateful design as `solution(k, nums, operations)`: - `k`: the rank to track (1-indexed from the largest). - `nums`: the initial list of integers already in the stream (possibly empty). - `operations`: a list of integers, where each value represents one `add(val)` call **in order**. For every value in `operations`, insert it into the stream and record the current k-th largest element among **all** numbers seen so far (the initial `nums` plus every value added up to and including this one). "k-th largest" means: sort all elements in non-decreasing order and take the element `k` positions from the end. Return the list of these recorded values, one per `add` call. You may assume `k` is always valid (there are at least `k` elements after each add). ### Constraints - `1 <= k <= 10^4` - At most `10^4` add calls (length of `operations`). - Each integer fits in a signed 32-bit integer. - Aim for `O(log k)` per add (a size-`k` min-heap keeps the top-k largest; its root is the k-th largest).

Constraints

1 <= k <= 10^4
At most 10^4 add calls (len(operations) <= 10^4)
len(nums) can be 0
Each integer fits in a signed 32-bit integer (-2^31 .. 2^31 - 1)
k is always valid: at least k elements exist after each add

Examples

Input: (3, [4, 5, 8, 2], [3, 5, 10, 9, 4])

Expected Output: [4, 5, 5, 8, 8]

Explanation: Start with [4,5,8,2], k=3. add(3): pool {2,3,4,5,8}, 3rd largest=4. add(5): 3rd largest=5. add(10): 3rd largest=5. add(9): pool now has 8,9,10 as top three, 3rd largest=8. add(4): 3rd largest still 8.

Input: (1, [], [5, 3, 8, 1, 10])

Expected Output: [5, 5, 8, 8, 10]

Explanation: Empty start, k=1 tracks the running maximum: 5, then 5, then 8, then 8, then 10.

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

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

Explanation: k=2 with negatives. After add(-1): {-1,0}, 2nd largest=-1. add(-2): {-2,-1,0}, 2nd largest=-1. add(-3): 2nd largest=-1. add(5): pool top two are 5 and 0, 2nd largest=0.

Input: (4, [7, 7, 7, 7, 7], [7, 7])

Expected Output: [7, 7]

Explanation: Duplicates: every element is 7, so the 4th largest is always 7.

Input: (1, [2147483647], [-2147483648])

Expected Output: [2147483647]

Explanation: 32-bit boundary: INT_MAX already present, adding INT_MIN does not change the maximum (k=1).

Hints

You never need every element sorted at once. To know the k-th largest, you only need to remember the k largest values seen so far.
A min-heap capped at size k does exactly that: push each new value, and if the heap grows past k, pop the smallest. The root is then the k-th largest.
Initialize by heapifying nums and trimming it down to k elements before processing any add call.
Each add is O(log k): one push plus at most one pop. With at most 10^4 adds this is comfortably fast.

Quick Overview

This question evaluates proficiency with data structures and order-statistics in a streaming context, focusing on API design and time/space complexity trade-offs within the Coding & Algorithms domain.