Amazon Interview Question for Development Support Engineers






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

- abhi1301 May 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Simple and good solution :-)

- NirmalGeo May 05, 2011 | Flag
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)

- vijay May 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@abhi : can you explain your logic

- Anonymous May 05, 2011 | Flag Reply
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
(add array[ptr1] +

- Monish May 06, 2011 | Flag Reply
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

- Hari Sudan May 07, 2011 | Flag Reply
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)

- Sudhindra May 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

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

indeed this is o(n^2)

- Anonymous February 23, 2012 | Flag
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]) ;
	}

- Nishant Agarwal June 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous July 08, 2011 | Flag Reply
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.

- Zodiac July 10, 2011 | Flag Reply
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];


}



}
}
}

- Thahir February 18, 2012 | Flag Reply


Add a Comment
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.

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