4 ms·

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

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.

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.