Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Could you please tell me how space complexity will be o(n)? What would be the hash function in this case? If we take number as index in array then array size would be more than n, probably we need to find some good hash function but this will complicate the problem. Thoughts?
Could you please tell me how space complexity will be o(n)? What would be the hash function in this case? If we take number as index in array then array size would be more than n, probably we need to find some good hash function but this will complicate the problem. Thoughts?
Actually, space complexity is not O(n), that's O(M), M is the range of the given numbers.
simple solution :
sort the array, take two index keep one at start node, another at end node, call then i and j
count = 0;
if A[i] + A[j] > sum
j--;
else if A[i] + A[j] < sum
i++;
else
output i and j and set increment count;
do the same untill j > i
if count == 0 output node present;
complexity : O(nlogn)
It is ok for this method if the requirement is that return true or false, namely if exist question. Once we detect the sum we return true.
public static void two_sum_problem(int arr[], int sum) {
// store all the elements of arr in a hashmap
HashMap hm = new HashMap();
for (int i = 0; i < arr.length; i++) {
hm.put(arr[i], arr[i]);
}
// go through the array, and check if the difference sum-arr[i] is in the hashmap
// if sum-arr[i] is in the hashmap, you have found two numbers that add upto sum.
for (int i = 0; i < arr.length; i++) {
int lookFor = sum - arr[i];
boolean hasValue = hm.containsValue(lookFor);
if (hasValue) {
System.out.println("Found: "+ arr[i] + "+" + lookFor + "=" + sum);
}
}
}
What if the array is {2,3,5} and my sum = 6. The array has number 3 in it - at that point, it will do hashmap.containsKey(sum – array[ i ]) = 3 and it will say it is present in the hashmap and the pair will be 3,3 that sums up to 6. But we don't want that as we have just one 3 in the array and not two of them.
No problem. The question is to find if there is a pair in the array whose sum is equal to a given value. No need to find them.
My answer is using hash table, as Chander Ramesh said. However, one point to take care is that if the given number is 4 and there is a 2 in the array, S - array[j] exists in the hash table. To avoid that, the frequency for each number can be recorded in the hash table. For that case, see if the frequency for 2 is 2, then it's ok, otherwise it's not the right case.
I am confused whether you need to find all subset whose sum is equal to S or just pairs of element..if pairs then the solution is pretty straightforward....
int[] in = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int i ,j,n;
n = 10;
for (i = 0, j = in.length - 1; j > i; i++, j--) {
if (in[i] + in[j] > n)
j--;
else if (in[i] + in[j] < n)
i++;
else
System.out.println("Pair(i+j=n) = ("+(i+","+j)+"="+n+")");
}
Be sure to take care the permutation of same numbers in a row.
e.g.
(90 , 99) : 9 + 9 = 18
(90 , 98) : 9 + 9 = 18
(90 , 97) : 9 + 9 = 18
(90 , 96) : 9 + 9 = 18
(91 , 100) : 9 + 9 = 18
(91 , 99) : 9 + 9 = 18
(91 , 98) : 9 + 9 = 18
(91 , 97) : 9 + 9 = 18
(91 , 96) : 9 + 9 = 18
(92 , 100) : 9 + 9 = 18
(92 , 99) : 9 + 9 = 18
(92 , 98) : 9 + 9 = 18
(92 , 97) : 9 + 9 = 18
(92 , 96) : 9 + 9 = 18
vector<int> sumarray;
const int size = 1000;
const int maxNum = 100;
for (int i = 0; i < size; i++) {
sumarray.push_back(ARC4RANDOM(maxNum));
}
sort(sumarray.begin(), sumarray.end());
const int sum = 2 * ARC4RANDOM(maxNum);
int count = 0;
{
unsigned int i = 0;
unsigned int j = (unsigned int)sumarray.size() - 1;
while (j > i) {
if (sumarray[i] + sumarray[j] > sum) {
j--;
} else if (sumarray[i] + sumarray[j] < sum) {
i++;
} else {
const unsigned int indexI = i;
const unsigned int indexJ = j;
while (j > i) {
if (sumarray[i] != sumarray[indexI] && sumarray[j] != sumarray[indexJ]) {break;}
if (sumarray[i] == sumarray[indexI]) {i++;}
if (sumarray[j] == sumarray[indexJ]) {j--;}
}
for (int c = indexI; c < i; c++) {
for (int b = indexJ; b > j; b--) {
cout << DebugLog << "(" << c << " , " << b << ") : " << sumarray[c] << " + " << sumarray[b] << " = " << sum << endl;
count++;
}
}
}
}
cout << DebugLog << "Sum Count:" << count << endl;
}
public static int[] arrayPairSumIndices(int[] a, int k)
{
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
for (int i = 0; i < a.length; i++)
{
if (hashMap.containsKey(k - a[i]))
{
return new int[]{hashMap.get(k - a[i]), i};
}
hashMap.put(a[i], i);
}
return null;
}
I'm pretty sure this is the best. O(n) time complexity and O(n) space. This returns the indices at which the two values are at.
public String find2Sum(int[] array, int sum) {
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < array.length; i++) {
set.add(array[i]);
}
for (int j = 0; j < array.length; j++) {
if (set.contains(sum - array[j])) {
return "first " + array[j] + " second " + (sum - array[j]);
}
}
return null;
}
Here's an O(n^2) and O(n) algorithms. Run them on your computer and see the difference
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Iterator;
public class TwoSumTest {
public static void main(String[] args) {
int max = 200_000;
int sum = 20000;
int[] a = new int[max];
for (int i = 0; i < max; i++) {
a[i] = (int) (max * Math.random());
}
TwoSumTest ts = new TwoSumTest();
System.out.println("\nHash version\n");
long now = System.currentTimeMillis();
StringBuffer sbh = ts.twoSumHash(a, sum);
System.out.println(System.currentTimeMillis() - now);
now = System.currentTimeMillis();
System.out.println("\nQuadratic version\n");
StringBuffer sb2 = ts.twoSumN2(a, sum);
System.out.println(System.currentTimeMillis() - now);
System.out.println("sbh: " + sbh.length() + " sb2: " + sb2.length());
if (sbh.toString().equals(sb2.toString())) {
System.out.println("Same output");
}
}
public StringBuffer twoSumN2(int[] a, int sum) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < a.length - 1; i++) {
for (int j = i + 1; j < a.length; j++) {
if (a[i] + a[j] == sum)
sb.append("(" + i + ":" + a[i] + "," + j + ":" + a[j] + ")");
}
}
return sb;
}
public StringBuffer twoSumHash(int[] a, int sum) {
Hashtable<Integer, ArrayList<Integer>> ht = new Hashtable<>();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < a.length; i++) {
ArrayList<Integer> row = ht.get(a[i]);
if (row == null) {
row = new ArrayList<>();
ht.put(a[i], row);
}
row.add(i);
}
for (int i = 0; i < a.length; i++) {
ArrayList<Integer> row = ht.get(sum - a[i]);
if (row != null) {
Iterator<Integer> it = row.iterator();
while (it.hasNext()) {
int j = it.next();
if (i < j) {
sb.append("(" + i + ":" + a[i] + "," + j + ":" + a[j] + ")");
}
}
}
}
return sb;
}
}
The 2 sum problem is a classic variation of the subset sum problem. It is defined as the following:
- Chander Ramesh January 18, 2013You have an unsorted array, and you are given a value S. Find all pairs of elements in the array that add up to value S.
2 solutions - one minimizes space complexity, and the other time. As stated in the "hint", one approach is to hash the entire array, and then for each element check if S-array[j] is in the hash table. This takes O(n) time and O(n) space to store the array.
Alternatively, if one wishes to minimize space complexity, simply sort the array. Then, have two pointers - one initialized to array[0] and the other array[length-1]. Then check the sums; if the sum is > S, decrement the right pointer. If it is < S, increment the left pointer.