Walmart Labs·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Walmart Labs SWE interview with a greedy array problem. Pretty algorithmic, nothing too wild, but the follow-up about an O(n) optimization is where things got interesting.

Questions Asked (1)

Given an array of integers and a number m, remove exactly m elements such that the number of distinct values remaining is as small as possible. Return that minimum distinct count.

Algorithms & Data Structures

Author's notes

I got the frequency map idea pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Count the frequency of each distinct value, then sort these frequencies in ascending order. Remove elements starting from the least frequent values until exactly m elements are removed, minimizing the number of distinct values left.

Pro tip: Clarify edge cases upfront, such as when m equals the array length (result 0) or when m is 0 (result is the original distinct count). Also, mention that if removing a value's entire frequency would exceed m, you can partially remove it without reducing the distinct count.

1. Understand the problem and edge cases

Restate the problem to ensure clarity and discuss edge cases like m=0, m=array length, or when all elements are distinct.

2. Count frequencies

Use a hash map to count how many times each distinct value appears in the array.

3. Sort frequencies

Extract the frequencies and sort them in ascending order to prioritize removing values with the smallest counts.

4. Greedily remove elements

Iterate through the sorted frequencies, subtracting each from m until m is exhausted, and count how many distinct values are fully removed.

5. Compute and return result

The minimum distinct count is the total number of distinct values minus the number of fully removed values.

Key Points to Mention

Time complexity: O(n + k log k) where n is array length and k is number of distinct values, due to counting and sorting frequencies.
Space complexity: O(k) for the frequency map and sorted list.
Greedy strategy: removing least frequent values first minimizes distinct count.
Handling partial removal: if m is not enough to remove a full frequency, distinct count doesn't decrease.
Edge cases: m=0 returns original distinct count; m >= n returns 0.
Alternative approaches: using a min-heap for frequencies, but sorting is simpler and efficient.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.