Interview Questions

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