Repeat Code With LeetCode — Contains Duplicate
Guess what? It’s another…spoiler…hashmap problem
This is the first warm-up problem in Grokking The Coding Interview, and it is a LeetCode easy. There are some easy LeetCode questions that I think make good practice because of the techniques they require, but this is not one of them — it’s more or less a repeat of the anagrams question, which I have already covered. It is still useful if you have never solved a hashmap problem before.
Grokking The Coding Interview deserves some discussion, but things are getting kind of murky. Once upon a time, DesignGurus and Educative content all fell under the Educative.io umbrella, so for a flat fee you had access to Grokking The Coding Interview, Grokking The System Design Interview, and a wide variety of other Educative.io content that consisted of everything from Docker to Elixir. Now DesignGurus and Educative are separate entities (the creator confirmed it on Reddit here) and for some reason Educative is rolling out their own similarly-worded content, like Grokking The MODERN System Design Interview.
None of the above was an affiliate link, and I have no intention of asking for one anytime soon. It is all just too confusing, and I do not want to gripe about what Educative.io did because I am missing critical context. For all I know, the two parted on amiable terms.
What this means for you, the reader, is that you have the option to buy lifetime subscriptions to DesignGurus courses like Grokking The Coding Interview, monthly subscriptions to DesignGurus, or monthly subscriptions to Educative.io to try out their more varied content. I personally think the lifetime subscription is the best option, but I have no idea what the legal ramifications would be if DesignGurus were ever to retire (would we lose website access)? Plus, these are a lot of paid resources. Not every software engineer intern, computer science undergrad, and self-taught developer has access to all of these things, especially if on top of that they are considering LeetCode Premium.
Some Free Resources:
- Blind75
- Grind75, something Yangshun Tay himself wrote to me about. He said the list is much better, but I don’t know if it ever caught on the same way Blind75 did
- NeetCode covers all 75 questions on YouTube
- A mapping someone made of all Cracking The Coding Interview questions to LeetCode. I never used this, and as far as I know Smack never did either, but we still both really like the list because it probably comes closest to actually matching fundamental data structures and algorithms problems
The fundamental idea here is that regardless of what list you choose, you are probably better off learning patterns than trying to do every LeetCode problem.
Question
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Difficulty: Easy
Skills Required: Sorting (depending on implementation), hashmaps (depending on implementation)
Trivia: This is the first warm-up question in Grokking The Coding Interview
Solution
Here is how I imagine the thought process is supposed to go
Interviewer: Given an integer array nums, return true if any value appears at least twice in the array , and return false if every element is distinct
Candidate: Well, kind interviewer, I suppose I could use brute force. Compare every element to every other element. If we obtain a match at any point, then there is indeed a duplicate
Interviewer: That would be fine, but I am interviewing 18 other applicants. Can you do better?
Candidate: Well I suppose sorting the list would be O(n log n), so perhaps we can use a hashmap?
Interviewer: That will pass, but just so you know eight other candidates already did the same thing. If you do this correctly you will still have a system design interview, a behavioral interview, a take-home challenge, an HR challenge, and a 500-word essay
Candidate: What?
Interviewer: What?
This is C++. You also can solve the problem with std::sort, but a hashmap is better with a time complexity of O(n) (someone else’s explanation and code is here).
Below is the best explanation of a hash table, which is very close to a hashmap with some caveats
I use an unordered_map, which is another close approximation. Here is a definition:
A hash table is a data structure that is used to store keys/value pairs. It uses a hash function to compute an index into an array in which an element will be inserted or searched. By using a good hash function, hashing can work well. Under reasonable assumptions, the average time required to search for an element in a hash table is O(1)
— -Source
I admit that the line
u1[nums[i]]++
is confusing, I have just written it so many times that I have gotten used to it. The for loop is just a way to get counts. We are populating the unordered_map with key/value pairs, where each key is a number and each value is the number of times that number has appeared. At the end we see if anyone has a count greater than or equal to 2.
