Katkat
Back

Design set with O(1) random access

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates skill in designing a composite data structure that supports average O(1) insertion, deletion, and uniform random access, and tests understanding of hashing, indexing, randomness, and concurrency control.

Design a data structure ("FancySet") that stores unique integers and supports the following operations, each in average O(1) time:

  • add(x): Insert value x if it is not already present. Return whether the insert happened.
  • delete(x): Remove value x if it exists. Return whether a deletion happened.
  • getRandom(): Return a uniformly random element currently in the set.

Requirements / follow-ups:

  • All operations should be average O(1).
  • Handle corner cases such as calling getRandom() on an empty set (define and justify behavior).
  • Discuss how you would make this data structure thread-safe. Compare using a single lock for the whole set vs finer-grained locking (e.g., element-level locks), and explain trade-offs.