Software development engineer in test - Given a randomly filled array of N numbers and a number X...?
Software Design Engineers in Test SDET FAQ
(Continued from previous question...)
22. Software development engineer in test - Given a randomly filled array of N numbers and a number X...?
Question:
Given a randomly filled array of N numbers and a number X . print all pair inside array such that they sum up to X.
Answer:
1. sort the array
2. keep two pointers one at the start of the array and other at thh end of the array .
3. check
if sum of the value pointed by those pointer is equal to X then pritn the pair and move both pointer towards each other.
else if sum of the value is less then X then move first pointer towards end of the array by one step.
else move 2nd pointer towards start of the array by one step.
4. goto step 3 till first pointer index value is less than the 2nd pointer index value.
5.END
.. step 2-4 takes only O(n) .. since we are having only one pass over the array.
but step 1 takes nlogn time bcoz of sorting.without using any extra space.
so total complexity is O(nlogn) time and O(1) space.
(Continued on next question...)
Other Interview Questions
|