|
159. Given array of n integers and given a number X .......
Microsoft Interview Questions and Answers
(Continued from previous question...)
159. Given array of n integers and given a number X .......
Question:
Given array of n integers and given a number X, find all the unique pairs of elemens (a,b), whoose some is equal to X.
maybe an answer:
Pseudo code
1) Partition the set by n/2. All Elements N/2 and below on the left. All Elements > N/2 on the right. (Possible in O(n))
2) Put all elements in left in a hash map ensuring no duplicates. (keep a int countN/2 = 0, on one fine update to 1 and on a pair update to 2. Output pair(n/2,n/2) dis regard any other n/2
3) For all elements on the right basically > n/2 check for n - element in the hashmap. If exists ouput pair and remove element from hashmap.
(Continued on next question...)
Other Interview Questions
| 