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