Problem 2: Find stone pair(s)
There are N number of stones, labeled as [0, N-1]. We know the weight of each of those stones. We want to find ONE stone pair, i.e. 2 stones,
whose weight difference is D.
Question A
Formally describe the problem to clearly define the problem without ambiguity. Something like:
write a function F that …
the inputs of the function are …
the output of the function are ….
This question might be harder than you thought. Please think carefully.
Question B
Write the function you described in your answer to question A.
What is the space complexity of your algorithm? What is the time complexity?
Can you achieve O(N) for both time complexity and space complexity? If yes, please implement it.
Write a test program to test your function.
Please list all corner cases you want to test
How to verify the function can process these corner cases correctly? Can you do it in a more systematic way?
Question C (optional)
Same as the original question B, but this time we want to find ALL stone pairs whose weight difference is D. Please note that pair (1, 4) and pair
(4, 1) are considered as the same pair, so only need to return one. Your algorithm’s time complexity should be O(max(R, N)), R is the number of
result pairs, N is the number of stones.