Ibibo Interview Question
Software Engineer / DevelopersTeam: Payu
Country: India
Interview Type: In-Person
Doubtful. Basically you want to find pairs satisfying K + bi = a where i is some integer. So bi = a - K. This amounts to asking to find all b that are factors of a - K.
Is there a way to build a data structure that retrieves all the elements it contains that are factors of a particular number in time proportional to the number of factors retrieved? I don't know for sure, though it seems difficult.
sorry, small correction :
1. Initialize an empty list.
2. For every integer a in input_array, check if a is present in the list. If so, print a, a-k.
3. Check if (a+k)%k is equal to k. if so, add a+k to the list. else, proceed with step 2
I almost reached same approach as you but how do you get rid of duplicates??
e.g.)
K = 2 (5, 3) (3, 5)
for each number a in the array, decompose the number a-k into the product of a series of prime numbers. e.g. a-k = 2^x * 17^y * 31^z
with this information, it takes relatively (but not strictly) constant time to figure out the complete set of integer U, such that a%u = k . simply mix and match all of the prime numbers.
save U as a hash map. Suppose the construction of U takes constant time C. then constructing U for every integer in the array takes time O(n*C) . after that, merge all of of the hash map into a big hash map. then, scan through the array one more time to find all the pairs.
the big savings here is that, you do not compare each pair of numbers any more.
We can achieve O(n.sqrt(n)).
1. Create boolean map for array. (map[i] = true only if i is present in array) => O(n)
2. For each element in array do this, array[i] = array[i]-k
3. Now iterate over the elements and ignore negative numbers
4. For each number, run a loop from 1 to sqrt(array[i]) (lets call this iterator j)
5. If array[i] % j = 0, then check map[j], if true, the required numbers are j and array[i]
Absent limitations on what the integers may be, you can't achieve less than O(n^2) for the simple reason that there may be O(n^2) distinct pairs that satisfy the criterion. Since you have to print all of them out, this needs at least O(n^2) time. If you want an example of an O(N^2) input, consider K = 0 and 1, 2, 4, 8, 16, 32, 64, ...
- eugene.yarovoi July 19, 2012