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.

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.

Hints

  1. First count how many times each distinct value appears.
  2. 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.

Hints

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

Loading coding console...