Interview Question

Software Development Engineer Interview Hyderābād (India)

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.
data structures

Interview Answer

2 Answers


Let arr be the given array.
And K be the give sum

for i=0 to arr.length - 1 do
  hash(arr[i]) = i // key is the element and value is its index.

for i=0 to arr.length - 1 do
  if hash(K - arr[i]) != i // if K - ele exists and is different we found a pair
    print "pair i , hash(K - arr[i]) has sum K"

Interview Candidate on Jan 18, 2012

Using hashmap is great to get O(N) time complexity with O(n) space cost, however, if no additional memory is recommended, sort the list (O(nLogn)) and using a simple algorithm (O(n)) to find all pairs demoed in this video:

Anonymous on Mar 19, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.