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 Technical Screen rounds at Meta.

What role is this question designed for?

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

Find top-K frequent values with tiebreaks

Quick Overview

Given an integer array and k, return the k highest-frequency values, breaking ties by smaller numeric value then earlier first-occurrence index (lexicographically for strings), and returning all uniques when k is too large. The solution covers an O(n) bucket-counting algorithm plus O(n log k) heap and expected-linear quickselect alternatives with their trade-offs, derives floor((sqrt(8n+1)-1)/2) as the maximum number of distinct frequency values, and outlines input validation for robustness at scale.

Find top-K frequent values with tiebreaks

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question Given an integer array `nums` and an integer `k`, return the `k` values with the highest frequency. The array can contain up to 10^6 elements. When multiple values share the same frequency, break ties deterministically: 1. First by **smaller numeric value** (for string inputs, break ties lexicographically instead). 2. Then by **earlier first-occurrence index** in the array. Your solution should address all of the following: 1. Return the correct `k` values under the tie-breaking rules above. If `k` exceeds the number of distinct values, return all of the distinct values. 2. Provide an algorithm faster than `O(n log n)` — for example `O(n)` or `O(n log k)` — and justify why it stays correct under the tie rules. 3. Discuss and compare the trade-offs among the main approaches: bucket counting by frequency, a size-`k` heap, and a selection/quickselect-based partition. State the time and space complexity of each. 4. **Follow-up:** For an array of length `n`, derive the maximum possible number of *distinct* frequency values achievable across its unique elements, and justify your formula. 5. **Follow-up:** How would you validate and guard against invalid inputs (e.g. non-integer elements, negative or non-integer `k`, an extremely large `n`) while keeping the service robust?

Quick Answer: Given an integer array and k, return the k highest-frequency values, breaking ties by smaller numeric value then earlier first-occurrence index (lexicographically for strings), and returning all uniques when k is too large. The solution covers an O(n) bucket-counting algorithm plus O(n log k) heap and expected-linear quickselect alternatives with their trade-offs, derives floor((sqrt(8n+1)-1)/2) as the maximum number of distinct frequency values, and outlines input validation for robustness at scale.

Given an integer array `nums` and an integer `k`, return the `k` values with the highest frequency. When multiple values share the same frequency, break ties deterministically: 1. First by **smaller numeric value**. 2. Then by **earlier first-occurrence index** in the array. Rules: - Return the result as a list ordered from highest rank to lowest under the rules above (frequency descending, then smaller value, then earlier first occurrence). - If `k` is greater than or equal to the number of distinct values, return all of the distinct values (still in ranked order). - If `k <= 0`, return an empty list. Aim for an algorithm faster than `O(n log n)` overall (counting is `O(n)`; only the relevant tie tiers need ordering).

Constraints

0 <= len(nums) <= 10^6
Elements are integers (may be negative).
k may be 0, negative, or larger than the number of distinct values.
If k <= 0, return [].
If k >= number of distinct values, return all distinct values in ranked order.

Examples

Input: ([1, 1, 1, 2, 2, 3], 2)

Expected Output: [1, 2]

Explanation: Frequencies: 1->3, 2->2, 3->1. Top 2 by frequency are 1 then 2.

Input: ([4, 4, 5, 5, 6], 2)

Expected Output: [4, 5]

Explanation: 4 and 5 both have frequency 2; tie broken by smaller value (4 before 5). 6 has frequency 1.

Input: ([7], 1)

Expected Output: [7]

Explanation: Single element; only one distinct value.

Input: ([], 3)

Expected Output: []

Explanation: Empty array has no distinct values, so the result is empty even though k=3.

Input: ([1, 2, 3], 0)

Expected Output: []

Explanation: k <= 0 returns an empty list.

Input: ([5, 5, 5], 10)

Expected Output: [5]

Explanation: k exceeds the 1 distinct value, so return all distinct values.

Input: ([3, 1, 2], 5)

Expected Output: [1, 2, 3]

Explanation: All have frequency 1; k exceeds distinct count, so return all, ordered by smaller value first.

