Facebook Interview Question
Software Engineer / Developersassuming number of distinct integers is less than 32 (WLOG)
assign each value a bit position
create a mask for each of the exclusion rule set
generate subsets from original set (different n-bit values)
for mask in masks:
if value & mask == mask
then exclude, continue generation
print value
exponential:-( to generate all subsets
//Assume: The exclusion rules are converted into a vector of numbers where each number's binary representation tells us which numbers are in the exclusion set
e.g: {(a1,a3,a5), (a1,a2)} = {00010101, 00000011)
// Assume: We have n distinct numbers
vector<vector<int>> Subsets(int n, vector<int> E)
{
vector<vector<int>> subsets;
//Generate all subsets
for(int i=0;i< 1<<n;i++)
{
int violate = 0;
// Check if it violates an exclusion set
for(int j=0; j< E.size(); j++)
{
if(i&E[j] != 1)
{
violate = 1;
break;
}
}
if(!violate)
{
// i represents a valid subset
vector<int> sub;
for(int k=0;k<n;k++)
{
if(i & 1<<k == 1)
{
sub.push_back(k);
}
}
subsets.push_back(subset)
}
}
return subsets;
}
We can imagine the set {a1,a2,a3,..} like a graph where initially all nodes are connected with each other.This means that initially this is a complete graph. Now we check the exclusion set, and for all 2 nodes in the same exclusion set, we remove the edge that connects them.Now, the remaining graph is full with nodes that are connected only and only if they can be in the same graph. Now, in order to find a valid subset, we can run a Depth First search to find all connected components.Every connected component will be a valid subset according to the way we created the graph. Now, for any of this subsets, we must generate the subsets to find all the solutions. Final complexity O(2^N). I think this solution is more interesting than raw backtracking.
wonderful solution.....but just wondering wha if (a1, a2) is an invalid subset but (a1,a2,a3) is a valid subset.
wonderful solution.....but just wondering wha if (a1, a2) is an invalid subset but (a1,a2,a3) is a valid subset.
@bogdan:
Suppose the set is {a1,a2,a3} and the exclusion rule is {a1,a2}. Then the edge between a1,a2 will be deleted.Still a1,a2 is connected via a3.So DFS will generate the subset {a1,a2,a3}.Which is not valid!!!!!!!!!!
How about this sol.
Treat all points as nodes of graph. For each exclusion rule add edges between all elements of the exclusion set. Now run BFS and collect nodes into different components. Suppose number of Components = N. Now run a for loop of i between 1 to 2^N-1. This would give us a Bit Vector to generate different subsets. In the for loop look at the bit pattern of the i, i'th bit signifies that it includes the an element from i'th component. Iterate and print all the different subsets.
bogdan.cebere, your solution is correct. Just that insted of looking for strongly connected components, look out for cliques in the remaining graph. All the cliques will go into one valid set and then we can create subsets out of it. If there is no clique, then all the edges would correspond to valid subsets.
1, Treat the exclusion rules as the elements b1 ={a1, a3},b2= {a2, a4, a10} , find all non-null subsets {b1} {b2} {b1,b2}, O(2^|R|)
2, for each subsets, substitute b1 with every possible specific number, b1 => {a1}, {a2}, |b1| x |b2| ...
3. add {} empty set to the answer, which I think a valid subset.
how about this?
Start with 00000(of length of number of characters), print all permutations of it
Start with 10000, print all permutations.
and so on.
so you start with 2^i+1 and shift it to length of the string and call permutations on that.
For excluding just convert them to bit representation and directly compare them.
I think we cannot get rid of creating subsets for all integers of size N. So we are looking at a size of O(2^n).
The real trick is to help detect the wrong subsets.
1. Assign a prime number to each number in the given subset (a1->2, a2->3, a3->5 etc)
2. Create a product of the exclusion sets. Each product of unique prime numbers is unique.
3. When creating subsets, calculate the product of the items in the subset. If the product is divisible by any of the products of the exclusion sets, then it is invalid.
The extra complexity is of K where K is the number of exclusion sets.
static void
generate_valid_subset(int *a, int n, int curr_loc, int *form, int form_len, struct list_node **applicable_rules, int *exclusion_refs, struct exclusion_rule *rules)
{
struct list_node *curr;
int i, j;
for (;curr_loc < n; ++curr_loc) {
if (exclusion_refs[curr_loc] == 0) {
form[form_len++] = a[curr_loc];
// Output form 0..form_len-1
for (i = 0; i < form_len; ++i) {
printf("%d ", form[i]);
}
printf("\n");
curr = applicable_rules[curr_loc];
while (curr != NULL) {
i = curr->data;
curr = curr->next;
for (j = 0; j < rules[i].n; ++j) {
++exclusion_refs[rules[i].rule_elements[j]];
}
}
/* Recursive call can be done via stack. */
generate_valid_subset(a, n, curr_loc + 1, form, form_len, applicable_rules, exclusion_refs, rules);
/* clean-up*/
form_len--;
curr = applicable_rules[curr_loc];
while (curr != NULL) {
i = curr->data;
curr = curr->next;
for (j = 0; j < rules[i].n; ++j) {
--exclusion_refs[rules[i].rule_elements[j]];
}
}
}
}
}
int valid_subsets(int *a, int n, struct exclusion_rule *rules, int rules_count)
{
struct list_node **applicable_rule;
struct list_node *prealloc_nodes, *next_free;
int *exclusion_refs;
int *form;
int total_exclusions = 0, i, j, k;
applicable_rule = (struct list_node **)malloc(sizeof(struct list_node *) * n);
memset(applicable_rule, 0, sizeof(struct list_node *) * n);
exclusion_refs = (int *)malloc(sizeof(int) * n);
memset(exclusion_refs, 0, sizeof(int) * n);
form = (int *)malloc(sizeof(int) * n);
for (i = 0; i < rules_count; ++i) {
total_exclusions += rules[i].n;
}
prealloc_nodes = next_free = (struct list_node*)malloc(sizeof(struct list_node) * total_exclusions);
for (i = 0; i < rules_count; ++i) {
for (j = 0; j < rules[i].n; ++j) {
k = rules[i].rule_elements[j];
next_free->data = i;
next_free->next = applicable_rule[k];
applicable_rule[k] = next_free++;
}
}
generate_valid_subset(a, n, 0, form, 0, applicable_rule, exclusion_refs, rules);
free(applicable_rule);
free(exclusion_refs);
free(form);
free(prealloc_nodes);
}
could u tell us your definition for valid and invalid
- anonymous December 22, 2010