LinkedIn·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026Remote

Summary

LinkedIn infrastructure interview, one technical coding round focused on a data structure design problem. The question was a step up from the classic version and I wasn't fully prepared for the wrinkle around duplicate handling.

Questions Asked (1)

Design a data structure that supports insert, remove, and getRandom in average O(1) time, where duplicates are allowed and getRandom must return elements with probability proportional to their frequency.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the LC 380 version cold, array plus hashmap, swap-with-last on remove, done.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying that the data structure must handle duplicates and that getRandom should return elements with probability proportional to their frequency. Then, propose a design that combines a dynamic array to store all elements (including duplicates) and a hash map to track each element's indices in the array, enabling O(1) insert, remove, and getRandom by leveraging random index selection.

Pro tip: Mention that getRandom can simply pick a random index from the array, which naturally gives probability proportional to frequency because duplicates occupy multiple slots. Also, highlight that removal can be done in O(1) by swapping the element to remove with the last element and updating the hash map, a common trick in array-based data structures.

1. Clarify requirements and constraints

Confirm that duplicates are allowed, getRandom must be frequency-proportional, and all operations should be average O(1). Discuss potential edge cases like removing non-existent elements.

2. Propose core data structures

Use a dynamic array (list) to store all elements, including duplicates, and a hash map (dictionary) mapping each unique element to a set of its indices in the array. This allows O(1) access and updates.

3. Design insert operation

Append the new element to the array and add its index to the hash map's set for that element. Both operations are O(1) on average.

4. Design remove operation

To remove one occurrence of an element, get an index from its set in the hash map. Swap the element at that index with the last element in the array, update the hash map for the swapped element, then remove the last element from the array and the index from the set. This is O(1) average.

5. Design getRandom operation

Generate a random index uniformly from 0 to array length - 1 and return the element at that index. Since duplicates occupy multiple slots, the probability of returning an element is proportional to its frequency.

Key Points to Mention

Use of a dynamic array to store all elements, including duplicates, enabling O(1) random access.
Hash map mapping each unique element to a set of its indices in the array for O(1) insert and remove.
Swap-with-last technique for O(1) removal from the array, updating the hash map accordingly.
getRandom implemented by picking a random index from the array, which naturally gives frequency-proportional probability.
Average O(1) time complexity for all operations, with worst-case O(n) for hash map collisions but amortized O(1).
Handling edge cases: removing an element not present, empty data structure, and maintaining index sets correctly.

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