## Amazon Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
0
of 0 vote

A possible solution but maybe not the best would be using a hashmap.
Time: O(n)
Space: O(n)
if only computational complexity is important then this would be the best. Thanks

Comment hidden because of low score. Click to expand.
0
of 0 vote

sort and compare
Complexity O(nlog(n))
Otherwise map approach can be used to obtain a complexity of O(n) with O(n) space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Have you ignored this condition "d. Number of occurrences does matter."?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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]

Comment hidden because of low score. Click to expand.
0

After all this, the complexity is still O(n), if space is not an issue then I support a hash table solution

Comment hidden because of low score. Click to expand.
0

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()) );``````

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Guys, even with small positive numbers it fails

Array1 = {4}
Array2 = {2,2}

Probably no of elements also count. But still method does not hold good for all conditions

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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()) );``````

Comment hidden because of low score. Click to expand.
0

This will work for -ve, 0 and +ve numbers.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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...

Comment hidden because of low score. Click to expand.
0

If I understand your algorithm correctly, when array1 is 1,1 and array2 is 2,2 then x will be 0, but the arrays are not equal.

Comment hidden because of low score. Click to expand.
0
of 0 vote

PS: Iterator only executes if you have same unique hashset a1 and a2.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++)
{
}
for(int i=0;i<a2.length;i++)
{
}

if(hs1.size()==hs2.size())
{
Iterator itr = hs1.iterator();
while(itr.hasNext()) {
{
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));

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry. Haven't consider the no of occurrence condition... ... instead of hash set.. hash Map can solve the occurrence condition.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0

Sorry, xoring is flawed. I just got it.

Comment hidden because of low score. Click to expand.
0

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 ....

Comment hidden because of low score. Click to expand.
0

but in this case we will have to count zeros in both arrays initialy.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

Comment hidden because of low score. Click to expand.
0

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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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=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.

Comment hidden because of low score. Click to expand.
0

But your algorithm does not take into account number of occurrences of elements, does it?

Comment hidden because of low score. Click to expand.
0

I guess the same logic, but incrementing the value each time you find some element should work.

So if we encounter 8, bit-array=1.
For another occurrence of 9, bit-array=2.

Still not a very good solution for very large arrays.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#python

if arr1 == arr2:
return True
elif:
return False

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.