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 Amazon.

What role is this question designed for?

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

Find Most Frequent Values | Amazon Coding Question

Find Most Frequent Values

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an integer array `nums` and an integer `k`, return the `k` distinct values that occur most frequently in `nums`. The result may be returned in any order. If multiple values have the same frequency, any ordering among them is acceptable. You may assume that the input is constructed so that there is at least one valid answer of size `k`. Example: ```text Input: nums = [1, 1, 1, 2, 2, 3], k = 2 Output: [1, 2] ``` Follow-up: After explaining a straightforward counting-and-sorting solution, implement a more efficient version using a heap.

Quick Answer: This question evaluates proficiency in analyzing element frequency distributions, choosing appropriate data structures, and optimizing top-k selection with attention to time and space complexity.

Part 1: Find Most Frequent Values Using Counting and Sorting

Given an integer array nums and an integer k, return the k distinct values that occur most frequently in nums. For deterministic testing, return the selected values ordered by decreasing frequency. If two values have the same frequency, the smaller integer should come first. If more than k values are tied at the cutoff frequency, this same tie-break rule determines which values are included.

Constraints

1 <= len(nums) <= 100000
1 <= k <= number of distinct values in nums
-1000000000 <= nums[i] <= 1000000000
The input is guaranteed to contain at least k distinct values.

Examples

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

Expected Output: [1, 2]

Explanation: 1 appears 3 times and 2 appears 2 times, so they are the two most frequent values.

Input: ([5], 1)

Expected Output: [5]

Explanation: Edge case: the array has only one value.

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

Expected Output: [6, 4, 7]

Explanation: All distinct values are requested, ordered by frequency.

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

Expected Output: [10, 20]

Explanation: 10 and 20 both appear twice; the smaller value comes first.

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

Expected Output: [3, -2]

Explanation: 3 appears 4 times and -2 appears 3 times.

Hints

First count how many times each distinct value appears.
Sort the value-frequency pairs by negative frequency, then by the value itself.

Part 2: Find Most Frequent Values Using a Heap

Given an integer array nums and an integer k, return the k distinct values that occur most frequently in nums. Implement the ranking step using a heap instead of sorting all distinct values. For deterministic testing, return the selected values ordered by decreasing frequency. If two values have the same frequency, the smaller integer should come first. If more than k values are tied at the cutoff frequency, this same tie-break rule determines which values are included.

Constraints

1 <= len(nums) <= 100000
1 <= k <= number of distinct values in nums
-1000000000 <= nums[i] <= 1000000000
The input is guaranteed to contain at least k distinct values.
The intended ranking approach should use a heap and avoid sorting all distinct values.

Examples

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

Expected Output: [1, 2]

Explanation: 1 and 2 have the two highest frequencies.

Input: ([7], 1)

Expected Output: [7]

Explanation: Edge case: only one distinct value exists.

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

Expected Output: [4, 6]

Explanation: 4 and 6 both appear 3 times, and both are selected. They are returned in increasing value order because their frequencies tie.

Input: ([9, 9, 8, 8, 7, 6], 2)

Expected Output: [8, 9]

Explanation: 8 and 9 both appear twice. They are the two most frequent values and are returned in increasing value order.

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

Expected Output: [1, 2]

Explanation: All values appear once, so the two smallest values are selected by the deterministic tie-break rule.

Hints

You still need a hash map to count frequencies before using the heap.
Maintain a min-heap of at most k candidates so the least desirable candidate can be removed when the heap grows too large.

Quick Overview

This question evaluates proficiency in analyzing element frequency distributions, choosing appropriate data structures, and optimizing top-k selection with attention to time and space complexity.