## PayPal Interview Question

Software Engineer / DevelopersInsert all the elements of the first array into the hash table.

Now take each element from the second array subtract from the sum and then look for that number in hash

If found then they are the pair

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

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

Algo:

1. move the contents of both the arrays to a single array

2. sort this array

3. navigate to that section of the array where -ve moves over to +ve (use the tip that n+(-n)=0). - have two pointers x and y moving in opposite direction to each other

4. if x and y are pointing to absolute of the same number, print the numbers as they add up to 0

5. else move either of that pointer which is pointing to the smaller of the abs of the current number

6. repeat step (4) until x and y are within the range of the array index

Tips:

- use an efficient algo to sort the array

- if there is a 0 which means x & y point to the same number. in this case, move x & y one step away from each other (0 added to any non-zero number will not yield a 0 anyway)

i think there is no need of hash table u can pick a number from first array and serarch for its negative in other arry.. it will run in o(nlogn) time

- ankur August 14, 2012