Amazon Interview Question
Software Engineer / DevelopersAdd all the elements in the each array. hold in variable addArr1 and addArr2
Multiplly all the elements in the each array. hold in variable mulArr1 and mulArr2
if addArr1 == addArr2 && mulArr1 == mulArr2 then both the array match else do not match.
Note: work for the positive numbers only.
Theoretically a good idea but practically multiplying numbers would easily exceed the capacity of current standard datatypes. For example, the array contains 200 elements from 1 to 200, the multiplying would be 200! most of our standard datatypes wont be able to store such numbers. now what if the numbers are something in the 10000 or 100000 range.
Good approach though, I like it
It should still work, number of occurrences are taken into consideration
array1 = [1 2 3 2 4 2], sum = 14, product = 96
array2 = [3 1 2 2 2 4], sum = 14, product = 96
PS: again, this fails for large numbers and large arrays
so here are a list of conditions for anonymous' solution:
-> works for only +ve numbers > 0
-> equal length arrays only
-> smaller numbers and smaller arrays [depending on the datatype used]
After all this, the complexity is still O(n), if space is not an issue then I support a hash table solution
The large number wouldn't be a problem if we go on adding/subtracting and multiplying/dividing.
This will work only if there are no zeros in the list of integers.
int sum = 0;
double mul = 1.0;
for( int i = 0; i<8; ++i )
{
sum = sum + array1[i] - array2[i];
mul = mul * array1[i] / array2[i];
}
return ( (sum == 0) && ((mul - 1.0) < numeric_limits<double>::min()) );
@Kannan: I prefer your solution but interviewers wont accept it because the solution has to be successful in all cases when compared to a worser complexity algorithm. Sort and compare for this problem will work for a case like below
a1 = [ (2^128−1) , 2^127 , 4, 1, 2, 10]
a2 = [ 2 , 4, 1, 10, (2^128−1), (2^128−1)]
If you sort both and compare then it would definitely work.
But your code would fail. The algo you wrote is a really good approach. But as blue_skin points out, there are constraints to your solution as >0 and datatype range
Thanks
The sum and the product of the elements of a multiset are not sufficient in uniquely identifying the multiset itself.
This is nicely illustrated on an external page,
math . stackexchange . com / questions/8207/is-a-combination-of-sum-and-product-of-any-sequence-unique
An excellent counter-example given by a user on that page is the following: { 2, 4, 6, 6 } vs. { 3, 3, 4, 8 }. Both have sum 18 and product 288.
@Chennavarri
By a small modification we can count the zeros also
int zeroCount = 0;
int sum = 0;
double mul = 1.0;
for( int i = 0; i<10; ++i )
{
int val1 = array1[i];
int val2 = array2[i];
if( val1 == 0 )
{
++zeroCount;
val1 = 1;
}
if( val2 == 0 )
{
--zeroCount;
val2 = 1;
}
sum = sum + val1 - val2;
mul = mul * val1 / val2;
}
return ( (zeroCount == 0) && (sum == 0) && ((mul - 1.0) < numeric_limits<double>::min()) );
hey kannan, that works but as chennavarri mentioned its still not complete. it is limited by the datatype size. for example consider a simple example as below.
a1 = [ 2,2,2......[500 times],1,1,1,....[500 times]]
a2 = [ 1,1,1......[500 times],2,2,2,.....[500 times]]
your 'mul' variable would give invalid results because it goes out of range
Since order and occurrences of elements doesn't match make a bit map vector of each array where bit_x i = 1 in case the element is present. The array would match if bit_x XOR bit_y == 1. (All present or not present).
This won't be efficient in case one element is 1 and other is 10000. But, this can be one solution.
Not sure if this will work, but could we keep a running xor of the all the values in a1 and a2. So we can iterate over both lists at the same time and have a variable x which will store the bitwise xor of all the values in both arrays. If x == zero at the end then a1 and a2 are equal.
Let me know where my logic is flawed...
package com.intro.amazon;
import java.util.HashSet;
import java.util.Iterator;
public class MatchArray0003 {
public boolean matchArray(int[] a1, int[] a2)
{
HashSet<Integer> hs1 = new HashSet<Integer>();
HashSet<Integer> hs2 = new HashSet<Integer>();
for(int i=0;i<a1.length;i++)
{
hs1.add(a1[i]);
}
for(int i=0;i<a2.length;i++)
{
hs2.add(a2[i]);
}
if(hs1.size()==hs2.size())
{
Iterator itr = hs1.iterator();
while(itr.hasNext()) {
if(hs1.add((Integer)itr.next()))
{
return false;
}
}
}
else
{
return false;
}
return true;
}
public static void main(String args[])
{
int[] a1={1,2,3,2,3,4,5,6,3,4,2,1,7};
int[] a2={5,4,2,6,7,1,3};
MatchArray0003 obj = new MatchArray0003();
System.out.println(obj.matchArray(a1, a2));
}
}
Create a HashMap
Passing array1 into the HashMap (complexity O(n))
1. If no hit then add the key into the HashMap and set Value as 1
2. If Hit, increment the value by 1
Passing array2 into the HashMap (complexity O(n))
1. If Hit, then decrement the value by 1
2. If no Hit, then ARRAYS DONT MATCH-> return False
Array2 passed with ALL Hits
1. Scan the HashMap for value not equal to zero (complexity O(n))
2. If all zeros then Match else no Match
Overall complexity is 3n i.e O(n)
Space complexity O(n) for the hashmap
Why would nt xor work? If we keep xoring the elements of both arrays, if they both are equal then result would be 0, if it is non zero then they are not equal. Am i missing something?
Yes.. but I think if XOR of two arrays is zero .... and if we subtract arr1[i] - arr2 [i] .. it should come as zero as well
as well size of both arrays should be equal ....
public boolean compareArray() {
Map<Integer, Integer> numMap = new HashMap<Integer, Integer>();
int lenA = A.length;
int lenB = B.length;
if (lenA != lenB) { return false; }
for (int i=0; i<lenA; i++) {
if (!numMap.containsKey(A[i])) {
numMap.put(A[i], 1);
} else {
int count = numMap.get(A[i]);
numMap.put(A[i], count+1);
}
}
for (int i=0; i<lenB; i++) {
if (!numMap.containsKey(B[i])) {
return false;
} else {
int count = numMap.get(B[i]);
if (count > 1) {
numMap.put(B[i], count-1);
} else {
numMap.remove(B[i]);
}
}
}
if (numMap.size() == 0) {
return true;
} else {
return false;
}
}
Some comments to the above code.
public boolean compareArray() {
Map<Integer, Integer> numMap = new HashMap<Integer, Integer>();
int lenA = A.length;
int lenB = B.length;
if (lenA != lenB) { return false; }
// Now it traverses the array A
// If the numMap doesn't contain
//
// It seems we need two arrays
// A = {1,2,3,4,5}
// B = {2,3,4,1,5}
// First take the case of matching arrays
// 1 => 1
// 2 => 1
// 3 => 1
// 4 => 1
// 5 => 1
// Here basically the map is filled by the
// the elements of the array A, and the
// number of occurances of the element in
// array A
for (int i=0; i<lenA; i++) {
if (!numMap.containsKey(A[i])) {
numMap.put(A[i], 1);
} else {
int count = numMap.get(A[i]);
numMap.put(A[i], count+1);
}
}
Sort and Hashing are most generic solutions I guess which work for any input.
Assuming array elements are only +ve integers:
- Scan through both array once and find the max element in both. If they are not the same return false.
- If equal then allocate 2 arrays of size the max element. However we only need bit arrays i.e we need to store 0 or 1.
- Scan through the first array and wherever we encounter an element set the corresponding position bit in the bit-array to 1. So if we encounter 8, bit-array[7]=1.
- Do the same for 2nd array too.
- Xor both the bit-arrays. If the result is 0 then return true else false.
Time- O(n). Space is not dependent on n, its dependent on the maximum number. So if the max number is 200, we need to 400 bits worth of space.
Similar to the idea of hashing but this will only work if the array elements are positive integers.
But your algorithm does not take into account number of occurrences of elements, does it?
A possible solution but maybe not the best would be using a hashmap.
- chennavarri November 09, 2010Time: O(n)
Space: O(n)
if only computational complexity is important then this would be the best. Thanks