|
187. Given array of integers and a int variable say X. ......
Microsoft Interview Questions and Answers
(Continued from previous question...)
187. Given array of integers and a int variable say X. ......
Question:
Given array of integers and a int variable say X. Need to find out all unique pairs from array which sums to X.
for e.g. arr[] = {1,2,3} , X=4
output - (1,3) (3,1)
maybe an answer:
1. A[n] array and SUM .Take temp array B[n]
2. for each i=0 to n-1
if A[i] > SUM/2
B[i] = SUM - A[i]
else
B[i] = A[i]
3. Now B[n] array contains elements <= SUM/2 .
4. if B[n] contains duplicate element, then B[i] and SUM-B[i] elements gives SUM of two elements.
else
A[n] does not contains two such numbers to give SUM.
5. Time complexity o(n) & Space complexity O(n)
6. The above logic is Problem reducing i.e finding Two numbers sum problem to duplicate problem
maybe an answer2:
def fun(X):
uniquePairDict = {}
for element in arr:
rest = X - element
if rest in arr:
pairString = "(" + element + "," + rest + ")"
if pairString not in uniquePairDict:
uniquePairDict[pairString] = 0
print uniquePairDict
(Continued on next question...)
Other Interview Questions
| 