How should I practice Top K Frequent Values Across Key-Partitioned Shards?

Start by reading the full statement, solve the visible examples, then compare the pattern against related JPMorgan Chase phone screen problems in FastPrep.

Is Top K Frequent Values Across Key-Partitioned Shards associated with JPMorgan Chase?

FastPrep tags this as a JPMorgan Chase phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Hash Table

Top K Frequent Values Across Key-Partitioned Shards

Learn this problem

● Medium

JPMorgan ChaseFULLTIMEPHONE SCREEN

Problem statement

A data set is split across several partitions. You are given partitions, where each row contains the integer values stored on one worker, and an integer k.

The data is partitioned by key: every occurrence of the same value belongs to exactly one partition. Different partitions therefore have disjoint sets of distinct values.

Return the k most frequent values across the entire data set. Order the result by decreasing frequency. If two values have the same frequency, place the smaller numeric value first.

A scalable solution should compute a local Top K on each partition and merge only those local candidates into a global Top K.

Function

topKFrequentByPartition(partitions: int[][], k: int) → int[]

Examples

Example 1

partitions = [[1,1,1,2],[3,3,4],[5,5,5,5]]k = 3return = [5,1,3]

The frequencies are 5:4, 1:3, 3:2, and 2:1, 4:1. The first three values are [5,1,3].

Example 2

partitions = [[4,4,2,2],[1,1,3],[7]]k = 4return = [1,2,4,3]

Values 1, 2, and 4 each occur twice and are ordered numerically. Values 3 and 7 each occur once, so 3 fills the fourth position.

Constraints

1 <= partitions.length <= 10^4
0 <= partitions[i].length
The total number of values across all partitions is at most 2 * 10^5.
Every distinct value appears in exactly one partition.
1 <= k <= the total number of distinct values.