InMobi Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
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)
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
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.
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\}\}.
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.
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 ?
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