Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    0
    of 0 votes
    32
    Answers

    5) Programming question:
    a. Given two integer arrays and the size of each array.
    b. Determine if arrays match.
    c. Order of elements does not matter.
    d. Number of occurrences does matter.
    e. Return true for match, false for no match
    f. Computational complexity is important.

    - Nona Namgiv on November 09, 2010 Report Duplicate | Flag
    Amazon Software Engineer / Developer Coding



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

- chennavarri on November 09, 2010 | Flag Reply
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.

- nitin on November 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous on November 10, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- blue_skin on November 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Darpok on November 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- blue_skin on November 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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]

- blue_skin on November 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- blue_skin on November 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 on November 11, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- chennavarri on November 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on November 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Balaji on November 19, 2010 | Flag
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()) );

- Kannan on November 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kannan on November 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- blue_skin on November 13, 2010 | Flag
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.

- ekapil2 on November 14, 2010 | Flag Reply
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...

- vince on November 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- spookymulder83 on November 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about using a hashset?
PS: Iterator only executes if you have same unique hashset a1 and a2.

- IntroJ on November 16, 2010 | Flag Reply
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++)
{
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));

}

}

- IntroJ on November 16, 2010 | Flag Reply
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.

- IntroJ on November 17, 2010 | Flag Reply
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

- ketz on November 19, 2010 | Flag Reply
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?

- Srividya on November 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, xoring is flawed. I just got it.

- Srividya on November 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ashish Sharma on December 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ashish Sharma on December 02, 2010 | Flag
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;
}
}

- bawet on November 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ik on November 23, 2010 | Flag
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[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.

- Anonymous on February 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- tbag on February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

Still not a very good solution for very large arrays.

- tbag on February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#python

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

- weijiang2009 on February 06, 2011 | Flag Reply


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More