Given two arrays, 1,2,3,4,5 .....
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Given two arrays, 1,2,3,4,5 .....
Question:
Given two arrays, 1,2,3,4,5 and 2,3,1,0,5 find which number is not present in the second array.
maybe an answer:
Sort array2>
Now binary search for every element in array1
>
Time complexity : N(log M) + MLogM => (N+M)logM>
N = no of elements in array1>
M = No of elements in array2>
maybe an answer2:
1. Take the first array as row, we name this array as A,
2. The second one as column, we name this array as B
3. we can make an m*n matrix S, S[i][j] is equal to 1 if A[i] = B[j], for giving two arrays, we can make following matrix:
0 0 1 0 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 1
5. check each row to see if it doesn't contain 1, the element in Array A corresponding this row is not present in the second array
(Continued on next question...)
Other Interview Questions
|