FastPrepCalculating Quantiles
Problems/Calculating Quantiles

Calculating Quantiles

Indeed logoIndeed● MediumNEW GRADINTERNOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The source picture shows the task up to the input format, and other reports from the same test give the rest. The input is q, the number of parts, then unsorted value and count pairs, where a count says how many times its value appears.

No report gives limits. Here, q is 2 to 1000, there are 1 to 10^4 pairs, values run from -10^9 to 10^9, and counts run from 1 to 10^8. The reports also do not say whether a value can be listed in two pairs. Here it can, and its counts add up. You get the pairs as a list and return the quantiles as a list, instead of reading input and printing.

The judged task matches the source at about 90%.

You have a population of N values. Number them 1 to N from lowest to highest, so position 1 holds the smallest value. For a whole number q, the k-th q-quantile is the value at position I_k = N * k / q. If I_k is not a whole number, round it up to the next whole number. There are q - 1 quantiles, one for each k from 1 to q - 1.

The population is given in compressed form. Each pairs[i] = [v, c] means the value v appears c times.

  • The pairs can come in any order.
  • The same value can be listed in more than one pair. Its counts add up.
  • N is the sum of all the counts.

Return the q - 1 quantiles in order, from k = 1 to k = q - 1.

Function

calculateQuantiles(q: int, pairs: int[][]) → int[]

Examples

Example 1

q = 2pairs = [[1,1],[2,3],[3,1]]return = [2]

The pairs describe the values 1, 2, 2, 2, 3, so N = 5. With q = 2 there is one quantile: I_1 = ceil(5 * 1 / 2) = ceil(2.5) = 3. The 3rd value is 2.

Example 2

q = 3pairs = [[7,2],[6,2],[5,2]]return = [5,6]

The pairs are not sorted. Sorted, the values are 5, 5, 6, 6, 7, 7, so N = 6.

  • I_1 = 6 * 1 / 3 = 2, and the 2nd value is 5.
  • I_2 = 6 * 2 / 3 = 4, and the 4th value is 6.

Example 3

q = 2pairs = [[4,100000000],[5,100000000],[6,100000000]]return = [5]

Each value appears 10^8 times, so N = 3 * 10^8. I_1 = 3 * 10^8 / 2 = 1.5 * 10^8. Positions 1 to 10^8 hold 4, and positions 10^8 + 1 to 2 * 10^8 hold 5, so the answer is 5.

Example 4

q = 5pairs = [[15,2],[3,2],[19,1],[5,3],[2,1],[18,2],[11,1],[8,1],[12,1],[6,1]]return = [3,5,11,15]

Sorted, the 15 values are 2, 3, 3, 5, 5, 5, 6, 8, 11, 12, 15, 15, 18, 18, 19. With q = 5 the indices are 15 * k / 5 = 3, 6, 9, 12 for k = 1 to 4. Those positions hold 3, 5, 11, 15.

Constraints

  • 2 <= q <= 1000
  • 1 <= pairs.length <= 10^4
  • pairs[i].length == 2
  • -10^9 <= pairs[i][0] <= 10^9
  • 1 <= pairs[i][1] <= 10^8

More Indeed problems

  • Insert into an Unrolled Linked ListPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Course Completion OrderPHONE SCREEN · Seen May 2025
  • Recipes You Can PreparePHONE SCREEN · Seen May 2025
All Indeed interview questionsSee Indeed hiring insights
Saved
class Solution {
    public int[] calculateQuantiles(int q, int[][] pairs) {
        // Write your code here.
    }
}
Checking account…