Oracle Interview Question: Given array of n integers and... | Glassdoor

Interview Question

Software Development Engineer Interview Hyderabad (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

3 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
0

Assume K is the element sum to find out. Sort the list. Have 2 pointer to the array. Start pointer to point to the first index of the array. End pointer to point to the index which is equal to number K.
1. Add the values of start index and end index.
2. If sum is equal to K, then we have got the pair.
3. If sum is greater than K, decrement the End pointer.
    If sum is lesser than k, increment the Start Pointer.
4. Repeat from step 1 till Start pointer and End pointer collide.

Harsha Jayaramachar on Nov 10, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.