Amazon Interview Question for Software Engineer / Developers






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

I think you can do it nlogn. For O(n) there must be some DP solution which i am not able to think of. Sort the array and for each element [0<=j<len A] , subtract i-A[j] and do a binary search for this element in sorted array.

- Mukesh Tiwari February 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree, sort and then binary search will do in O(nlogn) and hashmap (frequency of no, number) should work in O(n).

- neo February 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For O(n log n): sort array in place and then have two indexes, one at start and one at the end. If the sum < I, move first index. if sum > I, move second index. if sum == I, stop.
For O(n): use a hashmap/hashtable/dictionary where you keep the values I-A[i] for every element in the array. Then check if A[i] exists in the hashtable. Of course, you shoul be careful for the following case: e.g.: I = 10, A = [1,2,3,4,5,6] and 5, 5 is not a solution.

- S February 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Kudos S!

- AB February 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice answer S. For O(n) case, how do we detect such cases as for 5 that you mentioned above ?

- Bandicoot February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Eliminate those entries having both key and value with same numbers(Values)

- Vasundhara February 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for nlog(n): first sort list with merge sort in nlogn, then go over list, for each item, subtract itt= from I, and search for (I-item) in log(n). since list is sorted, we can use binary search

- hamed February 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for nlog(n): first sort list with merge sort in nlogn, then go over the list. For each item a, subtract a from I = b, and then search the b in the rest of the item in log(n). Since list is sorted, the list can be search in binary search with the time complexity of log(n)

- weijiang2009 February 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The fastest way to do this is in order n, where you do only one pass through the array and store a key in the hashtable that is the difference of the I and a[i]

Hashtable table = new Hashtable();
for (int i = 0; i < array.length; i++){
      
      if ( table.containsKey( a[i] ){

              return a[i] and table[a[i]];
      }
      else{
       
           table.add(I-a[i], a[i]);

      }

}

- Anuj February 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice one

- Jim March 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Find length of array, say L::O(n)
2. Find Lth largest element using deterministic quick select::O(n)
3. Now we know the range, so use counting sort to sort the array::O(n)
4. Now keep two pointers at first and last positions, Add, if equal return true, if less move left pointer ahead, else move right pointer back by 1 position.::O(n)

- Anonymous February 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can do it in O(n)...
Hash first element.
Pick next element j and look for I-j in hash table, if available return j & I-j. Else enter into hash table and traverse the array till end.

- Anonymous February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) is possible with HashMap <Number, Count>
1. First keep every number to HashMap - O(n)
2. For each element in Map; check if it's pair is available ie., (sum - element); If available yes or else continue with other elements.

- Karthik February 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Easy: IP: 12 23 12 4 1 , sum = 13,
if(input > sum/2) hash = sum-input, else hash = input, if number > sum->ignore
a[1]=12,
23 ignore
collision 12+12 != 13, ignore
a[4] = 4
Found: a[1]=12, plus input=13, so found

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

<pre lang="" line="1" title="CodeMonkey94540" class="run-this">public void checkCompliment(int [] A, int sum){

Map map = new HashMap <Integer,Integer>();
int i=0;
while(i<A.length){
if(map.containsKey(sum-A[i])){
// print the two numbers
System.out.println("i:"+new Integer(A[i])+"sum-i:"+new Integer(sum-A[i]));

}
else map.put(A[i],A[i]);
i++;
}

}</pre><pre title="CodeMonkey94540" input="yes">
int [] A= new int []{3,11,9,5,1};
// new Complement().checkCompliment(A, 12);
int [] A1= new int []{};
new Complement().checkCompliment(A1, 12);</pre>

- Anonymous August 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Initially scan the array and find the max value.
Let take example,
array contains 3 15 8 5 10... you want to find 11
max in the array was 15
so create an array[max]... in this case array[15].
again scan the array put 3 in array[3], put 15 in array[15], put 8 in array[8] and so on.


here the 11 may be the following combination,
10+1,
9+2,
8+3, etc.

in our array first element was 3 then search at the index 8 if 8 is present then we return ture... if not then search again the same method.

Time complexity:-
find max=O(n)
search and put the element into array=O(n)
find the two element=O(n)
totally+O(n+n+n)=== O(n)


If any wrong write command :-)

- Preethi July 08, 2014 | 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