Challenge - 5 Problems
Top K Frequent Elements Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
What is the output of this Rust code for top K frequent elements?
Given the Rust code below that finds the top 2 frequent elements in the array, what is the printed output?
DSA Rust
use std::collections::{HashMap, BinaryHeap};
fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
let mut freq_map = HashMap::new();
for num in nums {
*freq_map.entry(num).or_insert(0) += 1;
}
let mut heap = BinaryHeap::new();
for (num, freq) in freq_map {
heap.push((freq, num));
}
let mut result = Vec::new();
for _ in 0..k {
if let Some((_, num)) = heap.pop() {
result.push(num);
}
}
result
}
fn main() {
let nums = vec![1,1,1,2,2,3];
let top2 = top_k_frequent(nums, 2);
println!("{:?}", top2);
}Attempts:
2 left
💡 Hint
Think about which numbers appear most often and how the heap orders elements.
✗ Incorrect
The number 1 appears 3 times, 2 appears 2 times, and 3 appears once. The heap orders by frequency descending, so top 2 are 1 and 2.
🧠 Conceptual
intermediate1:30remaining
Which data structure is best to efficiently find top K frequent elements?
To find the top K frequent elements from a list, which data structure helps efficiently keep track of the highest frequencies?
Attempts:
2 left
💡 Hint
You need to count frequencies and then quickly get top K elements.
✗ Incorrect
HashMap counts frequencies, Min-Heap keeps track of top K elements efficiently by frequency.
🔧 Debug
advanced2:00remaining
What error does this Rust code produce?
Consider this Rust code snippet for top K frequent elements. What error will it raise?
DSA Rust
use std::collections::{HashMap, BinaryHeap};
fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
let mut freq_map = HashMap::new();
for num in nums {
freq_map.insert(num, freq_map.get(&num).unwrap() + 1);
}
let mut heap = BinaryHeap::new();
for (num, freq) in freq_map {
heap.push((freq, num));
}
let mut result = Vec::new();
for _ in 0..k {
if let Some((_, num)) = heap.pop() {
result.push(num);
}
}
result
}Attempts:
2 left
💡 Hint
Check how freq_map.get(&num) is used before insertion.
✗ Incorrect
The code tries to unwrap a None value on first insertion because the key does not exist yet.
❓ Predict Output
advanced2:00remaining
What is the output of this Rust code with tie frequencies?
Given the Rust code below, what is the output when multiple elements have the same frequency?
DSA Rust
use std::collections::{HashMap, BinaryHeap};
fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
let mut freq_map = HashMap::new();
for num in nums {
*freq_map.entry(num).or_insert(0) += 1;
}
let mut heap = BinaryHeap::new();
for (num, freq) in freq_map {
heap.push((freq, num));
}
let mut result = Vec::new();
for _ in 0..k {
if let Some((_, num)) = heap.pop() {
result.push(num);
}
}
result
}
fn main() {
let nums = vec![4,4,1,1,2,2,3];
let top3 = top_k_frequent(nums, 3);
println!("{:?}", top3);
}Attempts:
2 left
💡 Hint
Elements with same frequency may appear in any order depending on heap ordering.
✗ Incorrect
Frequencies: 4=2,1=2,2=2,3=1. The heap pops highest frequency first. Among ties, order depends on element value because BinaryHeap orders by tuple (freq, num).
🚀 Application
expert2:30remaining
How to optimize top K frequent elements for very large input?
You have a very large list of integers and want to find top K frequent elements efficiently in Rust. Which approach is best?
Attempts:
2 left
💡 Hint
Think about time and space efficiency for large data.
✗ Incorrect
Counting frequencies with HashMap is O(n). Using a Min-Heap of size K keeps top K elements efficiently in O(n log k). Sorting entire list is O(n log n) and less efficient.