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 k most frequent elements, discuss O(n)

Quick Overview

Find k most frequent elements, discuss O(n) evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question Given an integer array `nums` of length `n` and an integer `k` (where `1 ≤ k ≤` the number of distinct values in `nums`), return **any** ordering of the `k` values that occur most frequently. Work through the problem in increasing order of efficiency: 1. **Baseline.** Describe a straightforward approach (e.g. count frequencies, then sort the distinct values by frequency). Analyze its time and space complexity. 2. **Heap-based.** Improve the selection step to **O(n log k)** time using a typical data structure (a size-`k` heap) instead of fully sorting all distinct values. Explain why this is better when `k` is much smaller than the number of distinct values. 3. **Linear time.** Achieve **expected O(n) time and O(n) extra space** *without* any global sort. Explain the data structures you would use (bucket sort by frequency, or Quickselect on the frequency counts) and implement that approach. Discuss the time/space trade-offs of each approach and when each is preferable. **Example** ``` nums = [1, 1, 1, 2, 2, 3], k = 2 -> [1, 2] (any order accepted) nums = [1], k = 1 -> [1] ```

Quick Answer: Find k most frequent elements, discuss O(n) evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given an integer array `nums` of length `n` and an integer `k` (where `1 <= k <=` the number of distinct values in `nums`), return the `k` values that occur most frequently. The k most-frequent values are uniquely determined; for this console, return them ordered by frequency descending, breaking ties by value ascending, so the result is deterministic. Work through the problem in increasing order of efficiency and pick one to implement: 1. **Baseline** — Count frequencies with a hash map, then sort the distinct values by frequency and take the first `k`. Time O(n + d log d), space O(d), where `d` is the number of distinct values. 2. **Heap-based** — Keep a size-`k` min-heap keyed on frequency so you never fully order the long tail of infrequent values. Time O(n + d log k); strictly better than the baseline when `k` is much smaller than `d`. 3. **Linear time** — Use bucket sort by frequency: frequencies live in `[1, n]`, so drop each value into a bucket indexed by its count and scan buckets from highest frequency down until you have `k` values. Time O(n), space O(n), with no global sort. (Quickselect on the frequency counts is the expected-O(n) alternative with O(1) extra selection space.) **Examples** ``` nums = [1, 1, 1, 2, 2, 3], k = 2 -> [1, 2] nums = [1], k = 1 -> [1] ```

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
1 <= k <= number of distinct values in nums
The k most-frequent values are uniquely determined for the given inputs

Examples

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

Expected Output: [1, 2]

Explanation: 1 appears 3 times and 2 appears 2 times — the two most frequent. 3 appears once and is excluded.

Input: ([1], 1)

Expected Output: [1]

Explanation: Single element; the only value is the most frequent.

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

Expected Output: [6, 4]

Explanation: Frequencies: 6->4, 4->3, 7->2. Top 2 ordered by frequency descending: [6, 4].

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

Expected Output: [-1]

Explanation: -1 occurs 3 times, more than -2 (2) and 5 (1); negatives are handled like any other value.

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

Expected Output: [5]

Explanation: Only one distinct value, repeated five times.

Input: ([10, 20, 30, 40], 4)

Expected Output: [10, 20, 30, 40]

Explanation: All values distinct with frequency 1; k equals the number of distinct values, so all are returned (ties broken by value ascending).

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

Expected Output: [1, 2, 3]

Explanation: All three values tie at frequency 2; the deterministic tie-break orders them by value ascending.

Input: ([0, 0, 0, 9, 9, 8, 8, 8, 8], 3)

Expected Output: [8, 0, 9]

Explanation: Frequencies: 8->4, 0->3, 9->2. Ordered by frequency descending gives [8, 0, 9].

Hints

Every approach shares the same first step: count how often each value appears with a hash map in O(n) time.
You never need to fully sort all distinct values when you only want the top k — a size-k min-heap selects them in O(n + d log k).
No value can appear more than n times, so frequencies fall in [1, n]. Bucket the values by their count and scan from the highest bucket down for true O(n) time with no sort.

Quick Overview