Katkat
Back

Find kth element and sliding-window kth in stream

xAISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to maintain order statistics in a streaming context, moving from a static selection problem to an efficient sliding-window implementation.

Part 1: Finding the Kth Largest Element

Given an unsorted array of integers nums and an integer k, write a function findKthLargest(nums, k) that returns the kth largest element in the array. You should aim for an average time complexity of O(n).

Part 2: Sliding Window Kth Largest

Design a class SlidingWindowKth that maintains the kth largest element for a sliding window of size w. The class should support two methods:

  1. add(val): Adds a new value to the stream.
  2. getKth(): Returns the kth largest element currently present in the window of the last w elements.

Constraints

  • 1 <= k <= w <= 10^5
  • 1 <= nums.length <= 10^5
  • Values are in the range [-10^6, 10^6]

Example

w = 3, sequence: [1, 5, 2, 8, 3]

  • Window [1, 5, 2]: 2nd largest is 2
  • Window [5, 2, 8]: 2nd largest is 5
  • Window [2, 8, 3]: 2nd largest is 3

Implementation Signature

class SlidingWindowKth:
    def __init__(self, w: int, k: int):
        pass

    def add(self, val: int) -> int:
        pass

Hints

Hint 1

For the first part, consider the QuickSelect algorithm which partitions the array around a pivot to avoid full sorting.

Hint 2

For the sliding window, a simple heap is insufficient because removing the element that slides out of the window is difficult; consider using two balanced heaps or a SortedList/TreeMap structure.

Hint 3

Since the value range is fixed and potentially dense, a Fenwick tree (Binary Indexed Tree) or a segment tree mapping values to frequencies could provide logarithmic time updates.

Follow-up questions

  • How would you optimize the solution if the input stream contains a very large number of duplicate values?
  • If the window size `w` is massive (e.g., 10^9), how would you handle memory constraints?
  • How does your implementation change if the distribution of incoming values is heavily skewed towards the minimum or maximum?