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
remove(val) will forward to
Set.remove and return a
boolean indicating whether or not the given value was inside the
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.
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.