Amazon Interview Question Site Reliability Engineers


Country: United States


Comment hidden because of low score. Click to expand.
7
of 9 vote

You can do this in O(nlogn) time complexity.
First sort the elements [O(nlogn)]
now start from the very first element and binary search (sum-firstelement) in i+1 to n.can be done in logn
Do so for every other number.
Overall time comlexity is still O(nlogn)

Example:
a={3,2,5,1,8,0} sum to be want 8
Sorted array={0,1,2,3,5,8};
start with 0 and binary search (8-0=8) in i+1 to n
and then start with 1 binary search (8-7) in i+1 to n
and so on :)

- Deven Bhooshan on July 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1

- mahi on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you plz elaborate it more!

- softy on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This approach will return the same pair multiple times. The question asks for unique pairs. You need some way of knowing which values have already been used. Maybe a bit-vector.

- pws on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To solve the problem of duplicate pairs, for the pair of ith element do binary search from i+1 to N.

- Aashish on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry i forgot to mention that you have to search only in i+1 to n elements . I have edited the answer.

- Deven Bhooshan on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cool, but what if there are duplicated values in the input?
eg., input = {2, 2, 6}, and desired sum is 8. the algorithm would return the pair (2, 6) twice.

- pws on July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

While iterating the element you just have to chek the adjacent element. If the element is same then just increment the pointer to the next location.

- subrata on July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if we have already sorted the array . then why we need to do binary search then ??. can't we linearly move from front and back.

- singhsourabh90 on July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Well, the question needs to be clarified a lot.
1. Are the elements given in the range? If yes, use look up table.
2. else, do sort the array in nlogn, remove duplicates & find the pairs by running the two pointers, low[=0] & high[=n-1].
3. Are the pairs {2,6} & {6,2} considered the same?

Below code is based on: 1 & 3

void findPair(int* a,int n,int k)
{
        int hash[10]={0},i;
        for(i=0;i<n;i++)
        {
                if(!hash[a[i]])
                {
                        if(hash[k-a[i]])
                                printf("%d %d\n",a[i],k-a[i]);
                        else
                                hash[a[i]]=1;
                }
        }
}

complete code here: ideone.com/17w1Z

- Aashish on July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.HashMap;

public class GetPairValue {

void findPair(int Sum)
{
HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
int[] a={2,4,6,4,7};
for(int i=0;i<5;i++)
{
if(hm.get(a[i])==null)
{
hm.put(a[i], Sum-a[i]);
}
}
System.out.println(hm);
for(int i=0;i<5;i++)
{
if(hm.get(a[i])!=null && hm.get(hm.get(a[i]))!=null)
{
System.out.println("Pair Values are : "+a[i]+" "+hm.get(a[i]));
hm.remove(a[i]);
hm.remove(Sum-a[i]);
}
}
}

public static void main(String str[])
{
GetPairValue gpv=new GetPairValue();
gpv.findPair(8);
}
}

- apandey846 on July 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Note that this is done in O(n)...!

- apandey846 on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

is it necessary to do two traverse?
public void findUniquePairSumToN(int n) {
Map<Integer, Integer> table = new HashMap<Integer, Integer>();
for (int a : array) {
if (table.containsKey(n - a)) continue;
table.put(a, n - a);
}
for (Map.Entry<Integer, Integer> entry : table.entrySet()) {
System.out.println("Pair: " + entry.getKey() + " " + entry.getValue());
}
}

- gfan on July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@gfan: in your code, you will put n-a that is possibly not in the array to the map...e.g. a={2,4,6,4,7}, the output will be {(2,6),(4,4),(7,1)}... (7,1) should not be in the answer!

- emma.wang on July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<stdio.h>
#include<stdlib.h>

int a[10];

void sum(int a[10], int i, int j, int n, int s)
{
     if(i == n)
         return;
     if(j == n)
          return sum(a, i+1, 0, n, s);
     if(s == a[i] + a[j] && i != j)
     {
          printf("\n\nPairs are {%d and %d}\n\n", a[i], a[j]);
          a[j] = -5000; //---- Just to avoid the repetative pairs. Example: (2,4) and (4, 2). 
          sum(a, i+1, 0, n, s);
     }
     else        
         sum(a, i, j+1, n, s);
}
          

int main()
{
    int i, n, s;
    printf("\nEnter the number of elements\n");
    scanf("%d", &n);
    printf("\nEnter the sum\n");
    scanf("%d", &s);
    printf("\nEnter the elements\n");
    for(i = 0; i < n; i++)
          scanf("%d", &a[i]);
          
    sum(a, 0, 1, n, s);
    system("pause");
    return 0;
}

- Anonymous on July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int array[]={10,20,30,40,50,60,70,80};
	n=8;
	cout<<" \n\nEnter the value :";
	cin>>val;
	int flag=0;
	i=0,j=n-1;
	while(i<j)
	{
		if(array[i]+array[j]==val)
		{
			cout<<"\n"<<array[i]<<" + "<<array[j]<<" = "<<val;
			flag=1;
			i++;
			j--;
		}
		else if(array[i]+array[j]>val)
			j--;
		else
			i++;
	}
	if(flag==0)
			cout<<"\nNo such elements";

- varun on July 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I tihnk it is not necessary that only two elements will sum up to the given sum S.isnt it??

- softy on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But the question says "pairs" of elements.

- Anonymous on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But the question says "pairs" of elements.

