Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
bool FindNumbers(std::vector<int>& A, int sum, int& num1, int& num2)
{
// if don't want to use extra space
// then sort vector using std::sort
// and use binary search below in loop instead of find
std::set<int> s(A.begin(), A.end());
for each(int x in A)
{
int y = sum - x;
// vector::
std::set<int>::iterator it = s.find(y);
if ( it == s.end())
continue;
num1 = x;
num2 = *it;
return true;
}
return false;
}
public static boolean findSum2(int[] a, int sum) {
if (a.length == 0) {
return false;
}
Arrays.sort(a);
int i = 0;
int j = a.length - 1;
while (i < j) {
int tmp = a[i] + a[j];
if (tmp == sum) {
System.out.println(a[i] + "+" + a[j] + "=" + sum);
return true;
} else if (tmp > sum) {
j--;
} else {
i++;
}
}
return false;
}
This can also be solved in order of n by using a boolean array of length equal to highest number in the input list..
iterate through each number and:
1. set the flag of that location (the current number) in bool array to "true".
2. subtract this number from the sum.
3. check on the location of the result of step 2, to see if it is a true.
- if yes, we have found the pair, exit.
- if no, continue iterating
(1) First find the smallest no. in the array.
(2) add it to every element in the array.
(3) add it to the sum to be found also. i.e let sum += (2 * smallest)
(4) Construct a dictionary (dict) with elements as keys.
(5) Iterate through the array as follows:
for i = 1:length(a)
{
tsum = sum - a[i];
if(tsum > 0 && dict[tsum].exists())
{
print a[i] - smallest;
print tsum - smallest;
}
dict[a[i]] = true;
}
Steps:
1) Sort the array in nlog(n) time.
2) If sum of first and last element is == given number. Bingo !!
3) Else if sum is greater, do sum of first and second last element and check.
4) Else if sum is less, do sum of second and last element and check.
Repeat step 3 and 4 until you find the given sum OR the given number lies between the sum of previous computation and present computation, in that case sum does not exists. :)
Again with format
- Gerry September 09, 2011