## 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)

return common;
}``````

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

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

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

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

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 )

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

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.

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

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

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

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.

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

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.

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

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

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

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.

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

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

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

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.

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

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

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

can u explain briefly .

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)

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

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

}

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

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

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

}

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

}``````

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.

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

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