Katkat
Back

Design structure for insert and k-th largest

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a dynamic data structure that maintains elements while efficiently querying the k-th largest value, necessitating a balance between insertion speed and retrieval performance.

Problem Statement

Design a data structure that supports a multiset of integers (where duplicates are allowed) and provides the following operations efficiently:

  1. insert(val): Add an integer val to the multiset.
  2. get_kth_largest(k): Return the k-th largest element currently in the multiset. Assume k is always valid (1 <= k <= current number of elements).

Requirements

Define the class KthLargestTracker with the following signature:

class KthLargestTracker:
    def __init__(self):
        # Initialize your data structure
        pass

    def insert(self, val: int) -> None:
        # Add val to the structure
        pass

    def get_kth_largest(self, k: int) -> int:
        # Return the k-th largest element
        pass

Examples

Example 1: tracker = KthLargestTracker() tracker.insert(10) tracker.insert(20) tracker.insert(10) tracker.get_kth_largest(1) -> returns 20 tracker.get_kth_largest(2) -> returns 10 tracker.get_kth_largest(3) -> returns 10

Constraints

  • Number of insert operations: up to 10^5.
  • Number of get_kth_largest operations: up to 10^5.
  • Values: range between -10^6 and 10^6.

Considerations

Consider the time complexity of both operations. Can you optimize get_kth_largest to be faster than O(N log N)?

Hints

Hint 1

If you maintain a sorted list, insertion takes O(N) time; consider if a tree-based approach or a heap-based approach could improve this.

Hint 2

A min-heap of size K can maintain the K largest elements seen so far, but that only helps find the k-th largest if k is fixed at initialization.

Hint 3

For a general k, consider using a Balanced Binary Search Tree (BST) that stores subtree sizes at each node to facilitate rank-based lookups.

Follow-up questions

  • How would your design change if the multiset was very large and needed to reside on disk instead of memory?
  • If k is always a constant value (e.g., always the 3rd largest), how can you simplify the implementation?
  • How would you handle the removal of an element from the multiset?