InMobi Interview Question for Software Engineer / Developers


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

- eugene.yarovoi August 22, 2013 | Flag Reply
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)

- OTR August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aks August 22, 2013 | Flag
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

- rajdeeps.iitb August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aks August 22, 2013 | Flag
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.

- Anonymous August 26, 2013 | Flag Reply
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\}\}.

- hoper April 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi April 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- hoper April 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi April 19, 2014 | Flag


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