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

What role is this question designed for?

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

Find K most frequent elements | eBay Coding Question

Q: Find K most frequent elements

This question evaluates a candidate's ability to implement efficient frequency counting and selection logic, demonstrating understanding of data structures, time and space complexity, and handling of large input sizes.

Find K most frequent elements

Company: eBay

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given an array of integers `nums` and an integer `k`. Return the `k` elements that occur most frequently in `nums`. You may return the answer in any order. ## Input - `nums`: list of integers (can include negatives) - `k`: integer where `1 <= k <= number of distinct values in nums` ## Output - A list of `k` integers corresponding to the most frequent values. ## Example - Input: `nums = [1,1,1,2,2,3]`, `k = 2` - Output: `[1,2]` ## Constraints (typical interview bounds) - `1 <= len(nums) <= 10^5` - Values fit in 32-bit signed integer ## Follow-ups (optional) - Can you do it faster than sorting by frequency?

Quick Answer: This question evaluates a candidate's ability to implement efficient frequency counting and selection logic, demonstrating understanding of data structures, time and space complexity, and handling of large input sizes.

Part 1: K Most Frequent Elements by Sorting

Given an integer array nums and an integer k, count how many times each distinct value appears. Return the k most frequent distinct values. To make the output deterministic, return the result ordered by decreasing frequency. If two values have the same frequency, place the smaller value first.

Constraints

1 <= len(nums) <= 10^5
1 <= k <= number of distinct values in nums
-2^31 <= nums[i] <= 2^31 - 1

Examples

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

Expected Output: [1, 2]

Explanation: 1 appears 3 times, 2 appears 2 times, and 3 appears 1 time.

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

Expected Output: [4, 5]

Explanation: 4 appears 3 times. Both 5 and 6 appear 2 times, so 5 comes before 6 because it is smaller.

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

Expected Output: [-2, -1]

Explanation: -2 appears 3 times, -1 appears 2 times, and 3 appears once.

Input: ([7], 1)

Expected Output: [7]

Explanation: Edge case with a single element.

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

Expected Output: [1, 2, 3]

Explanation: All values appear once, so they are ordered by numeric value.

Hints

Use a hash map or Counter to compute the frequency of each number.
After counting, sort the distinct numbers using frequency descending and value ascending.

Part 2: K Most Frequent Elements Without Sorting All Counts

Given an integer array nums and an integer k, return the k most frequent distinct values without sorting all distinct values by frequency. Design an algorithm that keeps only the best k candidates while scanning the frequency table. Return the result ordered by decreasing frequency. If two values have the same frequency, place the smaller value first.

Constraints

1 <= len(nums) <= 10^5
1 <= k <= number of distinct values in nums
-2^31 <= nums[i] <= 2^31 - 1

Examples

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

Expected Output: [1, 2]

Explanation: The two most frequent values are 1 and 2.

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

Expected Output: [5, 2]

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

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

Expected Output: [2, -1, -3]

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

Input: ([10], 1)

Expected Output: [10]

Explanation: Edge case with only one distinct value.

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

Expected Output: [1, 2]

Explanation: All values appear once, so the two smallest values are chosen after tie-breaking.

Hints

First count frequencies with a hash map or Counter.
Use a min-heap of size k so you only keep the current top k candidates instead of sorting every distinct value.

Quick Overview

This question evaluates a candidate's ability to implement efficient frequency counting and selection logic, demonstrating understanding of data structures, time and space complexity, and handling of large input sizes.