## Ibibo Interview Question for Software Engineer / Developers

• 0

Team: Payu
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

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, ...

Comment hidden because of low score. Click to expand.
0

Yes, but can you do O(n+S) where S is the number of such pairs?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. sort the array first, O(nlgn)
2. we can filter out all the numbers which are less and equal than K. O(n)
3. let's say the number of rest elements is m (m should be less and equal than n). Find the pairs in the rest.t O(m^2).

The worst case is O(n^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why cant we follow the same approach as do to find (a,b) where the sum is =k.

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. Else, check if (a+k)%k is equal to k. if so, add a+k to the list.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

I almost reached same approach as you but how do you get rid of duplicates??

e.g.)
K = 2 (5, 3) (3, 5)

Comment hidden because of low score. Click to expand.
0

Same here, I don't get it

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

split nos in 2 groups based on rightmost set bit in k. lets call them g1 and g2. now check for a % b = k where a belongs to g1 and b to g2. worst case is still o(n2) but avg case is quite good.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Worst case will always be O(n^2).... Unless some range is mentioned for input array.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

1. Element > k and Element =< K move to two seperate arrays
2. Then do % on elements of the arrays. do both a%b and b%a

This will be less than O(n^2)

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Sort the array in O(nlogn).

1. If remainder is K, then b >= K + 1
2. For a given b that meets the criterion 1,
2.1 Find (K + ib) for i=0,1,2,3,4 such that K+ib < max of the array. Each (K + ib, b) is a solution.
2.2 Increment b by one and repeat step 2.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.