- Anonymous on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are (2,6) and (6,2) different ?

by firoz

- Anonymous on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry i mis read this question works for the given input but fails for this input array :
array[]={2,5,3,4,6,1};

I think it cant be done in O(n) , you have to take two loops .

see this : ideone.com/TVwTX

- softy on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your algo is expecting numbers in sorted order and unique elements in the list. take this example and solve it { 2,4,6,2,4,6}

- KrishKrish on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you have to sort your array first. so time complexity will be O(nlgn).
it can be done using hashing in O(n).

- kunal.id89 on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Don't think hashing is a good idea, since no range for numbers is mentioned......Can end up using lots of space.....

- Water on July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

but i dont think we have any other method to do in linear time..

- kunal.id89 on July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are (2,6) and (6,2) different ?

by firoz

- Anonymous on July 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't be . as in both cases S=8.

- Abhishek on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No.. (2,6) and (6,2) are considered as same..

- Anonymous on July 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <map>
using namespace std;

int main ()
{
  int ar[10]={2,3,7,6,4,5,0,1,2,8};
  map<int,int> mymap;
  map<int,int>::iterator it;
for(int i=0;i<10;i++)
{
 int a = ar[i];
 mymap[a]=a;
}
  // show content:
  
  //12+25 = 37
  int sum = 4;
  for ( it=mymap.begin() ; it != mymap.end(); it++ )
   { 
   int x = sum-(*it).first;
   if(mymap[x])
   {cout << (*it).first << "and" << mymap[x] << endl; }
    }
  getchar();
  return 0;
}

- saurabh(vit) on July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;
int main()
{
	int givenArray[] = {7,2,4,6,4,6,1};
	int answer = 8;
	int count=0;
	for(int i=0; i<7; i++)
	{
		for(int j=i+1; j<7; j++)
		{
			count++;
			if(givenArray[i]+givenArray[j] == answer)
				cout<<"{"<<givenArray[i]<<","<<givenArray[j]<<"} => index("<<i<<" ,"<<j<<")"<<endl;
		}
	}
	cout<<"count = "<<count;
	return 0;
}

- NlogN on July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Answer is:=>
{7,1} => index(0 ,6)
{2,6} => index(1 ,3)
{2,6} => index(1 ,5)
{4,4} => index(2 ,4)
count = 21
The complexity is n logn and here index does matter so pairs (2,6) at 1,3 is different then pairs of (2,6) at 1,5

- Anonymous on July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity will be O(n^2), since none of your loops are being shortened by a factor of two (or any other log base)

- Sameer on July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Array.prototype.unique = function(){
   var arr = this, new_arr = [];
   console.log(arr)
    for(var i=0 ; i<arr.length; i++){
        if(new_arr.indexOf(arr[i])===-1){
           new_arr.push(arr[i]);
        }
    }
   return new_arr;
}

function pair(array/*array*/,sum/*int*/){
    var result = {}, i=0, temp;
    /*preprocessing*/
    array = array.unique();
    console.log(array)
    while(i<array.length){
           temp = sum - parseInt(array[i]);
        if(array.slice(i).indexOf(temp)!=-1){
           result[array[i]] = temp;
        }
        i++;
    }
    
    return result;
}
    
    
    var array = [2,4,6,4,3,6,7,9,4,8,2,7,1];
    var sum = 10;
    
    var obj = pair(array,sum);
    for(var i in obj){
        document.write(i+" : "+obj[i]+"<br/>");

}

- zhujy8833 on July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def get_pairs(l, n):
    l = sorted(l)
    i = 0
    j = len(l)-1
    while i < j:
        if l[i] + l[j] < n:
            ii = i
            while i < j and l[ii] == l[i]: i+=1
        elif l[i] + l[j] > n:
            jj = j
            while j > i and l[jj] == l[j]: j-=1
        else:
            print l[i], " ", l[j]
            while i+1 < j and l[i+1] == l[i]: i+=1
            i += 1
~

- diaosi on July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_unique_pairs(array, S): 
    values = set(array)
    result = set()
    for value in values:
        pair = S - value
        if pair in values and pair not in result:
            result.add(value)

    return [(value, S - value) for value in result]

print find_unique_pairs([2, 4, 6, 4, 6], 8)

- llvllatrix on July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It's easy to achieve O(n) by using Hash table. Travel the array from a1 to an, find whether there is sum-ai in Hash table. Then, put each element in Hash table if and only if it is not in hash table, unless the value is equal to sum/2.

- LoocalVinci on September 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

HashMap approach. The only "cool" thing is I didn't use extra data structure to prevent from printing duplicate pairs. The embedded comment should be clear on how I am using the hashmap alone to prevent printing duplicate pairs.

static void findPairs(int[] arr, int sum) {
  HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
  for(int i : arr) {
    int j = sum-i;
    // suppose sum=8 and i=6, then j=2
    // we want to check whether j=2 is already in the map and whether
    // the value is false (indicating we haven't printed it yet)
    // furthermore, we want to check whether i=6 is in the map because
    // if so, then this pair must have been printed as well
    // exception is when i=j, such as i=4 and j=4
    if(map.containsKey(j) && !map.get(j)) {
      if(i == j || !map.containsKey(i)) {
        System.out.println("" + j + "+" + i);
        map.put(i, true);
        map.put(j, true);
      }
    } else {
      map.put(i, false);
    }
  }
}

- Sunny on December 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More