## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 vote

If the question is how to print a powerset, it can be done extremely simply. I will demonstrate by example.
Imagine 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.

Comment hidden because of low score. Click to expand.
0

#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;
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

what is the question?

Comment hidden because of low score. Click to expand.
0

I believe the question was to generate a power set

Comment hidden because of low score. Click to expand.
1
of 1 vote

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);

}

}

Comment hidden because of low score. Click to expand.
0

Can you please explain the algorithm? I tried to do a dry run but its very confusing and I got lost in the recursion stack. Any help on algorithm would be greatly appreciated

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>>();
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>();
}
}
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>();
Test test =  new Test ();
List<List<String>>  powerSet = test.computePowerIterative(input);
System.out.println("Size of power set " +powerSet.size());
test.printPowerSet(powerSet);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
//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 }

Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive approach:
1- Take out first element.
2- Compute power set of the rest
3- Duplicate each element of above set and add the first element to the duplicate.
4- The above set is what we want

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) {
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) {
}
cutOff = cutOff >> 1;
index++;
}
return subSet;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Java 8 Impl:

public static void printPowerSet(int[] arr) {
if (arr == null) return;

int bitCounter = (int) Math.pow(2, arr.length);

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());
});
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

+(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];

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

array = {1,2,3,4}
power_set=[[]]
for i in array:
for j in power_set:
power_set= power_set + [list(j)+[i]]
print(power_set)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.