Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Why do you need additional arraylist while you can do the same thing, just using the hashmap?
shouldn't the answer be a boolean?
btw, what is the example of the input (other then {0,1,2,..}) which meets requirements?
walk the input array (say A) and create another array of structures (B). such that
b[i].index = i
b[i].diff = a[i] - i;
Now our problem is reduced to finding two elements in B such that the sum of diff is zero! To do that sort the new array on the key = abs(b[i].diff)
now walk the array b, and see if any adjusant elements sum is zero. If yes, then we got our target, if not we didnt!
This will be O(n + nlogn + n) == O(n log(n)) solution.
for A = {12, -3, 12, 12, 8}
the B = { {0,12}, {1,-4}, {2, 10}, {3, 9}, {4,4}}
when you sort B by abs(diff) you get
B = { {1,-4}, {4,4}, {3, 9}, {2, 10}, {0,12}}
Now since b[0].diff + b[1].diff == 0
you return the answer a i = 1, j = 4
To explain more on why method works:
we are looking for i and j so that
i + j = a[i] + a[j]
i.e
a[i] - i = - 1 * (a[j] - j)
we store the diff of a[i] - i in B[i].diff
and by looking at two elements in b where B[i].diff - B[j].diff == 0 we find our answer.
// FindIJ.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
int partition(int a[], int l, int r) {
int pivot, i, j, t;
pivot = a[l];
i = l; j = r + 1;
while (1)
{
do ++i; while (a[i] <= pivot && i <= r);
do --j; while (a[j] > pivot);
if (i >= j) break;
t = a[i]; a[i] = a[j]; a[j] = t;
}
t = a[l]; a[l] = a[j]; a[j] = t;
return j;
}
void quickSort(int a[], int l, int r)
{
int j;
if (l < r)
{
// divide and conquer
j = partition(a, l, r);
quickSort(a, l, j - 1);
quickSort(a, j + 1, r);
}
}
// returns true if two elements exist in a, such that a[i] + a[j] = i + j
bool DoesExist(int a[], int n)
{
for (int i = 0; i < n; i++)
{
a[i] = i - a[i];
}
// sort the array
quickSort(a, 0, n - 1);
for (int i = 0; i < n-1; i++)
{
if (a[i] + a[i+1] == 0) return true;
}
return false;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = { 12, -3, 12, 12, 8 };
printf("DoesExist(\"{ 12, -3, 12, 12, 8 }\"):"); DoesExist(a, sizeof(a) / sizeof(a[0])) ? printf("yes\n") : printf("no\n");
int b[] = { 12, -2, 12, 12, 8 };
printf("DoesExist(\"{ 12, -2, 12, 12, 8 }\"):"), DoesExist(b, sizeof(b) / sizeof(b[0])) ? printf("yes\n") : printf("no\n");
}
O(n) solution,
Basically keep a track of (Value - Index) of all the element you walked thru, if you happen to see one that the result of (index - value) is logged previously you got the pair .
private static bool ContainElementsWithValueSumEqualsToIndexSum(int[] array)
{
var hash = new HashSet<int>();
int idx;
for(idx = 0; idx < array.Length; idx++)
{
if(hash.Contains(- (array[idx] - idx)))
return true;
else
hash.Add(array[idx] - idx);
}
return false;
}
/*
Assume int i and j are index positions.
2 Possible Cases:
1) arr[i] = i, arr[j] = j
thus, arr[i] + arr[j] = i + j
2) arr[i] = j, arr[j] = i;
thus, j + i = i + j
*/
public static boolean isSumEqualToIndices(int[] arr)
{
if (arr == null || arr.length < 2)
return false;
HashMap<Integer, Integer> ht = new HashMap<>();
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == i)
{
if (ht.containsKey(null) == false)
ht.put(null, i);
else
return true;
}
if (arr[i] != i)
{
if (ht.containsKey(arr[i])
{
if (ht.get(arr[i]) == i)
return true;
}
}
ht.put(i, arr[i]);
}
return false;
}
Let's say i'th and j'th element in the array are p and q, respectively . What we want is
i + j = p + q
or
i - p = - (j - q)
O(n) algorithm:
1. walk over the array and do
a[i] = a[i] - i
2. Again walk over the array
h = hashMap
for every A[i]:
if -A[i] in h :
return true;
else
insert A[i] -> h
public class Sum {
//a[i]+a[j]=i+j
//a[i]-i =j-a[j]
public static void main(String[] args) {
int[] array = {6, 1, 3, 2, 10, 14, 50};
Map<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
for (int i = 0; i < array.length; i++) {
hashmap.put(array[i] - i, i);
}
for (int i = 0; i < array.length; i++) {
if (hashmap.containsKey(i-array[i]) && hashmap.get(i-array[i])!=i)
{
System.out.print("the condition is true " +"index1: "+ i +", value1: "+array[i]+", index2: "+hashmap.get(i-array[i])+", value2: "+array[hashmap.get(i-array[i])]);
break;
}
}
}
}
actually I found the array is just 0, 1, 2, 3, 4.....
proof:
consider the first three elements, namely x, y, z so x has index 0, y->1, z->2
we have the following equations:
x+y = 0+1=1
y+z = 1+2 = 3
x+z = 0+2 =2
so we get x = 0, y = 1, z =3 it is a fixed solution
now we prove that the array is 0, 1, 2, 3..... as follows:
suppose we have any two distinct elements a1, a2(suppose a2 is not the last element) in that array, and a3 is the element right next to a2, so the index[a3]=index[a2]+1
we have a1+a3 = index[a1]+index[a3] = index[a1]+index[a2]+1=a1+a2+1
so we have a3 = a2+1
which means we have an unique array 0, 1, 2, 3, 4,......
END
Since we know we are looking for pairs where x+y = A[x] + A[y], by simple algebra, you can also look for x-A[x] = A[y]-y
- andrew January 15, 2014