Amazon Interview Question for Software Engineer / Developers


Team: AWS
Country: United States
Interview Type: Phone Interview




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

Using hash map will cost O(nlgn). There is a more efficient way to do it in O(n). As the integers are 8 bit so keep an int array of constant size 256. Now, make a pass through first array and use the element of the first array as the index of this array to update the count. Now make a pass to the second array and for each element check if this array contains positive count at the index=element.

public Set<Integer> findCommonElements(byte[] a, byte[] b)
{
	int count[256];
	Set<Intetger> common = HashSet<Integer>();
	
	for(int i=0; i<a.length; i++)
		count[a[i]]++;

	for(int i=0; i<b.length; i++)
		if(count[b[i]] > 0)
			common.add(b[i]);
	
	return common;
}

- zahidbuet106 April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Yep, that's what my final solution was.
Not sure why you say Hashmap will cost n log n

- puneet.sohi April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Yeah, what's with the comment that hashmap will cost nlogn?

- Anonymous April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i guess he meant to say lookup in hash map takes O(logN) so in total its O(NlogN)(and you can't that he is wrong :P )

- karthik April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For the solution without hashtable, what if the elements are duplicate in the arrays? And how does that solution becomes nlogn? I could not get it.

- Victor April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Any duplicates in array 'a' will show up as a common element, even if it does not exist in array 'b' at all.

- rroman01 April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

While using a BitVector or a 256 element flag array, as in this solution, seems more elegant - using a hashtable is also O(n). This is because each put and get is constant time in hashmaps/hashtables.

- Michael.J.Keating April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I got it, but i have one doubt. What about negative numbers. If you are making array of 256 index form 0 to 255. Byte[] A can have negative number also, so we do need to check before incrementing frequency of index?
What i mean, like if -25, then increment the frequency of count[127+25]?
Why i add 127; because positive numbers can atmost 127.
Please Advice.

- Avsa May 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, that is correct. Also, instead of using integer array of 256, we can use char array as all we need to do is maintain flag (no of repetitions is not asked).

- nharryp May 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static ArrayList<Byte> findCommonElements(byte[] a, byte[] b) {

	// record values in 'a' in a HashMap - O(n)  
	HashMap<Byte, Boolean> mapA = new HashMap<Byte, Boolean>();	
	for (byte val : a) 
		mapA.put(val, true);		

	// record common values in a new HashMap - O(n)
	HashMap<Byte, Boolean> mapAB = new HashMap<Byte, Boolean>();	
	for (byte val : b) {
		if (mapA.get(val) != null)
			mapAB.put(val, true);
	}

	// the common values - O(n)
	return new ArrayList<Byte>(mapAB.keys);
}

- Michael.J.Keating April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. using brute force will give O(n2) complexity.
2. sorting and comparing will give O(nlogn) complexity.
3. Using one array to se a bit vector and other to check if bit is set will give O(n) complexity.

- Nitin April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For 3, I don't think keeping a bitmap is wise as there could be thousands of element with most of repetitions.

- Victor April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Victor, the problem states that the arrays contain 8 bit integers, and we're looking for duplicates, so we only need a bit vector of length 256 regardless of how large the arrays are.

- David April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The bit vector size would be only need to be 32 bytes (256 bits).

- Michael.J.Keating May 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can u explain briefly .

- Aaron April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#define VAR_MAX 0x100
#define VAR_ELEM 0x08

#include <iostream>
using namespace std;

int v_tmp[VAR_MAX];
int v_in1[VAR_ELEM] = { 3, 6, 8, 2, 4, 1, 9, 5 };
int v_in2[VAR_ELEM] = { 3, 7, 4, 9, 5, 9, 8, 5 };
int v_out[VAR_ELEM];

void bucket_sort( int *v_ptr, int v_size )
{
int in, out;

for(out=0; out<VAR_MAX; out++)
{
v_tmp[out] = 0xFF;
}

for(in=0; in<v_size; in++)
{
out = v_ptr[in];
v_tmp[out]++;
}

for(in=0, out=0; in<VAR_MAX;)
{
if ( v_tmp[in] != 0xFF )
{
if(out >= VAR_MAX) return; // data protection

v_ptr[out] = in;
out++;
v_tmp[in]--;
}
else
{
in++;
}
}
}

int main()
{
int in1,in2;

bucket_sort( v_in1, VAR_ELEM );
cout << endl;
for(in1=0; in1<VAR_ELEM; in1++)
{
cout << v_in1[in1] << " ";
}

bucket_sort( v_in2, VAR_ELEM );
cout << endl;
for(in2=0; in2<VAR_ELEM; in2++)
{
cout << v_in2[in2] << " ";
}

cout << endl;
for(in1=0,in2=0; in1<VAR_ELEM && in2<VAR_ELEM;)
{
if( v_in1[in1] == v_in2[in2])
{
cout << v_in1[in1] << " ";
in1++;
in2++;
}
else if( v_in1[in1] < v_in2[in2])
{
in1++;
}
else if( v_in1[in1] > v_in2[in2])
{
in2++;
}
}

return 0;
}

Bucket Sort - O(n)

- Zack April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

std::vector<char> get_common(char *A, size_t An, char *B, size_t Bn)
{
std::vector<char> common;
common.reserve(std::max(An,Bn));

bool cache[256] = {false};

for(size_t i = 0; i < An; ++i)
cache[A[i]] = true;

for(size_t i = 0; i < Bn; ++i)
if (cache[B[i]])
common.push_back(B[i]);

return std::move(common);

}

int main()
{
char A[] = {1,2,3,4,7};
char B[] = {3,4,5,6,7,9,1};

cout << "sizeof(A):" << sizeof(A) << endl;
cout << "sizeof(B):" << sizeof(B) << endl;

auto com = get_common(&A[0], sizeof(A), &B[0], sizeof(B));
std::for_each(com.begin(), com.end(), [](char i){std::cout<<(int)i<<" ";});
return 0;
}

- Anonymous April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findCommonElements(int [] a , int [] b){
		// each containing 8 bits integer
		boolean [] flag = new boolean [256] ;
		for (int i = 0 ; i <= a.length ; ++i){
			flag [a[i]] = true ;
		}
		
		for (int i = 0 ; i < b.length ; ++i){
			if (flag[b[i]]){
				System.out.println("common elements is " + b[i]);
			}
		}

}

- Scott April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you could use the apporach outlined here - htp/algohub.blogspot.in/2014/04/intersection-of-two-sorted-arrays.html

- anon123 May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can put both arrays in 2 different sets and use retainAll method of set that finds the intersection of sets

- Vivek Grewal May 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python approach without using "in":

{

def findDuplicates(arr1, arr2):
    storage = [[] for i in range(256)]
    for i in arr1:
        storage[i] = 1;
    
    for i in arr2:
        if(storage[i] == 1):
            print i
    
def main():
    arr1 = [4, 5, 32, 110]
    arr2 = [13, 42, 32, 191, 93, 4]
    findDuplicates(arr1, arr2)

}

- NL May 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

max value of an array element is 255, so we can just sort both arrays using counting sort or bucket sort (time complexity is O(n)).
then just start comparing from smallest element, if they are equal compare next ones, if element in first array is greater, then compare with the next element of second array an so on,..
here is the code:

public class Test {

    public static void main(String[] args) {
        
        int[] a = {5, 8, 255, 45, 10, 9};
        int[] b = {1, 4, 211, 8, 210, 5, 10, 9};
        int[] resa = countingSort(a);
        int[] resb = countingSort(b);
        
        int i = 0;
        int j = 0;
        
        while (i != a.length && j != b.length) {
            if (resa[i] == resb[j]) {
                System.out.println("common element: " + resa[i]);
                i++;
                j++;
            } else if (resa[i] > resb[j]) {
                j++;
            } else {
                i++;
            }
        }

    }

    private static int[] countingSort(int[] a) {
        int[] count = new int[256];
        int[] output = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            count[a[i]]++;
        }

        for (int i = 1; i < 256; i++) {
            count[i] = count[i] + count[i - 1];
        }

        for (int i = 0; i < a.length; i++) {
            count[a[i]]--;
            output[count[a[i]]] = a[i];
        }
        return output;
    }

}

- madi.sagimbekov March 31, 2015 | Flag Reply


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

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