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