LinkedIn·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

LinkedIn SWE coding round, pretty much one meaty design-your-own-data-structure problem. The question sounds straightforward until you actually think through the getRandom constraint.

Questions Asked (1)

Design a data structure that supports insert, remove, and getRandom operations all in average O(1) time, where getRandom returns each element with equal probability.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The insert and remove parts felt manageable but getRandom is where it gets tricky.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Combine a dynamic array (for O(1) random access) with a hash map (for O(1) lookup by value). For removal, swap the target element with the last element, update the hash map, then pop the last element. This ensures all operations remain average O(1).

Pro tip: Emphasize that the hash map stores indices, not values, and that swapping with the last element is key to maintaining O(1) removal. Also, mention edge cases like removing the last element or the only element.

1. Clarify requirements and constraints

Confirm that all operations must be average O(1) and that getRandom should return each element with equal probability. Ask about duplicates, null values, and concurrency if relevant.

2. Choose data structures

Select a dynamic array (e.g., ArrayList in Java, list in Python) for O(1) random access and a hash map (e.g., HashMap) for O(1) value-to-index lookup.

3. Design insert operation

Append the new element to the array and record its index in the hash map. If duplicates are allowed, store a set of indices per value.

4. Design remove operation

Look up the index of the element to remove. Swap it 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 hash map entry for the removed value.

5. Design getRandom operation

Generate a random index between 0 and size-1 and return the element at that index from the array. This gives uniform probability.

Key Points to Mention

Use a dynamic array for O(1) random access and a hash map for O(1) lookup.
Swap with the last element during removal to avoid shifting elements.
Update the hash map after swapping to maintain correct indices.
Handle edge cases: removing the last element, removing the only element, and duplicates (if allowed).
Time complexity: insert O(1) amortized, remove O(1) average, getRandom O(1).
Space complexity: O(n) for storing elements and indices.

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