|
Given an array and a sum value return any two integers that sum upto the sum value.
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Given an array and a sum value return any two integers that sum upto the sum value.
Q:
Microsoft Interview Question for Software Engineer in Tests about Algorithm
:
Given an array and a sum value return any two integers that sum upto the sum value.
A:
1. Sort the array, say in ascending order.
2. Have two references: one to the beginning(left) of the sorted array and one at the end(right).
3. while right > left
3.0 Check if the two add up to the sum.
3.1 If yes, return them.
3.2 Else if their sum is < required sum, increment left.
3.3 else decrement right.
4. If we get out of the above loop, there are no two numbers that add up to sum.
This runs in O(nlogn + n/2) ~ O(nlogn), depending on the sorting method that is used.
(Continued on next question...)
Other Interview Questions
| 