Ibibo Interview Question for Software Engineer / Developers


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

- eugene.yarovoi July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi July 20, 2012 | Flag
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)

- puzzlek July 20, 2012 | Flag Reply
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.

- siva July 20, 2012 | Flag Reply
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

- siva July 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- nsdxnsk July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Same here, I don't get it

- ethioer July 21, 2012 | Flag
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.

- micropie May 12, 2013 | Flag Reply
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.

- PB May 19, 2014 | Flag Reply
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]

- revs January 31, 2016 | Flag Reply
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.

- loveCoding July 19, 2012 | Flag Reply
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)

- Meena July 20, 2012 | Flag Reply
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.

- axecapone July 19, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More