Repeat Code With LeetCode — Insert, Delete, GetRandom O(1)

The series has returned! Yaaaaaay

Photo by Aron Yigin on Unsplash. This picture is a bit of a stretch, but we are asked to create a new container.

Like last time, for the sake of personal pride I will not tell you when this story took place. Maybe it was right after college, making it was during college, and maybe it was last Friday. What matters is that this coding interview took place, and that I did not proceed but learned a lot.

The feedback? They did not give me any, which I find to be a pretty common occurrence with all companies. The interesting thing with this one is that they had a job opening with many required skills I did not possess. They reached out to me first, on LinkedIn, and I wanted the recruiter to be clear on what it was I did, and how it compared to the candidate they were asking for. Then I talked to the manager, who was extremely nice but said that, to be honest, they only had a few hiring positions and were interested in people who had experiences x, y, and z…yet he was going to move me forward, anyway. Maybe they were willing to consider me if I really nailed the coding interview. Maybe they were being honest and just wanted to test their hiring process, while I wanted to take the free interview.

tl;dr I do not know if I failed this coding interview. I may never know. I mean, I probably did. Wait, did I?

Probably

Source

I am disappointed the question above got down-voted so many times because it is exactly how I feel (it was not me, by the way). At the end of the day, I did not finish this coding problem. Many would say that this is all you need to know.

The Problem

LeetCode Insert, Delete, GetRandom O(1)

Difficulty: Medium

Skill Required: Hashmaps, System Design (kind of)

Description: Implement the RandomizedSet class:

• RandomizedSet() Initializes the RandomizedSet object.
• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

First of all, this is an excellent problem. It is not a stereotypical worthless question, it very closely ties to the academic concept of big oh, and it could be characterized as a design question. It is also harder than it may look at first glance. If someone held me at gunpoint and asked me to remove an element from a vector, I would traverse it, find it, remove it, and construct a new vector without it. The trickiest part of this question is removing in O(1).

The interviewer was awesome. He gave me the entire hour, right in the beginning, instead of doing what some interviewers do and coming late, or using up minutes at the beginning. He let me use C++, even though he admitted he had never seen a candidate use it and had not touched C++ in years. He let me know in the middle of the interview that I could use Google, as long as I let him know what it was I was searching.

I offered to use a vector, which I described as a rough ArrayList equivalent, then waffled for ten minutes talking about how to implement the remove operation — I suggested marking the index to remove, and he said this could be problematic. I decided to start coding anyway, after ten minutes of discussion, so that I could build a basic C++ class, add a vector, and implement insert. Then we got back to delete.

I cycled through data structures. I mentioned that this would not be a typical use case of a hashmap — he strongly hinted that a hashmap would help by suggesting that I should not worry about typical use cases. I realized that we could use a hashmap, but treat the keys and the values and the values as the keys (he did not really respond to this — while I think it is correct to say that the values are the keys, it is the indices that are the values).

We talked about how to attain O(1) deletion for a while…probably too long. He eventually just gave me the key, that you can swap the last element with the target element and then pop the vector.

Hiccups

• I tried to use the line if(u1.find(val) != u1.end()) { , which in hindsight was solid. He was confused by it, and that made me question it, but that was my responsibility as someone using a different programming language. Contains would have also worked, but the line is fine and also efficient
• I was trying to use find on an unordered map, which is correct, but I was also trying to traverse it for the second element. This was unnecessary, and also would have been inefficient. Trying to do this really ate up critical minutes
• I needed to make the mental leap to swap the target value with the last value
• While doing this again, in the comfort of my own time (and with YouTube open!), I found one last hiccup that may have prevented me from finishing: My removal was deleting from the map, but I also needed to update the hashmap at the end value

The Solution

PrintVector is not strictly necessary. Find this on my personal GitHub here

The hardest I have ever been roasted on this account was by a user named Cziffra7…I have not heard from him since, and as far as I can tell he has no articles and barely has a presence at all (almost as if he made the account exclusively to make fun of my article), but…I am kind of curious what he would have to say about the code above.

We can make the unordered map and vector private, but I don’t personally think this is a huge deal (others may). The print method is optional, but I thought it helped in debugging. getRandom? I don’t know if it would get the StackOverflow stamp of approval, but it’s the most straightforward way to obtain a random number and was based on a YouTube video I will link below.

Insert is fairly straightforward, as is getRandom. Remove consists of two little tricks. First, every time we insert we are keeping track via an unordered map that essentially maps values to indices. This is for the access a hashmap provides — now when we want to remove something, we can retrieve its index in O(1). The “swap” in this problem prevents us from having to take an element out in linear fashion.

It’s all explained a lot less confusingly in the video below, another gem.

Closing Thoughts

If you look at the GitHub, you will notice I put this up back in January. I have a full final round of interviews I’ve been meaning to dissect, and it’s been quite a while — one was a variation of TwoSum, but did not map to a LeetCode problem; I would estimate that if it were, it would be a LeetCode medium because it is a little harder than TwoSum itself. One was a lot more interesting, and asked me to interpret a lot of code on the fly…I thought I did fine, but unfortunately I did not.

Then there was a frontend interview at another company in which they actually gave me a functional bit of JavaScript/HTML/CSS that did not employ any frontend frameworks. I never figured that one out, but I should because it’s one of the most fair interviews I ever received.

Anyway, terrible segue, but I was having a look at this:

I got kind of obsessed with these. The amenities. The free food. The look and feel of one of those expensive colleges you don’t realize you can’t afford until after you’re done, only in this case you do not have to pay back any of it.

One thing I like about the video above is that she actually codes and talks about it. I find that a lot of them gloss over this, so they may as well be financial planners, or product managers, or professional bloggers…

I think just being able to code like this should be a point of pride in and of itself…unless cziffra7 comes out of the woodwork and dumps on it. Look, we used a hashmap. A vector. We took advantage of a neat technique to attain O(1) operations. That requires some degree of talent, as did coming up with elements of it during a real interview on a problem we had never seen before. Maybe you’re better suited, and would have solved it all perfectly on the first try.

At the end of the day, at least it’s code. Real code.