Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void getSubset(int n, vector<char>& pset, vector<string>& out) {
string temp;
int i = 0,x;
while(n) {
x =n%2;
if(x)temp+=pset[i];
n=n/2;
++i;
}
out.push_back(temp);
}
int main()
{
char a[]={'a','b','c','d'};
vector<char> pset(a, a+sizeof(a)/sizeof(char));
int sz = pset.size(), end = sz*sz;
vector<string> out;
for(int i = 0;i<end;++i) {
getSubset(i, pset, out);
}
for(int i = 0;i<out.size();++i){
cout<<out[i]<<" ";
}
cout<<endl;
}
This is slightly modified version of permutation logic.
I/P : {a,b,c}
O/P : {},a, b, c, ab, ac, bc, abc
public class PowerSet {
private final String in;
public Permutations_1( final String str ){
in = str;
}
public void permute( StringBuilder out,int level,int lenght){
if( out.length() == lenght ){
System.out.println( out );
return;
}
for( int i = level; i < in.length(); ++i ){
out.append( in.charAt(i) );
permute(out,i+1,lenght);
out.setLength( out.length() - 1 );
}
}
public static void main(String[] args) {
String in = "abcd";
StringBuilder out = new StringBuilder();
int lenght = in.length();
Powerset p = new Powerset(in);
for(int i=0;i<=lenght;i++)
p.permute(out,0,i);
}
}
#include<iostream>
#include<vector>
using namespace std;
void PowerSet(int A[], vector<int> V, int i, int l, int N){
if(l==0){
cout<<"{";
for(int v=0;v<V.size();v++){
cout<<V[v]<<" ";
}
cout<<"}";
}
else
for(int t=i;t<N;t++){
V.push_back(A[t]);
PowerSet(A, V, t+1, l-1, N);
V.pop_back();
}
}
int main(){
vector<int> V;
int A[3] = {1, 2, 3};
for(int i=0;i<=3;i++){
PowerSet(A, V, 0, i, 3);
}
}
This is an iterative approach. We can similarly have a recursive approach by tweaking the code a little.
This is based on the definition of a power set (Wikipedia). A Power set is the union of all subsets of S containing a particular element as well as all subsets not containing that element. The code is based on the simple logic.
public class Test{
private List<List<String>> computePowerIterative(List<String> input){
List<List<String>> powerSet = new ArrayList<List<String>>();
powerSet.add(new ArrayList<String>());
for(int i=0;i<input.size();i++){
String item = input.get(i);
int numOfSetsWithoutItem = powerSet.size();
for(int j=0;j<numOfSetsWithoutItem;j++){
List<String>lst = powerSet.get(j);
List<String> lst1 = new ArrayList<String>();
lst1.addAll(lst);
lst1.add(item);
powerSet.add(lst1);
}
}
return powerSet;
}
private void printPowerSet(List<List<String>> powerSet){
for(List<String> lst : powerSet){
System.out.print("{");
for(String s : lst){
System.out.print(s);
}
System.out.print("}");
System.out.println();
}
}
public static void main(String[] args) {
List<String> input = new ArrayList<String>();
input.add("a");
input.add("b");
input.add("c");
input.add("d");
input.add("e");
Test test = new Test ();
List<List<String>> powerSet = test.computePowerIterative(input);
System.out.println("Size of power set " +powerSet.size());
test.printPowerSet(powerSet);
}
}
I used brute force approach with c++11. This is not optimal per say O(n^4) or so. But works. Since sets are not concerned with order, then all combinations (NOT permutations) are required. 1,2,3 == 3,2,1.
Compile with "g++ -std=c++11 testPowerSet.cpp -o power_set"
cat testPowerSet.cpp:
#include <stdio.h>
#include <stdint.h>
#include <set>
using std::set;
typedef set<int> int_set_t;
typedef set<int>::size_type int_size_type;
typedef set<int_set_t> int_power_set_t;
static int_set_t testSet = {1, 2, 3, 4, 5};
int_power_set_t GetPowerSet(const int_set_t &inSet)
{
int_power_set_t retSet;
int_set_t workSet;
int_set_t::const_iterator setIt;
int_set_t::const_iterator curIt;
const uint32_t maxSubSize = inSet.size() - 1;
uint32_t curSubSize = 0;
uint32_t sizeCnt = 0;
uint32_t curIdx = 0;
uint32_t setCnt = 0;
int32_t numSets = 0;
//Power set consist of
//Empty set
retSet.insert(workSet);
if(inSet.empty()) return retSet; //Nothing to do
//The set itself
retSet.insert(inSet);
//Each single item
//Each combination of items (NOT permutations)
workSet.clear();
curIdx = 0;
//For each element
for(setIt = inSet.begin();
setIt != inSet.end();
setIt++ ) {
//For each subset size
for(curSubSize = 1; curSubSize <= maxSubSize; curSubSize++) {
if(curSubSize == 1) { //Special case, just add single item
numSets = 1;
} else {
numSets = inSet.size() - curSubSize + 1 - curIdx;
//In the negative case, create 0 sets
numSets = (numSets < 0) ? 0 : numSets;
}
//Number of sets of this size
for(setCnt = 0; setCnt < numSets; setCnt++) {
//Every set is based on the current item
workSet.insert(*setIt);
curIt = setIt;
advance(curIt, setCnt+1); //Advance to correct offset
//Number of elements in this size set
for(sizeCnt = 1; sizeCnt < curSubSize; sizeCnt++) {
workSet.insert(*curIt);
curIt++;
}
retSet.insert(workSet);
workSet.clear();
}
}
curIdx++;
}
return retSet;
}
void PrintPowerSet(const int_power_set_t &powerSet)
{
int_power_set_t::iterator powerIt;
int_set_t::const_iterator setIt;
for(powerIt = powerSet.begin();
powerIt != powerSet.end();
powerIt++) {
printf("{ ");
for(setIt = powerIt->begin();
setIt != powerIt->end();
setIt++) {
printf("%d ", *setIt);
}
printf("}\n");
}
}
int main(int argc, char *argv[])
{
int_power_set_t powerSet;
powerSet = GetPowerSet(testSet);
printf("Obtained power set:\n");
PrintPowerSet(powerSet);
return 0;
}
// vim: softtabstop=4:shiftwidth=4:expandtab
Output:
$ ./power_set
Obtained power set:
{ }
{ 1 }
{ 1 2 }
{ 1 2 3 }
{ 1 2 3 4 }
{ 1 2 3 4 5 }
{ 1 3 }
{ 1 3 4 }
{ 1 3 4 5 }
{ 1 4 }
{ 1 4 5 }
{ 1 5 }
{ 2 }
{ 2 3 }
{ 2 3 4 }
{ 2 3 4 5 }
{ 2 4 }
{ 2 4 5 }
{ 2 5 }
{ 3 }
{ 3 4 }
{ 3 4 5 }
{ 3 5 }
{ 4 }
{ 4 5 }
{ 5 }
We can use bit mapping concept to make a subset.
For example, if we have the set like {a, b, c};
We will have no a, no b, no c, yes a, no b, no c, and so on until yest a, yes b, yes c.
public static Set<List<String>> getAllPowerSets(List<String> input) {
assert(input != null);
int maxNumOfSets = 1 << input.size();
int i = 0;
Set<List<String>> result = new HashSet<>();
while (i < maxNumOfSets) {
result.add(getEachSubSet(input, i));
i++;
}
return result;
}
private static List<String> getEachSubSet(List<String> input, int cutOff) {
int index = 0;
List<String> subSet = new ArrayList<>();
while(cutOff > 0) {
if ((cutOff & 1) == 1) {
subSet.add(input.get(index));
}
cutOff = cutOff >> 1;
index++;
}
return subSet;
}
We may use recursive approach to get power set
void getPowerSet(const vector<int>& input, vector<vector<int> >& powerSet)
{
if (input.empty() )
{
powerSet.push_back(vector<int>());
return;
}
vector<int> current;
getNextLevel(0, input, current, powerSet);
return;
}
void getNextLevel(int level, const vector<int>& input, vector<int>& curSet, vector<vector<int> >& powerSet )
{
if ( level == input.size() )
{
// reach the bottom level
powerSet.push_back(curSet);
return;
}
getNextLevel(level+1, input, curSet, powerSet); // exclude level'th item
curSet.push_back(input[level]);
getNextLevel(level+1, input, curSet, powerSet); // include level'th item
curSet.pop_back(); //restore the current set
}
This will return a set of sets in the "out" parameter.
void power_set(set<set<char> >& out, set<char>& ps) {
if (ps.empty()) {
out.insert(ps);
return;
}
char elem = *ps.begin();
ps.erase(ps.begin());
set<set<char> > temp;
power_set(temp, ps);
for (set<set<char> >::iterator i = temp.begin(); i != temp.end(); ++i) {
out.insert(*i);
set<char> temp_set(*i);
temp_set.insert(elem);
out.insert(temp_set);
}
}
backtracking
def power_set(target):
def _helper(target, length, index, tmp, ret):
if len(tmp) == length:
ret.append(list(tmp))
return
for i in range(index, len(target)):
tmp.append(target[i])
_helper(target, length, i + 1, tmp, ret)
tmp.pop()
ret = []
for i in range(1, len(target) + 1):
tmp = []
_helper(target, i, 0, [], tmp)
ret.extend(tmp)
return ret
Java 8 Impl:
public static void printPowerSet(int[] arr) {
if (arr == null) return;
int bitCounter = (int) Math.pow(2, arr.length);
IntStream.range(0, bitCounter).forEach(mask -> {
StringBuilder sb = new StringBuilder("{ ");
final int[] counter = {1};
IntStream.range(0, arr.length).forEach(i -> {
if ((mask & counter[0]) != 0) {
sb.append(arr[i] + " ");
}
counter[0] <<= 1;
});
System.out.println(sb.append("}").toString());
});
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void getSubset(int n, vector<char>& pset, vector<string>& out) {
string temp;
int i = 0,x;
while(n) {
x =n%2;
if(x)temp+=pset[i];
n=n/2;
++i;
}
out.push_back(temp);
}
int main()
{
char a[]={'a','b','c','d'};
vector<char> pset(a, a+sizeof(a)/sizeof(char));
int sz = pset.size(), end = sz*sz;
vector<string> out;
for(int i = 0;i<end;++i) {
getSubset(i, pset, out);
}
for(int i = 0;i<out.size();++i){
cout<<out[i]<<" ";
}
cout<<endl;
}
Objective C implementation based on combination approach
+(void) createPowerSetWithIndex:(int) index withMutableString:(NSMutableString *) mutableString withInputString:(NSString *) inputString{
if (index == inputString.length) {
NSLog(@"output %@",mutableString);
return;
}
//first choice we choose this character
NSString * stringChar = [inputString substringWithRange:NSMakeRange(index, 1)];
[mutableString appendString:[NSString stringWithFormat:@"%@,",stringChar]];
[self createPowerSetWithIndex:index+1 withMutableString:mutableString withInputString:inputString];
//pop it now
NSRange range = NSMakeRange([mutableString length]-2,2);
[mutableString replaceCharactersInRange:range withString:@""];
//second choice we never choose this character
[self createPowerSetWithIndex:index+1 withMutableString:mutableString withInputString:inputString];
}
+(void) createPowerSetForString:(NSString *) inputString{
[self createPowerSetWithIndex:0 withMutableString:[NSMutableString new] withInputString:inputString];
}
+(void) createPowerSetWithIndex:(int) index withMutableString:(NSMutableString *) mutableString withInputString:(NSString *) inputString{
if (index == inputString.length) {
NSLog(@"output %@",mutableString);
return;
}
//first choice we choose this character
NSString * stringChar = [inputString substringWithRange:NSMakeRange(index, 1)];
[mutableString appendString:[NSString stringWithFormat:@"%@,",stringChar]];
[self createPowerSetWithIndex:index+1 withMutableString:mutableString withInputString:inputString];
//pop it now
NSRange range = NSMakeRange([mutableString length]-2,2);
[mutableString replaceCharactersInRange:range withString:@""];
//second choice we never choose this character
[self createPowerSetWithIndex:index+1 withMutableString:mutableString withInputString:inputString];
}
+(void) createPowerSetForString:(NSString *) inputString{
[self createPowerSetWithIndex:0 withMutableString:[NSMutableString new] withInputString:inputString];
}
If the question is how to print a powerset, it can be done extremely simply. I will demonstrate by example.
- heorhi July 19, 2014Imagine you have set {a,b,c,d}: then each element of a powersent (i.e., subset) can be encoded with 4 bits, each bit showing if a corresponding element participates in a subset: 1011 encodes {a,c,d} and 0011 encodes {c,d}. All possible subsets can be found by looking through all possible combinations of bits. It can be done by simply counting from 0000 to 1111 and printing a corresponding subset for each number. You can see that it will encode all 2^4 subsets. You can straightforwardly extend it to any set of n elements.