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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at xAI.

What role is this question designed for?

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

Find kth element and sliding-window kth in stream

Company: xAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

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

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

Part 1: Kth Smallest Element in an Array

Given an integer array nums and an integer k, return the k-th smallest element in nums. k is 1-indexed, so k = 1 means the minimum element. The array may contain duplicate values, and duplicates count as separate elements.

Constraints

1 <= len(nums) <= 200000
1 <= k <= len(nums)
Values may be negative, large, and duplicated
The input is guaranteed to be valid

Examples

Input: ([7], 1)

Expected Output: 7

Explanation: Single-element edge case: the only element is the 1st smallest.

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

Expected Output: 3

Explanation: Sorted order is [1, 2, 3, 4, 5], so the 3rd smallest is 3.

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

Expected Output: 3

Explanation: Sorted order is [1, 2, 3, 3, 3, 5]. Duplicates count, so the 4th smallest is 3.

Input: ([-10, 1000000000, 0, -10, 5], 5)

Expected Output: 1000000000

Explanation: The 5th smallest is the largest value.

Hints

You do not need to fully sort the array; think about partitioning around a pivot.
When many values equal the pivot, grouping values into less-than, equal-to, and greater-than regions avoids repeated work.

Part 2: Kth Smallest Value in Each Time-Based Stream Window

You are given a stream of events as a list, where each event is a pair (timestamp, value). Events arrive in non-decreasing timestamp order. For each new event at time t, consider the inclusive/exclusive time window t - W < timestamp <= t, including the new event. Return the k-th smallest value among events currently in that window. If the current window contains fewer than k events, return -1 for that event. Values are guaranteed to lie in a bounded integer range [min_value, max_value], allowing a frequency table to be used.

Constraints

0 <= len(events) <= 200000
Events are in non-decreasing timestamp order
0 <= W <= 1000000000
1 <= k <= 200000
min_value <= value <= max_value for every event
1 <= max_value - min_value + 1 <= 100000
Timestamps and values are integers

Examples

Input: ([(1, 10), (3, 7), (6, 8)], 5, 2, 0, 10)

Expected Output: [-1, 10, 8]

Explanation: At t=6, the window is 1 < timestamp <= 6, so it contains values [7, 8], whose 2nd smallest is 8.

Input: ([(1, 5), (2, 1), (3, 5), (7, 2), (8, 1)], 5, 2, 1, 5)

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

Explanation: At t=7, events with timestamp <= 2 expire because the condition is timestamp > 2. The remaining values are [5, 2], so the 2nd smallest is 5.

Input: ([], 10, 1, 0, 100)

Expected Output: []

Explanation: Empty stream edge case: there are no events, so there are no outputs.

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

Expected Output: [-1, -1]

Explanation: The window never contains at least 3 events.

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

Expected Output: [-1, 3, 1]

Explanation: All events have the same timestamp and remain in the window together. After all three values [0, 3, 1] arrive, the 2nd smallest is 1.

Hints

Because timestamps arrive in sorted order, expired events can be removed from the front of a queue.
Maintain a frequency count for each possible value, then use cumulative counts to locate the k-th smallest value.

Quick Overview

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.