Oracle

www.oracle.com

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.
Tags:
data structures
Answer

Interview Answer

2 Answers

1

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.
end-for

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"
  end-if
end-for

Interview Candidate on Jan 18, 2012
1

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:
http://youtu.be/3VBjhiKUtmE

Anonymous on Mar 19, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.