## InMobi Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: India
Interview Type: In-Person

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

This problem is called "set cover", and is a classic NP-complete problem. There are approximation algorithms and heuristics that you could employ. If you only need to solve this for very small inputs, you could just do it by trying every combination (try all combinations of size k before trying any of size x, if k < x).

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

Take each element of array find in each Set, Store the result in a hasmap in form HashMap<SetID,SizeOfMissingNumberOfArrayElement>. Sort the Map based on value in ascending Order. put the missing element in other sets, and if found print the result. there can be many such sets if same value is present in different sets but I am not counting that scenario here. In terms of complexity, if array size is m, and there are k sets having each n elements.O(nk)

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

Didn't get it. Would u like to run through the example?

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

Dynamic Programming can be used in this scenario.
A B C D
----------------------
A
B
C
D

start filling up from bottom till you get a combination which satisfies the condition

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

doesn't sound right as result can be A+B+C also

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

Here's another approach:
1. Hash the values of the target set.
2. Check if a given set contains the entire range of values, if yes return this set, otherwise save the number of values that are present in a an array (let's call this new array NumCommonElement whose ith element is the number common elements between ith set annd the target set).
3. We find a particular set that has all these key in previous step, then we are done as it is the minimum number of sets to cover the target set.
4. If not, then apply the Subset Sum algorithm on NumCommonElement (its entries are the number of common elements between the target set and the ith set) array with target sum as the length of the target set. Return the combination with shortest length.

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

if you say its the set cover problem then answer A +C+D

check example @ http_://en.wikipedia.org/wiki/Set_cover_problem

Given a set of elements \{1,2,...,m\} (called the universe) and a set S of n sets whose union equals the universe, the set cover problem is to identify the smallest subset of S whose union equals the universe. For example, consider the universe U = \{1, 2, 3, 4, 5\} and the set of sets S = \{\{1, 2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 5\}\}. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: \{\{1, 2, 3\}, \{4, 5\}\}.

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

No, it's the set cover problem alright. It's just here we have a small variation: we should not consider elements that are not in the "array to find". In other words, if a set contains elements not in the "array to find", ignore them, since those elements have no effect on the answer.

Typical set cover is trivially poly-time reducible to this variation (pick an "array to find" that contains the whole universe), and this variation is poly-time reducible to set cover just by deleting the irrelevant elements.

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

thank you for the clarification. i was very confused with the question and hence looked up the cover problem.

so the qns is to find minimun of sets whose union gives the array_2_find ?

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

Or a superset of the array_to_find. The problem asks you to find the sets whose union contains all the elements in array_to_find, such that the number of sets is minimized.

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.