Amazon Interview Question
Software Engineer / DevelopersTeam: AWS
Country: United States
Interview Type: Phone Interview
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 )
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.
Any duplicates in array 'a' will show up as a common element, even if it does not exist in array 'b' at all.
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.
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.
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);
}
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.
For 3, I don't think keeping a bitmap is wise as there could be thousands of element with most of repetitions.
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.
#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)
#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;
}
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]);
}
}
}
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;
}
}
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.
- zahidbuet106 April 29, 2014