Amazon Interview Question
InternsCountry: United States
The reason it works is because for example when we decrement the end pointer, we do this because it's too large to work with the current beginning pointer and hence too large to work with any of the subsequent beginning values since they're only going to get larger.
Idea:
Take each element of the array, put it in a hash map: O(n)
Loop the array once more: check if (target - element) is in the hash map: O(n) for the loop, O(1) for the subtraction and existence check in the map.
Total: O(n)
Thoughts? FWIW, a Python set would do nicely for this, rather than a hash map.
This approach is good, but 2 comments.
1) You are better of checking before inserting into hashmap, so you can break early if needed. Only one pass needed. Also, you won't have the problem of dealing with the case when you add the same element to get the target (eg. array is [2] and you are looking for 4).
2) This is worst case quadratic (bad input for hash function).
@Loler:
1) Clever, I like that shortcut.
2) Can you expand? My impression is we can assuming a good uniform non-colliding hash when using hashmaps/sets, otherwise a lot of algorithms stop becoming linear.
@jay: It is only _expected_ linear. Theoretically it is worst case (emphasis on worst case) quadratic.
Note that, I am not at all saying that we should reject the hash based solution for that reason. In fact, this is a very practical solution!
Just mentioning a possible reason why people are not upvoting :-)
What if the array contains duplicate values and their sum is target vaue
i.e. 1 2 3 3 4 and the target value is 6.
I guess this Hashmap wont work in that case.!!
From the first comment by Loler:
"Also, you won't have the problem of dealing with the case when you add the same element to get the target (eg. array is [2] and you are looking for 4)."
So to handle duplicate value case we need to have 2 iteration over hashmap, and while inserting if we get duplicate value then compare twice of it with sum.
@Rahul nice idea. I actually solved the problem this way in java, it assumes no duplicate values in the array.
public static boolean addsUp(int [] array, int sum){
if(array==null)
return false;
Set<Integer> targetSet = new HashSet<Integer>();
Set<Integer> arraySet= new HashSet<Integer>();
for(int i=0; i<array.length; i++){
targetSet.add(sum - array[i]);
arraySet.add(array[i]);
}
arraySet.retainAll(targetSet);
return arraySet.size()>1;
}
--- sort the array - O(n*logn)
--- loop through the array and for every element call binary search on that same array to find target - array[i] (of course ignore the element on the same index) - O(n*logn)
So in the end you have O(n*logn) + O(n*logn) = O(2*(n*logn)) = O(n*logn)
Is my O(n) solution wrong? If not - why does and O(nlogn) solution get more votes than an O(n) one? I just really want to know if I missed something here :-)
Jay, your answer isn't wrong but it's space complexity is O(N) whereas this and the other sorting solution would use O(1) space. Both are good answers and either could be the best depending on other factors.
Used the idea presented by @Jay. Expected O(n) time, O(n^2) worst case, and O(n) memory.
#include <iostream>
#include <vector>
#include <unordered_set>
#include <time.h>
#include <cstdlib>
bool addsUp(std::vector<int> input, int target){
std::unordered_set<int> temp_set;
for (int i = 0; i < input.size(); i++){
if (temp_set.find(target - input[i]) != temp_set.end()){
std::cout << "\n" << target - input[i] << " " << input[i];
return true;
}
temp_set.insert(input[i]);
}
return false;
}
int main(){
srand(time(NULL));
std::vector<int> my_vector;
for (int i = 0; i < 10; i++){
my_vector.push_back(rand() % 10);
std::cout << my_vector.back() << " ";
}
std::cout << "\nadds up to 13: " << addsUp(my_vector, 13) << "\n";
}
I consider the numbers are previously added in the hash.
bool addsUp(vector <int> &input, int target) {
for (int i = 0; i < input.size(); i++) {
int index = abs(target - input[i]) % KEY;
for (int j = 0; j < hash[index].size(); j++) {
if (target - input[i] == hash[index][j])
return true;
}
}
return false;
}
public class AddsUp {
public boolean checkSorted(int[] array, int target){
int l = 0;
int r = array.length - 1;
while(l<r){
int sum = array[l] + array[r];
if(sum == target){
return true;
}else if(sum < target){
++l;
}else{
--r;
}
}
return false;
}
public boolean checkNotSorted(int[] array, int target){
Set<Integer> values = new HashSet<>();
for(int val: array){
if(values.contains(target - val)){
return true;
}
values.add(val);
}
return false;
}
}
import java.util.Arrays;
public class ArraySumPair {
public static void main(String[] args) {
int [] a={1,2,3,4,1,5,6,0,9,8,1,2};
int [] arr={6,5,7,3,6,7,3,4,2,5,6,8,7,9,4,5,6,3};
Arrays.sort(arr);
getPair2(arr,14);
}
/**
* Find the pair in an array whose sum with complexity O(n). This assumes
* the array passed is sorted array and there are no duplicates in the array
*
* @param arr
* input array of elements
* @param k
* sum for which pair of array elements needs to be searched
*/
public static void getPair2(int[] arr, int k) {
int start = 0;
int end = arr.length - 1;
int sum = 0;
// output array to record matching pairs
StringBuilder arrs = new StringBuilder();
while (start < end) {
sum = arr[start] + arr[end];
if (sum == k) {
// we have found one pair, add it to our output array
arrs.append(arr[start] + "," + arr[end] + ";");
start++;
end--;
} else if (sum < k) {
start++;
} else {
end--;
}
}
System.out.println(arrs.toString());
}
}
Bool AddsUp(Array<int> input, int target)
{
for(int i = 0; i < input.size(); i++)
{
int nAnotherOne = target - input[i];
for(int j= i+1; j<input.size(); j++)
{
if(nAnotherOne == input[j])
return true;
}
}
return false;
}
target:
- Anonymous March 27, 2013132
First, sort the array.
3 21 32 67 89 100 128 130
Index the start and the end of the array and calculate the sum
If too small, increment the start index; if too large, decrement the end index.
>3 21 32 67 89 100 128 130< (130+3 = 133)
>3 21 32 67 89 100 128<130 (128+3 = 131)
3 >21 32 67 89 100 128<130 (128+21 = 149)
3 >21 32 67 89 100< 128130 (100+21 = 121)
3 21 >32 67 89 100< 128130 (100+32 = 132)
So we've found two values that add up to 132.
Complexity of sort O(N*logN) and complexity of finding step O(N) so total is O(N*logN).