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
Answer

Interview Answer

10 Answers

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> getPowerSet(Set s){
        Set> pset = new HashSet>();

        Object[] a = s.toArray();

        // Add the empty set
        Set subset = new HashSet();
        pset.add(new HashSet(subset));

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

    private void getPset(Object[] a, Set subset, Set> 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') {
                    subset.add(a[(n-1)-(m-1-j)]);
                }
            }
            power.add(subset);
        }

        return power;
    }

ellemeno on Nov 18, 2009
0

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

public List> powerset(final List set) {
        // If set is empty, just return an empty powerset.
        if(set.isEmpty()) return new ArrayList>();
        // 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> subset = this.powerset(set);
        // If the returned powerset is empty, add an empty set to it.
        if(subset.isEmpty()) {
            subset.add(new ArrayList());
        }
        // 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);
            sWithi.add(i);
            subset.add(sWithi);
        }
        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();
    powerset.add(new HashSet()); // Add the empty set
    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 < n; i++) {
        Object o = input[i];
        subset.add(o);
        powerset.add(new HashSet(subset));
        if ( i < 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 -> 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 >> b) & 1:
                print a[b],
        print

Chris on Apr 23, 2012
0

a little typo, should be l[b]

Chris on Apr 23, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.