Input: ([-1, -1, -2, -2, 0], 2)

Expected Output: [-2, -1]

Explanation: -1 and -2 both have frequency 2; tie broken by smaller value, so -2 ranks before -1. 0 has frequency 1.

Input: ([10, 20, 20, 10, 30], 2)

Expected Output: [10, 20]

Explanation: 10 and 20 both have frequency 2; tie broken by smaller value (10 before 20).

Input: ([1, 1, 2, 2, 3, 3, 3], 3)

Expected Output: [3, 1, 2]

Explanation: 3 has frequency 3 (highest). 1 and 2 each have frequency 2; tie broken by smaller value, so 1 before 2.

Hints

Count each value's frequency in one O(n) pass, and record its first-occurrence index in the same pass.
Define a single total order over the distinct values: frequency descending, then smaller numeric value, then earlier first-occurrence index. Sort or select by that key.
Two distinct integers can never be equal, so the first-occurrence tiebreak only ever resolves ties between a value's own equal keys — it is a stable secondary key, harmless to keep.
For an O(n)-style speedup over O(n log n), bucket values by frequency (buckets[f] = values seen f times) and walk buckets from high frequency to low, ordering only the tier you are currently emitting from.
Handle k <= 0 (return []) and k >= distinct count (return all distinct, still ranked) as explicit branches.

Last updated: Jun 26, 2026

Loading coding console...

Quick Overview

Find top-K frequent values with tiebreaks

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Constraints

0 <= len(nums) <= 10^6
Elements are integers (may be negative).
k may be 0, negative, or larger than the number of distinct values.
If k <= 0, return [].
If k >= number of distinct values, return all distinct values in ranked order.

Examples

Input: ([1, 1, 1, 2, 2, 3], 2)

Expected Output: [1, 2]

Explanation: Frequencies: 1->3, 2->2, 3->1. Top 2 by frequency are 1 then 2.

Input: ([4, 4, 5, 5, 6], 2)

Expected Output: [4, 5]

Explanation: 4 and 5 both have frequency 2; tie broken by smaller value (4 before 5). 6 has frequency 1.

Input: ([7], 1)

Expected Output: [7]

Explanation: Single element; only one distinct value.

Input: ([], 3)

Expected Output: []

Explanation: Empty array has no distinct values, so the result is empty even though k=3.

Input: ([1, 2, 3], 0)

Expected Output: []

Explanation: k <= 0 returns an empty list.

Input: ([5, 5, 5], 10)

Expected Output: [5]

Explanation: k exceeds the 1 distinct value, so return all distinct values.

Input: ([3, 1, 2], 5)

Expected Output: [1, 2, 3]

Explanation: All have frequency 1; k exceeds distinct count, so return all, ordered by smaller value first.

Input: ([-1, -1, -2, -2, 0], 2)

Expected Output: [-2, -1]

Explanation: -1 and -2 both have frequency 2; tie broken by smaller value, so -2 ranks before -1. 0 has frequency 1.

Input: ([10, 20, 20, 10, 30], 2)

Expected Output: [10, 20]

Explanation: 10 and 20 both have frequency 2; tie broken by smaller value (10 before 20).

Input: ([1, 1, 2, 2, 3, 3, 3], 3)

Expected Output: [3, 1, 2]

Explanation: 3 has frequency 3 (highest). 1 and 2 each have frequency 2; tie broken by smaller value, so 1 before 2.

Hints

Count each value's frequency in one O(n) pass, and record its first-occurrence index in the same pass.
Define a single total order over the distinct values: frequency descending, then smaller numeric value, then earlier first-occurrence index. Sort or select by that key.
Two distinct integers can never be equal, so the first-occurrence tiebreak only ever resolves ties between a value's own equal keys — it is a stable secondary key, harmless to keep.
For an O(n)-style speedup over O(n log n), bucket values by frequency (buckets[f] = values seen f times) and walk buckets from high frequency to low, ordering only the tier you are currently emitting from.
Handle k <= 0 (return []) and k >= distinct count (return all distinct, still ranked) as explicit branches.

Last updated: Jun 26, 2026

Loading coding console...