LeetCode #380 — Insert Delete GetRandom O(1)

Find more useful articles at www.davidseek.com

LeetCode’s challenge of the day on June 12, 2020 (#380) asks us to create an API wrapper around the standard Swift Set implementation. The only given requirement is that all operations must operate in constant time. We will use a Set as underlying data structure because there is no mentioning of duplication and all operations of a Set are constant by default.

insert(val) will forward to Set.insert and return a boolean indicating whether or not the given value has already been present in the underlying Set.

remove(val) will forward to Set.remove and return a boolean indicating whether or not the given value was inside the Set.

getRandom will return a random element from the underlying Set. There is no clear definition of what to return if the Set is empty yet the function declaration is does not return an optional value. So, we'll just return 0. This is a perfect example of missing clarification that you need to address in an interview.

If there is anything unclear or not clearly defined in the question statement, make sure to ask questions. Your interviewer will leave things out intentionally to trigger you to ask questions. The only mistake you can make here is to make assumptions and not be vocal about any uncertainty.

You might be asking yourself, “Why do we need this API wrapper in the first place? We could have just initialized a Set on the calling side and it would eliminate the need for this class to begin with.”

In theory, yes, this is true. Practically, the given RandomizedSet class gives us a clear structure of what is needed. It's easy to test, extend, and maintain. It removes the attributes and functions of the native Set element that we don't need or want in the implementation scope and is a very good practice to conform to.

Follow Up

The tech interview is designed to be a back and forth conversation between interviewer and developer. One possible follow up question could be that the interviewer requests that you implement the class without utilizing a Set. In that case I would suggest a HashMap (dictionary), where key and value are either the same or value is a random placeholder element.

If the question was to be modified to allow duplicates, then the value of the HashMap could indicate the count of each given element.

In that scenario, it’s important to adjust the getRandom function to take the counts into consideration. However, that's out of scope for this question. Let me know in the comments if you have any questions.

Find more useful articles at www.davidseek.com

Software Engineer at Amazon (Alexa Mobile)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store