## Amazon Interview Question for Software Engineer / Developers

• 0

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.

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

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

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.

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

Kudos S!

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

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

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

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

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

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)

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{

}

}``````

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

nice one

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)

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.

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.

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=12,
23 ignore
collision 12+12 != 13, ignore
a = 4
Found: a=12, plus input=13, so found

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>

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.
again scan the array put 3 in array, put 15 in array, put 8 in array 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 :-)

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.