## Amazon Interview Question

Software Engineer / DevelopersFor 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.

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

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]);
}
}
```

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)

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

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

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