Top-K Values per Key in MapReduce
Databricks● MediumFULLTIMEPHONE SCREENProblem statement
Implement the reducer result of a MapReduce pipeline. The mapper forwards every input key-value pair unchanged, and the shuffle stage groups pairs by key. The requested result is the k largest value occurrences within each key.
For this exercise, assume the finite parallel arrays keys and values represent the complete ordered input stream: position i contains pair (keys[i], values[i]). Process every pair. No distributed service or network request is needed in this finite adapter.
For each distinct key, keep its min(k, occurrenceCount) largest integer values. Equal values remain separate occurrences. Return rows [key, decimalValue], with keys in ascending lexicographic order and each key’s selected values in descending numeric order. The decimal value uses the ordinary integer representation with no leading zeroes except 0 itself. An empty stream returns an empty array.
The finite array interface, integer/key domain, duplicate handling, result representation and deterministic order are authored practice conventions. The operation remains per-key selection; do not count hits or choose one global top-k list.
Function
topKPerKey(keys: String[], values: int[], k: int) → String[][]Examples
Example 1
keys = ["b","a","b","a","c"]values = [7,1,4,9,3]k = 2return = [["a","9"],["a","1"],["b","7"],["b","4"],["c","3"]]Return a:9,1 then b:7,4 then c:3. Selection occurs independently within each key.
Example 2
keys = ["x","x","x","x"]values = [5,5,2,5]k = 2return = [["x","5"],["x","5"]]The two retained values are both5; do not deduplicate the stream.
Example 3
keys = []values = []k = 3return = []No key occurs and the output is empty.
Constraints
0 <= keys.length = values.length <= 200.- Every key contains from
1through10lowercase English letters. -10^6 <= values[i] <= 10^6.1 <= k <= 20.- Identical keys and identical values may occur repeatedly; preserve their multiplicity.