5 ms·

I would argue there are many well-qualified frontend engineers who won't correctly solve the two sum problem on their first time encountering it.

user5994461 6y ago
This one? https://leetcode.com/problems/two-sum/ https://leetcode.com/problems/two-sum/ >>> Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Seems trivial enough to me... except if the interviewer forgets the hard constraint that there is exactly one solution, then that's a shitstorm of edge cases. I'd criticize the problem for asking for the positions of the numbers rather than the numbers. That's just super annoying for no reason.
- fractionalhare 6y ago
  Does the problem actually have that constraint? If so then yeah it's significantly easier. I thought the reason you'd have to use a clever algorithm is because a brute-force solution to find all index pairs would require n^2 operations, where n is the size of the input array, because you can't stop after you find a single pair.
  - user5994461 6y ago
    Yes it does, you can open the leetcode and see for yourself. That also explains the "easy" difficulty rating. I guess you've been giving candidates a more hardcode version of the problem, not having that constraint? edit: nevermind, it's the other poster who was giving that problem, not you. No idea how they formulate it in their interviews.
    - fractionalhare 6y ago
      I don't ask candidates these kinds of questions in my interviews. For a coding interview, I'd normally ask them to implement something like backend rate limiting logic for an authentication service, and continually ratchet up the complexity on each successful implementation until the end of the interview. I was asked the two sum problem in an interview once, but I forget if it had this constraint or not. This seems much more reasonable.
      - zebnyc 6y ago
        Forgive me for my ignorance, but are you looking for anything more complex than a leaky bucket algorithm + gossip protocol solution?
  - Viliam1234 6y ago
    Technically, if all values in the array are the same value X, and the target is 2X, you can't do better than O(n^2), because just writing writing all valid solutions is O(n^2). If you can create a new array containing indices to the original array, sort the new array, and use two pointers starting at the beginning and the end of the sorted array to find a solution, it takes O(n×log(n)) time. It is not necessary to assume that the solution is unique, assuming it is okay to simply write one of the possible solutions. If all values are between 1 and k, and you can make a k-sized array, you can find a solution in O(n+k). No matter what you do, you can't get better than O(n). The important thing is that there is more than 99% chance you will never have to solve this problem in your job; and even in the case you would, there is 95% chance that the O(n×log(n)) solution would be acceptable regardless of whether it is the best possible or not.
boomfus 6y ago
If we're being very charitable I guess the idea of using a HashMap for an optimal solution might slip your mind but even a freshman in CS can just loop twice over an array and solve it.
- fractionalhare 6y ago
  I might be misunderstanding the question; how many pairs can there be? You can't just loop over the array twice to find all qualifying pairs of indices, if there are multiple. You'd have to loop over the array n times, where n is the size of the array. Isn't that why the question is difficult? There doesn't seem to be much incentive to using a hash table, complexity wise, if you could just solve it in O(n) time and O(1) space by naively iterating over the array.
  - renewiltord 6y ago
    He meant "write two loops" when he said "loop twice". It seemed obvious to me that he meant that but I can see how if you're used to more unambiguous language it could be confusing. Yeah, you just do it in O(n²) worst case because the problem is O(n²) to find all pairs that match because there can be O(n²) pairs. However he meant one pair here too. Pretty easy to solve. Did it in under 30 s in Python on my broken cellphone. If there are multiple pairs, just replace return with yield.

user5994461 6y ago

This one? https://leetcode.com/problems/two-sum/ https://leetcode.com/problems/two-sum/ >>> Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Seems trivial enough to me... except if the interviewer forgets the hard constraint that there is exactly one solution, then that's a shitstorm of edge cases. I'd criticize the problem for asking for the positions of the numbers rather than the numbers. That's just super annoying for no reason.

fractionalhare 6y ago
Does the problem actually have that constraint? If so then yeah it's significantly easier. I thought the reason you'd have to use a clever algorithm is because a brute-force solution to find all index pairs would require n^2 operations, where n is the size of the input array, because you can't stop after you find a single pair.
- user5994461 6y ago
  Yes it does, you can open the leetcode and see for yourself. That also explains the "easy" difficulty rating. I guess you've been giving candidates a more hardcode version of the problem, not having that constraint? edit: nevermind, it's the other poster who was giving that problem, not you. No idea how they formulate it in their interviews.
  - fractionalhare 6y ago
    I don't ask candidates these kinds of questions in my interviews. For a coding interview, I'd normally ask them to implement something like backend rate limiting logic for an authentication service, and continually ratchet up the complexity on each successful implementation until the end of the interview. I was asked the two sum problem in an interview once, but I forget if it had this constraint or not. This seems much more reasonable.
    - zebnyc 6y ago
      Forgive me for my ignorance, but are you looking for anything more complex than a leaky bucket algorithm + gossip protocol solution?
- Viliam1234 6y ago
  Technically, if all values in the array are the same value X, and the target is 2X, you can't do better than O(n^2), because just writing writing all valid solutions is O(n^2). If you can create a new array containing indices to the original array, sort the new array, and use two pointers starting at the beginning and the end of the sorted array to find a solution, it takes O(n×log(n)) time. It is not necessary to assume that the solution is unique, assuming it is okay to simply write one of the possible solutions. If all values are between 1 and k, and you can make a k-sized array, you can find a solution in O(n+k). No matter what you do, you can't get better than O(n). The important thing is that there is more than 99% chance you will never have to solve this problem in your job; and even in the case you would, there is 95% chance that the O(n×log(n)) solution would be acceptable regardless of whether it is the best possible or not.

boomfus 6y ago

If we're being very charitable I guess the idea of using a HashMap for an optimal solution might slip your mind but even a freshman in CS can just loop twice over an array and solve it.

fractionalhare 6y ago
I might be misunderstanding the question; how many pairs can there be? You can't just loop over the array twice to find all qualifying pairs of indices, if there are multiple. You'd have to loop over the array n times, where n is the size of the array. Isn't that why the question is difficult? There doesn't seem to be much incentive to using a hash table, complexity wise, if you could just solve it in O(n) time and O(1) space by naively iterating over the array.
- renewiltord 6y ago
  He meant "write two loops" when he said "loop twice". It seemed obvious to me that he meant that but I can see how if you're used to more unambiguous language it could be confusing. Yeah, you just do it in O(n²) worst case because the problem is O(n²) to find all pairs that match because there can be O(n²) pairs. However he meant one pair here too. Pretty easy to solve. Did it in under 30 s in Python on my broken cellphone. If there are multiple pairs, just replace return with yield.