LinkedIn·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

LinkedIn SWE coding round, one problem the whole session: LC 381, the follow-up to the classic insert/delete/getRandom question but with duplicates allowed. The index bookkeeping is where people fall apart and I was no exception.

Questions Asked (1)

Implement a RandomizedCollection 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 how many times they appear.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The array plus hashmap idea comes to you pretty fast, but the devil is in the swap.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a dynamic array to store all elements (including duplicates) and a hash map from each unique value to a set of its indices in the array. For insert, append to the array and add the index to the value's set; for remove, swap the element to remove with the last element, update the moved element's index, then remove the last element; for getRandom, pick a random index from the array. This achieves average O(1) time for all operations.

Pro tip: When removing, always swap with the last element to avoid shifting, and handle the edge case where the removed element is the last element itself. Also, mention that using a set for indices ensures O(1) removal of the index, and that getRandom is O(1) because array access is constant time.

1. Clarify requirements and constraints

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

2. Design data structures

Propose using a dynamic array (list) to store all elements and a hash map mapping each value to a set of indices where it appears. Explain why a set is used instead of a list for indices (O(1) removal).

3. Implement insert operation

Append the value to the array, add its index to the set in the hash map, and return true. If the value is new, create a new set.

4. Implement remove operation

Check if the value exists; if not, return false. Get an arbitrary index from the value's set, swap the element at that index with the last element in the array, update the index set for the swapped element, then remove the last element from the array and the index from the value's set. If the set becomes empty, remove the key from the map.

5. Implement getRandom operation

Generate a random index between 0 and array length - 1, and return the element at that index. This ensures each occurrence is equally likely, so probability is proportional to frequency.

Key Points to Mention

Use of a dynamic array to store all elements, allowing O(1) random access for getRandom.
Hash map from value to a set of indices, enabling O(1) average lookup and removal of indices.
Swap-with-last technique during removal to avoid shifting elements in the array.
Handling edge cases: removing the last element, removing when only one occurrence, and updating indices correctly after swap.
Time complexity analysis: insert O(1), remove O(1) average, getRandom O(1).
Space complexity: O(n) where n is the number of elements.

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