Amazon Interview Question Software Engineer / Developers
We do not have the 3rd number , thats one of the numbers we need to find !!
So how can you find the two numbers so that they add up to (k-3rd number)
How do you decide which pointer to increment/decrement? I'm just curious to know how to solve the sum-of-two problem in linear time even with a sorted array.
Yes, I too think that is the core of the solution. Once you sort it (keeping track of index) in O(nlogn) time, you can have two pointers moving from first to last and last to first and look for a third number in O(logn) but how to decide which pointer to increase or decrease? Lets say i and j are the indexes which move from first to last and last to first respectively. At any instant,
d = S - a[i] - a[j]
Then, the index movements can be as follows:
int k;
if (d < a[i])
j--;
else if (d > a[j])
i++;
else if (-1 != (k = binarySearch(d, a, i, j)))
return the indexes;
else
??? What happens here? Which index to move, i or j?
@Kaka
As i understand from the question it says "find the three indexes".If you will sort the array then you would loose the original index of array.I think we should do it without sorting the array.
Huh?
Why would you lose the index? Just keep the original index along when you move the elements.
For instance:
Instead of int array, have a pair array where pair is two ints, the value and the index in the original array.
There are no space limitations so using an extra pairs array and sorting that is allowed.
package com;
import java.util.HashSet;
import java.util.Set;
public class General {
static void threesum(int arr[],int sum){
int a,b,c;
a=b=c=0;
for (int i=0;i<arr.length;i++){
a=arr[i];
for(b=i+1;b<arr.length;b++){
for(c=b+1;c<arr.length;c++){
if(a+arr[b]+arr[c]==sum)
{System.out.println("Indexes are :"+i+":"+b+":"+c);return;}
else if(a+arr[b]+arr[c] > sum)
break;
}
}
}
}
public static void main(String[] args) {
int arr[]={1, 3, 4, 5, 8, 13, 17};
threesum(arr,25);
}
}
a slight variation of 3sum problem.. find two numbers such that their sum is equal to k-(3rd number).. a simple O(n^2) solution exists.. first sort the array,then starting from last, for each element try to find 2 numbers..this can be done in O(n) if we put two pointers and increment or decrement one of them depending on comparision of their sum with the number
- kaka September 17, 2008