LinkedIn·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

LinkedIn software engineer interview with a coding round focused on data structure design. The problem looked manageable at first but the edge cases during deletion are where things get tricky and where I suspect most people trip up.

Questions Asked (1)

Design a data structure that stores integers with duplicates and supports insert, remove, and getRandom, all in expected O(1) time. Insert should return whether the value is new to the collection, remove should return whether anything was actually deleted, and getRandom should pick uniformly across all stored occurrences including duplicates.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The insert and getRandom parts clicked pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map to store each unique value and its count, plus a dynamic array of all values (including duplicates) for O(1) random access. For insert, increment count and append to array; for remove, decrement count and swap-remove from array; for getRandom, pick a random index from the array. This ensures expected O(1) time for all operations.

Pro tip: Clarify that duplicates are treated as separate occurrences, so getRandom must pick uniformly among all stored items, not unique values. Also mention that the swap-remove technique maintains O(1) removal by moving the last element to the removed position.

1. Clarify requirements and edge cases

Confirm that duplicates are allowed and that getRandom should pick uniformly across all occurrences. Discuss edge cases like removing a value not present or inserting a duplicate.

2. Choose data structures

Select a hash map to track counts of each value and a dynamic array to store all values (including duplicates) for random access.

3. Design insert operation

Increment the count in the hash map and append the value to the array. Return true if the count was previously zero (new value), else false.

4. Design remove operation

If the value exists, decrement its count (remove from map if zero) and remove one occurrence from the array using swap-remove: replace the occurrence with the last element and pop. Return true if removal happened, else false.

5. Design getRandom operation

Generate a random index within the array's bounds and return the element at that index. This gives uniform selection across all occurrences.

Key Points to Mention

Hash map for O(1) count lookups and updates.
Dynamic array for O(1) random access and swap-remove for O(1) deletion.
Swap-remove technique: move last element to the removed index and pop.
Handling duplicates: array stores each occurrence, map tracks counts.
Time complexity: all operations expected O(1) due to hash map and array.
Space complexity: O(n) where n is total number of occurrences.

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