## Amazon Interview Question for Development Support Engineers

• 0

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

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

for (int i = 0; i < arr.length; i++) {
int currValue = arr[i];
if (!map.containsKey(currValue)) {
int diffValue = sum - currValue;
if (!map.containsKey(diffValue)) {
continue;
}
map.put(currValue, diffValue);
}
}

print(map);

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

Simple and good solution :-)

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

first sort the array using quick sort.. And then add up each pair of elements starring from first element of the array till sum doesn't exceed given value..
Complexity would be O(n logn)

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

@abhi : can you explain your logic

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

(1) First Sort the elements
(2a) use 2 pointers 'first' at first element and 'last' at last element in array.
(2b) while(last<first){
sum = array[first] + array[last]
if (sum < inputValue) first++;
else if (sum > inputValue) last --;
else { print f and l; BREAK while loop} //case when equal

Can also be done using recurrsion just make sure you take care when recursion stack opens. This solution breaks when first sum is found, if there are more pairs dont break and keep storing the first and last values. Example 1,3,3,4,5 and inputValue=6 will be matched by 1+5 and 3+3

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

Sort the array.
Take every element from the starting index, do a Binary Search for (Sum - CurrentNumber) on the rest of the array.

So, its N Log N + N/2 Log N

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

Use a hash map. It should store the sum for each value in the form of a linked list
Ex : 1,2,3,4,5
1->3(2)->4(3)->5(4)->6(5)
2->5(3) -> 6(4)->7(5)
3->7(4)->8(5)
4->9(5)
5
Here,1->6(5) indicates when 5 is added to 1, 6 is obtained .

While calculating the sum, if it is same as the given value then we have found the pair. This takes O(n)

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

Can you please tell how this is O(n). For every element you are adding to the remaining elements, right? so it O(n2), please correct me if i'm wrong.

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

indeed this is o(n^2)

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

``````for(i=0; i<n; i++)
{
// Search for (x-a[i]) in the rest of the array using Binary search
if(binary_search(a,(x-a[i]),0,n-1 ))
printf("%d %d\n",a[i],x-a[i]) ;
}``````

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

Can somebody please explain what do you mean by "minimum loop" ??

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

It just means minimum loops i.e best time complexity. You can also solve the problem in O(n^2) but than won't be the solution with minimum loop.

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

import java.util.Arrays;

public class Sum_of_number {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] numbers ={2,4,3,1,6,3,8,1,2,4,5,9,4,0,1};
int value =20;
Arrays.sort(numbers);
int low =0;
int high = numbers.length-1;
int sum =0;

sum = numbers[low]+numbers[high];

while(true)
{
if(sum==value)
{
System.out.println(numbers[low]);
System.out.println(numbers[high]);
break;

}
else if(sum>value)
{
high = high-1;
sum = numbers[low]+numbers[high];

}
else if(sum<value)
{
low = low+1;
sum = numbers[low]+numbers[high];

}

}
}
}

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.