← Meta Interview Insights

Meta·Machine Learning Engineer·Technical Phone Screen·Senior

Senior
May 2026

Summary

Meta ML engineer interview with a classic data structures question that sounds deceptively simple but has some real depth to it if you push past the obvious answer.

Questions Asked (1)

Q1

Design a data structure that supports insert, delete, search, and getRandom, all in O(1) time.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

My first instinct was just 'hashmap' and I said it out loud before thinking it through.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Combine a hash map for O(1) search/insert/delete with a dynamic array for O(1) random access. When deleting, swap the target with the last element in the array, update the hash map, then pop the last element. This maintains constant time for all operations.

Pro tip: Mention that this design is used in real systems like Redis for random eviction, and discuss trade-offs such as memory overhead and the need for careful index management during swaps.

1. Clarify requirements and constraints

Confirm that all operations must be O(1) on average, and discuss whether duplicates are allowed or if the data structure should store unique elements.

2. Propose the core data structures

Suggest using a hash map (dictionary) to store element-to-index mappings and a dynamic array (list) to store the elements for random access.

3. Explain insert and search operations

For insert, append to the array and add the element and its index to the hash map. For search, simply check if the element exists in the hash map.

4. Detail the delete operation with swapping

To delete, retrieve the index from the hash map, swap the target element with the last element in the array, update the hash map for the swapped element, then remove the last element from both the array and the hash map.

5. Discuss getRandom and complexity

For getRandom, pick a random index from the array and return the element. Analyze that all operations are O(1) on average, and mention potential edge cases like deleting the last element.

Key Points to Mention

  • Hash map provides O(1) average-time search, insert, and delete by mapping elements to their indices in the array.
  • Dynamic array enables O(1) random access for getRandom.
  • Swap-with-last technique ensures O(1) deletion by avoiding shifting elements.
  • Careful index updates in the hash map after swapping are crucial to maintain correctness.
  • Average-case O(1) time complexity; worst-case for hash map operations can be O(n) but is rare.
  • Space complexity is O(n) due to storing elements in both structures.

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