FastPrepDynamic Kth Largest Queries
Problem

Dynamic Kth Largest Queries

Learn this problem
Amazon logoAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

You are given an initial list of integer values and a stream of operations. The list changes over time as values are inserted.

Each operation is one of the following:

  • "insert": insert the accompanying value into the list.
  • "find": treat the accompanying value as k and return the current k-th largest value in the list.

Return the answers to all "find" operations in order.

Function

dynamicKthLargestQueries(initialValues: int[], operations: String[], values: int[]) → int[]

Examples

Example 1

initialValues = [3, 7, 1]operations = ["find", "insert", "insert", "find", "find"]values = [3, 4, 9, 2, 4]return = [1, 7, 3]

Initially the sorted values are [1,3,7], so the 3rd largest is 1. After inserting 4 and 9, the values are [1,3,4,7,9]; the 2nd largest is 7 and the 4th largest is 3.

Example 2

initialValues = [5]operations = ["insert", "find", "insert", "find"]values = [2, 1, 10, 2]return = [5, 5]

After inserting 2, the largest value is 5. After inserting 10, the 2nd largest value is still 5.

Constraints

  • operations.length == values.length
  • Each operation is either "insert" or "find".
  • For each "find" operation, 1 <= k <= the current list size.

More Amazon problems

drafts saved locally
public int[] dynamicKthLargestQueries(int[] initialValues, String[] operations, int[] values) {
  // write your code here
}
initialValues[3, 7, 1]
operations["find", "insert", "insert", "find", "find"]
values[3, 4, 9, 2, 4]
expected[1, 7, 3]
checking account