## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 5 vote

First Sort -> O(nlogn).
Then start from min end and then find (X-min) which costs O(logn).
In total, the cost will be O(nlogn)

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

correct

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

Can you explain with an example?

If the given array is not an arithmetic progression with common difference of 1 then how will you make sure that the result of X-min is within the array?

Sorted array 1,4,6,7 and X=5
Result: 4,1,-1,-2

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

``````public static void printPairs(int []a,int x){
HashSet<Integer> h= new HashSet<Integer>();
for(int i=0; i < a.length-1; i++){
}
for(int i=0; i < a.length-1; i++){
if(h.contains(x-a[i])){
System.out.println(a[i]+" "+(x-a[i]));
h.remove(x-a[i]);
}
}

}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a={1,2,3,4,5,6,7,8,9};
printPairs(a,9);
}``````

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

There's no need to do 2 loops - one should be enough. Here's C#:

``````public static void FindSumPairs_Hashtable(int[] nums, int target)
{
Dictionary<int, int> ht = new Dictionary<int, int>();

for (int i = 0; i < nums.Length; i++)
{
int factFamily = target - nums[i];

// Add to hashtable, factFamily as key, index as value
if (!ht.ContainsKey(factFamily))
{
}

// In case factFamily is same as current element
// e.g. -5, -4, -6, -3 looking for -10. We should not print (-5,-5)!
if (ht.ContainsKey(nums[i]) && i != ht[nums[i]])
{
Console.WriteLine("Sum {0} found: ({1} + {2}) at indices ({3}, {4})", target, factFamily, nums[i], ht[nums[i]], i);
}
}
}``````

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

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

void printPairs(int a[], int size, int x){
int i;
int low = 0;
int high = size-1;
for(i=0; i < size; i++){
if(a[low] + a[high] == x){
printf("%d %d\n",low,high);
low++;
}
else if(a[low] + a[high] > x)
high--;
else if(a[low] + a[high] < x)
low++;
if(low >= high)
break;
}
}

void main() {
//works for sorter array
int a[]={1,2,3,4,5,6,7,8,9};
printPairs(a,9,7);
}``````

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

A clever way! One improvement: you need to prevent the given value X is twice of one integer in the array.

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

Good catch.. :)
Break should be when low>high instead low>=high.

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

Good catch.. :)
Break should be when low>high instead low>=high.

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

gr8 solution ... but having a hard time following the question and the solution u posted

if a={-3,-2,-1, 1 ,3, 4 ,5 ,7, 11}
and printPairs (a, 9 ,9)

soln isnt suppose to be -->

7 + 3 + -1
7 + 5 + -3
7 + 4 + 1 + -3
...
...
...

Different pairs which sums up to 9

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

anon in the question it says about pair not more then 2 element to be added to produce the result .in your case i hope its an NP complete problem.

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

void pair(int a[], X)
{

int i = a;
int j = a[size-1];

while(i!= j)
{
if(a[i]+a[j] == X)
print (a[i], a[j]);
i++;
j--;
}

}

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

The strategy of Hash Table is used here.
The Key, Value pairs are stored in a hash table.
Consider an unsorted array S[1…n] . (Assuming they are non-negative distinct numbers)
Consider Query x = Sum of two elements in S[]
Algorithm:

``````for i in 1 to length[S]
key[i]=S[i] //Each element in the array when traversed is stored in key
value[i]=x-S[i] //the difference is stored in the value
for k in 1 to i
if(value[i] == key[k]) //finding if any key exists for a value
return(key[k],key[i])``````

The keys “key[k] and key[i]” are the two elements that sum to a query x.
Each step here takes a constant time of Θ(1) for comparing the key and value in the hash table.
Therefore, the Overall accesses in this strategy is given by 𝑻 𝒏 =𝚯(𝒏) .

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.