Amazon Interview Question
Software Engineer / DevelopersCountry: United States
May be there can't be any such solution, with less than O(n) worst case complexity.
Lets see...
suppose someone proposes an algo. which does this in sublinear time, that means
that algorithm will not look at every element, and it is theoretically possible to put those two elements at those positions which is not looked by that algorithm.
Hence looking at every element is necessary in worst case. So we need O(n) time.
But there is a catch, since the array is ordered, there may be a algorithm which does not literally looks at every element but takes advantage of this information about ordering of elements, And thus i think it may be possible to have such algorithm. Although I am not sure.
What I tried ,
take first element of the array, call it "x", now binary search for largest element less equal than (Sum - x). if the sum of those elements is Sum, then we have the answer.
Otherwise, Take second element of array. call it "y", now binary search (Sum - y) in the new limited range. But i guess the time complexity is not better than O(n).
Thanks.
Yeah I think that is the case here.
We can improve the constant factor by doing something like this.
a=Largest number
b=2nd largest
c= smallest
d=2nd smallest
if X > a+b || X< c
there is no combination.
This just improves the constant but still it is of same complexity
The above algorithm can be further optimized. Take first element, binary search the position where the other one should be to make the sum. If it exists return it. If not, take the smaller number on that position (if say the number u need to make the sum is 8, but u find that there are only 7 and 9 - u should take 7 now). Now do a recursion swapping the numbers. The output number should be the pivot, and find a higher index in the top part of the array where you expect the sum to be. Keep swapping and recur until you find the sum or end up with only two numbers.
This will always reduce the set in half. Thus it is log n. The above algorithm goes sequentially on one side which cannot be less than linear complexity. This algorithm will binary search on both sides.
example:
findSum(new int[]{1,3,5,10,11,15,25,36,50},35);
first iteration: pivot=1, expected 34
binary searched between 3 to 50 we found 25,36 position but no 34
next iteration: pivot=25, expected 10
binary searched between 3 to 15 and found 10
void sumX(int *a,int n,int x)
{
int p1=0;//first elem
int p2=n;//last elem
while(p2>p1)
{
int sum=a[p1]+a[p2];
if(sum<x)p1++;
elseif(sum>x)p2--;
else
cout<<a[p1] <<" "<<a[p2];
}
Hi All, I wrote this O(n) program in Java. I didn't find any solution that is less than this.
public class SortedArrayPairSum {
public static void main(String [] args) {
List<Integer> sortedArray = Lists.newArrayList(1, 5, 10, 12, 30, 60);
int sumExpected = 42;
int frontPointer = 0;
int backPointer = sortedArray.size() - 1;
while (frontPointer < backPointer) {
int actualSum = sortedArray.get(frontPointer) + sortedArray.get(backPointer);
if(actualSum < sumExpected) {
frontPointer++;
}
else if(actualSum > sumExpected) {
backPointer--;
}
else {
System.out.println("Pair=(" + sortedArray.get(frontPointer)+","+ sortedArray.get(backPointer) + ") Sum=" + actualSum);
break;
}
}
}
}
May be u can use binary search algorithm like solution, you will check with the middle number with the sumexpected. Or find the number first which is smalles that sumexpcted and it next successive number in the sequence is greater that sumexpcted so that it will reduce the array boundry for finding the sum of tow number. In above example, incase of putting end index to 60, keep it to 30 and then start the sum algorithm you are using. This will give you worst case as N but best case can be N/2
class Node
{
public Node right;
public Node left;
public int value;
}
public class bettersum
{
public static int findhalf(int[] arg,int sum)
{
int i=0;
int j=arg.length;
int half=sum/2;
int output=0;
for(int k=i;k<j;k++)
if(arg[k]>half)
{
output=k-1;
break;
}
return output;
}
public static Node initializeBST(int[] arg,int middle)
{
int length=arg.length;
Node root=new Node();
Node temp=new Node();
temp=root;
for(int i=middle;i>=0;i--)
{
initialsingleleft(temp,arg[i]);
temp=temp.left;
}
root.right=new Node();
temp=root.right;
for(int i=middle+1;i<length;i++)
{
initialsingleright(temp,arg[i]);
temp=temp.right;
}
return root;
}
public static void findsum(Node root,int sum,int middle,int length)
{
Node temp= root.left;
Node temp1=root;
for(int i=middle;i<=length;i++)
{
for(int j=middle-1;j>=0;j--)
{
if(temp.value+temp1.value>sum)
{
temp=temp.left;
}
else if(temp.value+temp1.value==sum)
{
System.out.println(" "+temp.value+" "+ temp1.value);
break;
}
else
{
break;
}
}
temp1=temp1.right;
temp=root.left;
}
}
public static void initialsingleright(Node node, int value)
{
node.value=value;
node.right=new Node();
}
public static void initialsingleleft(Node node,int value)
{
node.value=value;
node.left=new Node();
}
public static void main(String args[])
{
int [] a ={1,2,3,4,5,6,7,8};
int sum =8;
int middle=findhalf(a,sum);
findsum(initializeBST(a,middle),sum,middle,a.length);
}
}
public static void FindTwoNumbers(int[] arr,int X)
{
Hashtable ht = new Hashtable();
//let number's be x and y
//X-arr[i]=y..is the same as X=arr[i]+y.
//So we can store the arr[i] in a hashtable and iterate through the array.
for(int i=0;i<arr.Length;i++)
{
if(ht.ContainsKey(X-arr[i]))
{
ht[X - arr[i]] = arr[i];
}
else
{
ht.Add(arr[i],"");
}
}
foreach (var obj in ht.Keys)
{
if(ht[obj].ToString().Length!=0)
{
Console.WriteLine(obj.ToString() + "," + ht[obj].ToString());
}
}
}
Explanation for above code
{1,2,3,4,5}....let us say we are searching for 7
so, 7-1=6, we lookup 6 in hastable, if it is found we have a pair otherwise we add 1
7-2=5, not there in hashtable, so add 2 to hash
7-3=4 hashtable now contains {1,2,3}
7-4=3, is 3 present in hastable,yay! we have a pair
7-5=2, is 2 present in hastable, yes wo we have another pair
Explanation for above code
{1,2,3,4,5}....let us say we are searching for 7
so, 7-1=6, we lookup 6 in hastable, if it is found we have a pair otherwise we add 1
7-2=5, not there in hashtable, so add 2 to hash
7-3=4 hashtable now contains {1,2,3}
7-4=3, is 3 present in hastable,yay! we have a pair
7-5=2, is 2 present in hastable, yes wo we have another pair
as arrays are sorted use binary serach for finding ( X-array1[i]) in array2
- Encoder April 06, 2012