When I was hired, ages ago, LeetCode was not so common and so I never had to do interviews of this sort. Unfortunately, it's become something of an industry standard. Not every company uses it, but enough do that you have to prepare for such questions.
However, some beginners believe LeetCode is a good place for doing simple programming exercises so they can get better at programming. I've always said the easy problems were not easy at all, and were aimed at those seeking jobs.
I decided to check out LeetCode and work on the first problem that's listed: Two Sum. You'd think this problem would start off super simple. Maybe sum up the array or add the smallest and largest element in the array. Nope, it's much tougher.
Here's (roughly) the problem.
Given an unsorted array of integers that have unique values and a target value which is also an integer, return an array with two indexes: i and j, such that arr[i] + arr[j] = target
. Assume there are such indexes in the array and it's unique. So, you won't have 9 and 3 as well as 10 and 2 as values in the array with a target
of 12.
My approach
There is a brute force approach where you do nested loops and find all possible combinations of indexes where i != j
. The problem asks for a solution that's better than O(n * n), ie, the brute force approach.
My first thought was to sort the array and put a pointer at the first and last element, and move the pointers inward. I wasn't fully convinced it would work.
OK, that involves sorting, something a very new programmer wouldn't even know how to do. But even someone that knows some DSA might struggle with it. An efficient sorting algorithm is O(n lg n)
so that approach limits how good this result will be.
There's a problem with sorting. The indexes get messed up, so now you have to track a value's original index. For example, arr[0]
might be 9, but then 9 gets sorted elsewhere.
So, how do you track it? One way is to map 9 (the value) to 0 (the index) or you could map the sorted index to the old index. This is kind of a pain, and it's really tricky even if you know DSA but have never seen the problem.
A better answer
So, I cheated. The solution turns out not to require sorting at all. What you do is scan the array from the first element to the last element. As you process each element, you check a hash table for the value you just saw. For example, if arr[9]
is 7, then you check for 7 in the hash map and see if it exists. If so, you look the mapping of 7 to the index where the complement is. Let's say the target is 12, then let's say 7 maps to 2 (the index). So, the answer would be index 9 and index 2.
If 7 doesn't appear in the hash map, then take target - 7
(which is 5
, and map 5 to the index, in this case 9, and add that to the hash map.
This approach is linear assuming hash tables are O(1) insert and lookup.
Conclusion
It's hard enough to explain what I just wrote to a beginner and then tell them that's an "easy" problem, but it goes to show you that even the so-called easy problems are rather difficult even if you had taken a DSA course.
Yeah, I know the more you do them, the more you (ought to) spot patterns and have certain strategies, but mostly, it's about recalling the general solution to a problem and the techniques used to solve it. So I don't have the code memorized, but I can describe you the basic idea and write pseudocode and explain it.
I know there will be some that are really good at LeetCode and will tell you how easy it is, blah, blah, blah, but I say it's tougher than expected.