Amazon Interview Question Software Engineer in Tests
solution 1:
Anonymous is correct. scan Array_1, record in hash table. scan Array_2, look up in Hash table.
time: O(n)
solution 2:
use BST, build Array_1 to a BST, scan Array_2, look up in BST
Time: O(nlgn)
Solution 3:
if memory is not large enough, use bitset
bitset might not be a good solution, since it can only store true or false. What we also want to store is the repeated times of that value.
The solution don't work properly since it won't print the output as "2 x" solution to that problem can be solved if u use 2 hash tables. do exactly as the first solution but while reading the second array when u find the element reduce the occurrence by 1 and till it becomes zero and on the second hash table increase the value by one. after the scan is done, print the second hash table.
There is no need to maintain a counter variable for it, like if you put all the elements of the first array in the hashset and then, keep checking the elements from the hashset which matches and print them while inserting the elements of the first array into the hashset don't check whether the element is present in the array because it will not print the duplicate element.
sort first array by any good sorting technique say quick sort then pick first element and do binary search for in array1 which is sorted this search will be ologn for each element.
template <class T>
vector<T> ArrayIntersection(const vector<T> vecA, const vector<T> vecB)
{
vector<T>::const_iterator ite= vecA.begin ();
map<T, int> counter;
while (ite!= vecA.end())
{
++counter[*ite];
++ite;
}
vector<T> result;
ite= vecB.begin();
while (ite!=vecB.end ())
{
if (counter[*ite])
{
result.push_back(*ite);
if (counter[*ite]==1){
counter.erase (*ite);
}
else counter[*ite]--;
}
++ite;
}
return result;
}
1. Sort both arrays (O(nlogn))
2. Take two counters to traverse both arrays one counter pointing to each array in the beginning O(1)
3. move the counter to next elt which is pointing to smaller number eg. first array has current number 5 while second array has 8 then move the first counte to next elt.
4. If both are same print the elts and move both counters.
As soon as you are done with any array. steps 3 and 4 th O(n)
Total complexity = o(nlogn) + o(n) = o(nlogn)
@ANANT
first you need to find out sorting algos on bigger chunk of data...for bigger ur solution seems inappropriate.....suggest another thought of ur mind
we can do this also by XORing the elements of one array to find the repeated ones in both arrays indivisually in O(n).then if any element is in common move that to output array.now XOR elements of one array with other taking one element from both turn by turn.if result comes 0,chaek if the element is in common,if not move to output array else leave it.
complexity is O(n)+O(n)=O(n)
We can solve this using a HashTable.
- Anonymous May 08, 2009Traverse First Array, keeping each of the array elements as a key, increment the value at the key. Once done with traversing the first array.
Now for the second array again in the same HashTable lookup with the key as element from second array. If the value is != 0, copy the element in to output array. decrement the value count.
if value is 0 then move to next element in the array list. Once done with traversing the second array as well return the output array.
I screwed up with this in the intv, I took two different hash tables for both the arrays with definite pre-defined set of Keys (All Possible character's). The after comparision of two Hashtables returned the output array.
This was asked in tele phonic intv.