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 Onsite rounds at Google.

What role is this question designed for?

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

Design structure for insert and k-th largest

Q: Design structure for insert and k-th largest

This question evaluates data-structure design and algorithmic efficiency for dynamic order-statistics over a multiset (duplicates allowed), focusing on implementing insert and k-th largest operations and belonging to the Coding & Algorithms domain.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design a class that supports two operations over a multiset of integers (duplicates allowed): - `insert(num: int) -> void`: add `num` to the data structure. - `findLargest(k: int) -> int`: return the **k-th largest** value in the multiset using **0-based indexing**: - `k = 0` returns the largest value - `k = 1` returns the second largest value - duplicates count as separate elements Example: ``` insert(3) insert(3) insert(2) findLargest(0) -> 3 findLargest(1) -> 3 findLargest(2) -> 2 ``` Requirements: - Optimize for low time complexity of `findLargest(k)`. - You may assume `0 <= k < current_size` when `findLargest` is called. Clarify any additional constraints (expected number of operations, value ranges) as needed.

Quick Answer: This question evaluates data-structure design and algorithmic efficiency for dynamic order-statistics over a multiset (duplicates allowed), focusing on implementing insert and k-th largest operations and belonging to the Coding & Algorithms domain.

Design a data structure over an initially empty multiset of integers that supports two operations: insert(num), which adds a value to the multiset, and findLargest(k), which returns the k-th largest value using 0-based indexing. Duplicates count as separate elements. For this function version of the problem, you are given the full sequence of operations and must return the result of every findLargest query in order. Example: after inserting 3, 3, and 2, findLargest(0) = 3, findLargest(1) = 3, and findLargest(2) = 2.

Constraints

0 <= number of operations <= 200000
-10^9 <= inserted value <= 10^9
Duplicates are allowed and count as separate elements
Each findLargest query is valid when it appears

Examples

Input: ([('insert', 3), ('insert', 3), ('insert', 2), ('findLargest', 0), ('findLargest', 1), ('findLargest', 2)],)

Expected Output: [3, 3, 2]

Explanation: The multiset is [3, 3, 2]. In descending order it is [3, 3, 2], so the 0-th, 1st, and 2nd largest values are 3, 3, and 2.

Input: ([('insert', -1), ('insert', 5), ('insert', 5), ('insert', 0), ('findLargest', 0), ('findLargest', 1), ('findLargest', 2), ('insert', -3), ('findLargest', 4)],)

Expected Output: [5, 5, 0, -3]

Explanation: Before inserting -3, the descending order is [5, 5, 0, -1], so queries 0, 1, and 2 return 5, 5, and 0. After inserting -3, descending order is [5, 5, 0, -1, -3], so k=4 returns -3.

Input: ([('insert', 7), ('findLargest', 0)],)

Expected Output: [7]

Explanation: With only one element, the largest value is 7.

Input: ([('insert', 10), ('insert', 4), ('insert', 8), ('findLargest', 1), ('insert', 8), ('findLargest', 2), ('findLargest', 3)],)

Expected Output: [8, 8, 4]

Explanation: After the first three inserts, descending order is [10, 8, 4], so k=1 returns 8. After inserting another 8, descending order is [10, 8, 8, 4], so k=2 returns 8 and k=3 returns 4.

Input: ([],)

Expected Output: []

Explanation: No operations means there are no queries to answer.

Hints

If you store frequencies of values instead of the whole multiset in sorted order, inserts become much cheaper.
Convert the k-th largest query into an order-statistics query: in ascending order, it is the (current_size - k)-th smallest element.

Quick Overview

This question evaluates data-structure design and algorithmic efficiency for dynamic order-statistics over a multiset (duplicates allowed), focusing on implementing insert and k-th largest operations and belonging to the Coding & Algorithms domain.