Programming Interview Questions 1 : Find the Pair in the Array

Earlier, I wrote about my ways of interviewing job candidates at my work place. For a very long I wanted to post some of the questions that I ask, so that it might be useful to people like me. Hence, here comes the first of the series. I hope the more such posts would come at regular interval  :-)

Question  : Given an array of unsorted integers of size N (a1, a2, a3.... aN) and another integer k. Find the pair of numbers within the array that would sum up to k. To make the problem simple, there is no duplicates of integers in the array.  

Assume the array as : [3,1,4,7,2,9,8,6] and the k=10
The pairs that would sum to 10 are :-  (3,7) , (1,9), (4,6) and (2,8)

Solution 1:
This is the most simple and non-optimal solution with time complexity of O(N²) :

Run an iteration for i = 0 To (N-1)
    Run an iteration for j = i+1 To (N-1)
        Check if (a[i]+a[j]) == k Then output a[i], a[j] as a pair
    Next j
Next i

Anyone with an average programming skill should be able to get this solution. Next, asking for an optimized solution (i,e. with better time complexity) will help to evaluate how the candidate think when there is a constraint in the problem. Many average programmers' mind get struck with this one solution and will never make an attempt to try if there is an optimized solution.

Solution 2:
Using an additional memory for a Key-Value data structure

Initiate a Map object
Run an iteration for i = 0 To (N-1)
    Check if (k-a[i]) is Available in the Map
         Then Output a[i], k-a[i] as a pair 
    Add a[i] to the Map 
Next i

Since this is a linear approach, the time complexity for this algorithm is O(N), but it uses an additional memory. In case if the size of the array is too big (say in trillions) then having a map to store all the array numbers will consume plenty of memory space. If the candidate comes up with this solution, asking for something better than O(N²) but with better space complexity, will be useful to further evaluate the candidate.

Solution 3 :
Sort the array using a better sorting algorithm (say Merge Sort - N LogN ) and then having two pointers from either side to move further and search for the pair, as in below algorithm

Sort the array
Set a frontCursor referring to 0th index of array
Set a backCursor referring to (N-1)th index of array
Run an when frontCursor < backCursor
     Calculate x = a[frontCuror] + a[backCursor]
     If (x == k) 
         Output a[frontCursor], a[backCursor] as pair
         Increment frontCursor by 1
         Decrement backCursor by 1
     Else If (x>k)
         Decrement backCursor by 1
         Increment frontCursor by 1
Next iteration

If you have something more to add, please post it in the comments section below.

No comments:

Post a Comment