CareerCup

do you remember the interviewer's name? i have Amazon interview today (10th).

1st question can be done by sorting both arrays in nlogn time and then taking the smaller first element from both array and compare them.
2nd way is to hash them but this depends upon the range.

A little variation to Jitesh answer,

1. Sort the 2 arrays (o(nlgn)) Let say array A and B
2. Pick the smaller element of the sorted arrays. say A[0] < B[0]
3. remove / move ahead of all elements in smaller array(A) till next number is greater/equal B's current element. Meaning to say,
while(A[i] < B[j])
i++;
4. Check if A[i] == B[j] ( repeated element) - record it.
5. carry on step 3,4 till you have traversed atleast one array.

total complexity o(2n) + o(nlgn) ==> o(nlgn)

Killer's answer is an improvement no doubt. I would like to propose sorting just one array and doing binary search on it to find common elements with the second unsorted array. This maybe a little less efficient than Killer's though.

I hate hash table solutions as they will consume extra space and I feel we tend to escape thinking about other approaches by stating hash immediately.

how much time do they give to mail back the answers?

Well, sorry to interrupt you guys, but I was asked a almost similar kind of question but not in Amazon and not on Array.

The question was basically asked upon LinkedLists, wherein I was given two linked lists, which are meeting at some point and I had to find out the merging point of the two lists.

And the time when the question was asked, I wasn't really aware of how to do it, but later on I finally solved it.

So suppose, I have two link lists
L1 = 1 -> 2 -> 3 -> 5 -> 9 -> 20
L2 = a -> b -> c -> 2 -> 3 -> ...

So here both are meeting at the second element of the List L1.

The answer I thought upon was, we will take the length of the two link lists, say length of L1 is 6 and L2 is 8. So subtracting 8 - 6, I get 2.

Now, in the bigger list i.e. L2, start from the second node and start from the 1 node from the List L1.

So, on first remove, we will remove first element from each of the list and compare,
L1 -> 1 and L2 c, not matched
L1 -> 2 and L2 2, matched, and thus we get the merging point.

Thanks

it is not a good idea to count the no of nodes in the lists!
i have another idea for this.
maintain 2 queues for 2 linked lists
enqueue the nodes into their respective queues.
then deque one by one and compare if they are equal.
if equal return the node!

so is there any other way other than counting the nodes in the list?

let Array1[N] and Array2[M] where N>M.
Create a HashTable.
Put contents of array[1] in the hashtable=> O(n)
Put the contents of 2nd array in the HashTable => O(n).
Total O(n) + O(n)=O(n)
Collision while putting the content of second array means common elements.

A simple answer would be to find the length of both the linked lists and have two pointers, one for each linked list. Move (difference in lengths) steps in the longer linked lists and then start moving both the pointers by one every time until you have both the pointers pointing to the same node.

time Complexity - O(2n) = O(n)