Google Interview Question: Write a program the generates... | Glassdoor

## Interview Question

Software Engineer Interview

# Write a program the generates the power set of a set of

numbers
Tags:
combinatorics, discrete, powerset

1

How about something like this? Running time is O(n!).

(Java)
/**
* The power set of S is the set of all subsets of S, including the empty
* set and S itself. It is parallel to the idea of all combinations of
* characters in a string.
*/
public Set&gt; getPowerSet(Set s){
Set&gt; pset = new HashSet&gt;();

Object[] a = s.toArray();

Set subset = new HashSet();

int n = s.size();
this.getPset(a,subset,pset,n,0);
return pset;
}

private void getPset(Object[] a, Set subset, Set&gt; pset, int originalSize, int currentSize){
for (int i = currentSize; i (subset));
if (i ();
}
}

ellemeno on Nov 17, 2009
1

That's a clever way to do it! Though good look thinking that up on the spot.

What i did was, assuming the set has n elements:
for (i; from 0; to (2^n)-1)
{
generate binary represenation of i padded to n bits. (e.g if n=8, and i =4, representation would be 00100000). Call this representation "bitmap"

for (j; from 0; to bitmap.length)
{
if bitmap[j]==1: add set[j] to a tempset
}
add tempset to a global array of sets

}
return that global array of sets

Note that this has exponential complexity which i believe (but am not sure) is better than factorial complexity

OP on Nov 17, 2009
0

OP, I think yours is better, and easier to understand too. :)

O(n*2^n) is better than O(n!) as n grows.

Thanks for posting the question.

ellemeno on Nov 18, 2009
1

Here's the Java version of your algorithm if you don't want to explicitly pad:

Set powerset(Set set) {

Set power = new HashSet();
Object[] a = set.toArray();
int n = a.length;
int maxCount = (int)Math.pow(2,n);
for (int i = 0; i = 0; j--){
if (c[j] == '1') {
}
}
}

return power;
}

ellemeno on Nov 18, 2009
0

Using recursion and run in O(n2^n).

public List&gt; powerset(final List set) {
// If set is empty, just return an empty powerset.
if(set.isEmpty()) return new ArrayList&gt;();
// Pop the first element as a candidate for composition.
final Integer i = set.remove(0);
// Get powerset of the set without the candidate.
final List&gt; subset = this.powerset(set);
// If the returned powerset is empty, add an empty set to it.
if(subset.isEmpty()) {
}
// For all the existing sets in the powerset without the candidate,
// add the all combination sets of existing sets plus the candidate
// to the powerset.
final int length = subset.size();
for(int j = 0; j s = subset.get(j);
final List sWithi = new ArrayList(s);
}
return subset;
}

neakor on Nov 18, 2009
0

I finally got my head around a clearer version... credits to John Mongan et al:

public Set getPowerset(Set set) {
Set powerset = new HashSet();
getPset(set.toArray(), new HashSet(), powerset, set.size(), 0);
return powerset;
}

private void getPset(Object[] input, Set subset, Set powerset, int n, int start) {
for (int i = start; i &lt; n; i++) {
Object o = input[i];
if ( i &lt; n-1) {
getPset(input, subset, powerset, n, i+1);
}
subset.remove(o);
}
}

Time for n = 16 for binary version: 10089 ms. Items: 65536.
Time for n = 16 for recursive version: 9379 ms. Items: 65536

ellemeno on Nov 19, 2009
1

ellemeno dude if you don't ace your google interview, I'm going to be very disappointed :)

Good luck!

vic on Dec 17, 2009
1

A little theory: A power set is defined as all subsets of a set S. A specific k-subset of set S will contain n!/(k!(n-k)! elements ( also known as nCk or n Choose k. The lower bound on the operations you have to perform to generate nCk elements is nCk. Since we need all n subset to generate the powerset, total number of operations is the sum of all n choose k for k = 0 to n == 2^n -&gt; lower bound on the algorithm

A little code in Python

def powerset(iterable):
from itertools import combinations
s = list(iterable)
return [ combinations(s, r) for r in range(len(s)+1) ]

if you can't import the combinations function, suggest you'll implement one yourself. Give a reasonable explanation of how you would do it.

George on Jun 19, 2010
0

Another Python (less pythonic) example:

def gen(l):
n = len(l)
for i in range(0,pow(2,n)):
for b in range(0, n):
if (i &gt;&gt; b) &amp; 1:
print a[b],
print

Chris on Apr 23, 2012
0

a little typo, should be l[b]

Chris on Apr 23, 2012