Amazon Interview Question
Development Support Engineers(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] +
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)
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.
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];
}
}
}
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
- abhi1301 May 04, 2011for (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);