This is one of those tricks you just have to memorize and it's very hard to come up with the solution in 30 min.
What a great way to kick off a professional relationship:
"I know this problem is useless and obviously unrepresentative of the actual work we do. So do you (if you aren't incompetent). You also know perfectly well that I've memorized the answer and am only pretending to 'solve' it for you on the spot. And yet, we go along with the charade and pretend it's a vitally necessary, even clever hiring technique. Because hey, we're getting paid big bucks to play this game, after all. So who cares."
> This is one of those tricks you just have to memorize and it's very hard to come up with the solution in 30 min.
Maybe that particular solution is hard to come up with, but you can solve the problem without any "tricks", just basic principles. I'll try to explain which principles I'd use using python.
You can start with the trivial O(N^2) solution:
def has_2sum(lst, target):
# returns whether there are 2 (not necessarily distinct) elements in `lst` which sum to target
for a in lst:
for b in lst:
if a + b == target: return True
return False
First principle is runtime analysis. The runtime is O(N^2) because the inner loop is O(N) and runs N times. So we can try to speed up the inner loop. Second principle is to rewrite what the inner loop body as a function of the loop variable b.
def has_2sum(lst, target):
for a in lst:
for b in lst:
if b == target - a: return True
return False
Third principle is pattern recognition for common functions: the code is equivalent to
def has_2sum(lst, target):
for a in lst:
return (target - a) in lst
Fourth principle is to know which data structures support membership query. If you thought of hashtables, you get the O(N) solution.
def has_2sum(lst, target):
set_lst = set(lst)
for a in lst:
return (target - a) in set_lst
If you thought of sorted list, you get an O(N log N) solution.
import bisect
def has_2sum(lst, target):
sort(lst)
def contains(x):
# equivalent to `x in lst`
i = bisect.bisect_left(lst, x)
return (0 <= i < len(lst)) and (lst[i] == x)
for a in lst:
return contains(target - a)
To be honest, I had forgotten the O(n) solution and vaguely remembered the nlogn solution. After that experience, I have both solutions lodged in my brain.
Are you talking about determining a pair of numbers in an array that sum to a given value? That's O(n) and just uses a hashset/hashmap.