The algorithm puzzle in this post is an extension of a simple interview question I used to ask some candidates (who wanted to do their coding in C/C++), when I was at Microsoft.
The question started off simply:
Given an array of integers, you want to find out if the sum of all the numbers in that array is S. Write a C/C++ method to do it.
Most candidates would squint at me, probably thinking, is this for real? Once they had it written down, I would ask them the follow up question: Could this give wrong answers?
The answer is yes: the integer addition could overflow, and could give wrong answers.
To rectify that, some candidates would suggest using floats/doubles etc. Then the discussion would go on about how one could implement big integers, coming up with some test-cases etc.
Anyway, here is the puzzle.
Given n numbers in the range [-M,M], and a target sum S, also in the range [-M, M], can you figure out in O(n) time, whether those n numbers add up to S, while keeping all your computations within the [-M, M] range? (M is unknown to you). Assume arithmetic operations are O(1).
The question started off simply:
Given an array of integers, you want to find out if the sum of all the numbers in that array is S. Write a C/C++ method to do it.
Most candidates would squint at me, probably thinking, is this for real? Once they had it written down, I would ask them the follow up question: Could this give wrong answers?
The answer is yes: the integer addition could overflow, and could give wrong answers.
To rectify that, some candidates would suggest using floats/doubles etc. Then the discussion would go on about how one could implement big integers, coming up with some test-cases etc.
Anyway, here is the puzzle.
Given n numbers in the range [-M,M], and a target sum S, also in the range [-M, M], can you figure out in O(n) time, whether those n numbers add up to S, while keeping all your computations within the [-M, M] range? (M is unknown to you). Assume arithmetic operations are O(1).
[Solution]
No comments:
Post a Comment