6 ms·

> I actually got stuck at an interview because I forgot the nlogn solution for two sums. Absurd! Are you talking about determining a pair of numbers in an arra

> I actually got stuck at an interview because I forgot the nlogn solution for two sums. Absurd! 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.

nouveaux 5y ago
No. Sort the array. Then use two indexes, one on each side of the array. Increment indexes to meet in the middle. 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.
- yes_really 5y ago
  But why didn't you use the O(n) solution instead of the O(n log n) solution?
  - nouveaux 5y ago
    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.
  - wombat-man 5y ago
    I suppose if you had to optimize for least space used sorting in place and doing it they way they suggested would be best.
- akhmatova 5y ago
  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."
- zodiac 5y ago
  > 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) If you thought of `sortedcontainers.SortedList` (a third-party python package), you get an O(N^4/3) solution (analysis: https://grantjenks.com/docs/sortedcontainers/performance-scale.html https://grantjenks.com/docs/sortedcontainers/performance-sca...)

nouveaux 5y ago

No. Sort the array. Then use two indexes, one on each side of the array. Increment indexes to meet in the middle. 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.

yes_really 5y ago
But why didn't you use the O(n) solution instead of the O(n log n) solution?
- nouveaux 5y ago
  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.
- wombat-man 5y ago
  I suppose if you had to optimize for least space used sorting in place and doing it they way they suggested would be best.
akhmatova 5y ago
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."
zodiac 5y ago
> 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) If you thought of `sortedcontainers.SortedList` (a third-party python package), you get an O(N^4/3) solution (analysis: https://grantjenks.com/docs/sortedcontainers/performance-scale.html https://grantjenks.com/docs/sortedcontainers/performance-sca...)