## Amazon Interview Question for Site Reliability Engineers

Country: United States

Comment hidden because of low score. Click to expand.
9
of 11 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};
and then start with 1 binary search (8-7) in i+1 to n
and so on :)

Comment hidden because of low score. Click to expand.
0

+1

Comment hidden because of low score. Click to expand.
0

can you plz elaborate it more!

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

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={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

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);
}
}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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());
}
}

Comment hidden because of low score. Click to expand.
0

@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!

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

int a;

void sum(int a, 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;
}``````

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";``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

But the question says "pairs" of elements.

Comment hidden because of low score. Click to expand.
0

But the question says "pairs" of elements.

Comment hidden because of low score. Click to expand.
0

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

by firoz

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

by firoz

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

int main ()
{
int ar={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;
}``````

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 count=0;
for(int i=0; i<7; i++)
{
for(int j=i+1; j<7; j++)
{
count++;
cout<<"{"<<givenArray[i]<<","<<givenArray[j]<<"} => index("<<i<<" ,"<<j<<")"<<endl;
}
}
cout<<"count = "<<count;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

{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

Comment hidden because of low score. Click to expand.
0

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

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/>");``````

}

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
~``````

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:

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

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

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.

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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Time: O(n), Space: O(n)

``````public class DistinctPairs {
public static void main(String[] args) {
System.out.println(count(10, 1, 2, 3, 6, 7, 8, 9, 1) == 3);
System.out.println(count(47, 6, 1, 3, 46, 1, 3, 9) == 1);
System.out.println(count(9, 3, 2, 1, 45, 27, 6, 78, 9, 0) == 2);
System.out.println(count(9, 3, 3, 2, 1, 45, 27, 6, 78, 9, 0) == 2);
System.out.println(count(6, 1, 5, 7, -1) == 2);
System.out.println(count(6, 1, 5, 7, -1, 5) == 2);
System.out.println(count(2, 1, 1, 1, 1) == 1);
}

private static int count(int target, int... arr) {
int count = 0;
Set<String> seen = new HashSet<>();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
int k = target - arr[i];
int[] pair = new int[]{k, arr[i]};
Arrays.sort(pair);
String s = Arrays.toString(pair);
if (set.contains(k) && !seen.contains(s)) {
count++;
} else {
}
}
return count;
}
}``````

Comment hidden because of low score. Click to expand.

Name:

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

### Books

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

### 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.