Find kth element and sliding-window kth in stream

Q: Find kth element and sliding-window kth in stream

This question evaluates understanding of order statistics and selection in arrays as well as sliding-window stream processing, including maintaining kth elements with bounded-value frequency or bucket counts.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at xAI.

Q: What role is this question designed for?

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

Question

Loading...

You are given two related tasks.

Task 1: Kth element in an array

Given an integer array nums of length n and an integer k (1-indexed), return the k-th smallest element in nums.

Input: nums: int[] , k: int
Output: int (the k-th smallest value)
Constraints (typical interview):
- 1 <= n <= 2e5
- 1 <= k <= n
- Values may be large and can contain duplicates.

Clarify with the interviewer if they mean k-th smallest vs k-th largest; assume k-th smallest unless stated otherwise.

Task 2 (Follow-up): Kth element per time window in a large data stream

You receive a stream of events (timestamp, value) in non-decreasing timestamp order. For a fixed window length W (time-based window), for each new event at time t you must output the k-th smallest value among all events with timestamps in the inclusive window:

t - W < timestamp <= t

Requirements

The stream can be very large; you cannot store all past events.
Memory is limited; you should store only what is necessary for the current window.
Assume value falls within a known bounded range [MIN, MAX] so you can use a bucket/count array (frequency table) instead of storing all values.

Output

For each incoming event, output the current window’s k-th smallest value (or specify behavior if the window has fewer than k items; e.g., output null/-1/no output).

Example

If W=5, k=2, and events are:

(1, 10) , (3, 7) , (6, 8)

Then at t=6, the window contains timestamps (3,7) and (6,8) (since 6-5=1, and we take timestamp > 1), so the 2nd smallest is 8.