Microsoft Interview Question Software Engineer in Tests
Push all elements of array #2 onto an hash.
Use the index as value.
Search array #1 and get the indexes.
O(n) space & O(nlogn) solution :
Sort the 2nd array. Also maintain the original indexes of numbers before sorting. Now, traverse the first array, search each element in the 2nd array in logn(as it is sorted).
A similar approach
Create a BST out of those elements in the second array where each node has got the value and index number. O(n log n)
For every element in the first array, do a search on the BST created in step 1 and return the index. O(n log n)
Time Complexity:O(n log n) and space complexity O(n).
PS: If we are given doubly linked lists instead of arrays, then we can reduce the space complexity to O(1)
how is this more optimal than O(n) time and O(n) space solution using hashmap?
No way you get better than O(n) time. I guess he was looking for loop optimizations, fine tuning as such.
Yes I wonder the same thing. The hash table idea seems like a solid solution to me. That would have been my solution.
Assuming the arrays to be like what u have put as example . To avoid extra space(without hashtable) and arrays are faster than Hash table.replace the 2nd array with
for(i<arr2.lenght)
arr2[arr2[i]]= i //O(m) say
and then scan through the arr1 and then get it by:
arr2[arr1[i]]
Please comment
Did either of you actually try this?
(Though the idea of using an array on keys 1..n instead of a hash is brilliant.)
Lets say that Array2 is {3,2,4,5,1000}.
Will this logic work still?? What is the disadvantage with this solution??
arr2[arr2[i]]= i
let:
arr2[i] = X
doesn't this destroy the value of arr2[X] which is needed later?
If I step through the above example a collision occurs.
That said if arr1 is always guaranteed to be from 1..n, then we can use that as the "hash" map.
Thanks guys.
I am assuming we don't need arr2 later.The problem is to to return the index positions. The program sud run fine.
Instead we may use some type casting like this but we dont require it:
for(i<arr2.lenght)
arr2[(int)arr2[i]]= i //O(m) say
You can't write into array #2 as you are looping through it, because you will inevitably destroy information that you need later in the loop. What you can do is write into array #1 because you don't need it (as long as the input arrays are the same length and the first array is the first n natural numbers).
for (i = 1; i++; i <= length(arr2) {
arr1[arr2[i]] = i;
}
output(arr1);
How about this. This is O(N) but uses O(1).
int j = 0;
for(int i = 0 ; i < A.Length() , j < A.Lenght(); i++)
{
if(A[j] == B[i])
{
printf("%d ", i+1); ///position in B. A & B are arrays.
j++; i = 0; //reset i to continue loop.
}
}
you fucker !! don't you understand that your solution is O(n^2) .. people with such an IQ don't deserve to comment on such portals
Similar to the other question they asked you.
- Anonymous August 05, 2010