Pinterest Coding Question: Top K Frequent Elements

Problem overview

You are given an integer array nums and an integer k. Return exactly k distinct integers that appear most frequently in nums — the order does not matter. The key requirement is to return k most frequent distinct elements (not their counts) and to handle the case where many values may share similar frequencies.

What interviewers expect and typical flow

First, you should ask clarifying questions (are numbers limited in range? are duplicates allowed? streaming data?). Then present 1–2 approaches, pick one, and implement it. After coding, discuss correctness, edge cases (k == n, all elements unique), complexity, and possible optimizations.

Common solution approaches

• Frequency counting + min-heap (priority queue): Build a hash map of counts, push (freq, value) onto a min-heap of size k to keep top-k by frequency. Good when you want an easy-to-explain O(n log k) solution.

• Bucket sort (frequency buckets): Create buckets indexed by frequency (0..n). Put values into buckets and scan from high to low to collect k elements for an O(n) time and O(n) space approach.

• Quickselect on unique values: Use selection by frequency to get average O(n) expected time and O(n) space for unique values.

Skill signals to demonstrate

You should show hash-map frequency counting, heap/priority queue usage, bucket-sort intuition, time/space complexity analysis, handling edge cases and trade-offs (when k ~ n, when frequencies are skewed), and clear, testable code. Mention streaming or memory-limited variants (approximate counting or external memory) if prompted.