## Facebook Interview Question for Interns

Country: India
Interview Type: Phone Interview

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

import java.lang.*;
import java.util.*;
import java.math.*;
public class powerset_without_repeating {
public static void main(String[] args)
{
int a[]={1,2,2};
int n=a.length;
int cf=(int)Math.pow(2,n);
List<String>l=new ArrayList<String>();
for(int c=0;c<cf;c++){
String s="";
for(int j=0;j<n;j++){
int x=c&(1<<j);
if(x!=0){
s+=a[j];

}
}
if(!l.contains(s)){
}
}
for(String st:l){
System.out.println(st);
}

}

}

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

Clever solution. The strategy is to use a bitmask pattern to generate all the combinations. I believe it can be optimized somewhat by removing the duplicate test from the loops and instead performing a one time addAll to a Set<String> once the loops have completed.

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

Nifty technique, but this won't work for an element count > than 32 (64 for 64bit integer architectures) right?

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

"set of integers with repeated occurences of elements" this is mathematically incorrect. A set does not have repeated elements. A Multiset does.

Anyway, we can shrink the input in pairs: (number, n_occurrences) and generate the power set with a recursive function. Sample code in C++:

``````void PowerSet(int i, const vector<pair<int,int> >& vo, vector<int>& cur) {
if (i == vo.size()) {
if (cur.size() == 0)
cout << "NULL" << endl;
else {
for (size_t i = 0; i < cur.size(); i++)
cout << cur[i] << " ";
cout << endl;
}
} else {
size_t cur_size = cur.size();
PowerSet(i+1, vo, cur); // don't use any of these numbers
for (size_t k = 1; k <= vo[i].second; k++) {
cur.push_back(vo[i].first); // use this number k times
PowerSet(i+1, vo, cur);
}
cur.resize(cur_size); // get cur vector to previous size
}
}
void PowerSet(int v[], int n) {
sort(v, v+n);
vector<pair<int,int> > voccur;
for (int i = 0; i < n ; i++) {
int num = 1;
for (; i+1 < n && v[i] == v[i+1]; i++)
num++;
voccur.push_back(make_pair(v[i], num));
}
vector<int> cur_set;
PowerSet(0, voccur, cur_set);
}``````

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

can you write psuedocode instead, so that we can understand what the approach is.

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

It looks like powerset problem!

for each element of input :
If it is visited for the first time, just add it to all sets that has been added to powerset.

else check hashmap to find number of this element that has been visited, then add new element to set(s) that has exactly this number of duplication.

``````public static void powerSet(ArrayList<Integer> input) {
ArrayList<ArrayList<Integer>> powerSet = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> set = new ArrayList<Integer>();
HashMap<Integer, Integer> hm = new HashMap<>();
int focoused;
int counter=0,dupCounter;
if (input.isEmpty())
System.out.println("null");
else {
while (!input.isEmpty()) {
focoused = input.remove(0);
int psize = powerSet.size();
counter=0;
dupCounter=0;
{
if(hm.containsKey(focoused))
{
hm.put(focoused, hm.get(focoused)+1);
dupCounter = hm.get(focoused);
for (int i = 0; i < psize; i++) {
for(Integer ii : powerSet.get(i))
if(ii==focoused)
counter++;
if(counter==dupCounter-1)
{
powerSet.get(i).contains(focoused);
set = (ArrayList<Integer>) powerSet.get(i).clone();
}
counter=0;
}
}
else{
hm.put(focoused, 1);
for (int i = 0; i < psize; i++) {
set = (ArrayList<Integer>) powerSet.get(i).clone();
}
}
}
}
System.out.println(powerSet.toString());
}
}``````

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

My complete code is as follows.

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

void printSet(vector<int>& iset){
if(iset.size() == 0){
printf("NULL");
return;
}

printf("{");
for(int j = 0; j < iset.size(); j++){
printf("%d%s", iset[j],
j < iset.size() - 1 ? ", " : "");
}
printf("}");
}

int genPowerSetIdx(vector<int> &pset, int newIdx, vector<vector<int>> &result)
{
int numRepeat = 1;
int value;
int size = result.size();

assert(newIdx < pset.size());

value = pset[newIdx];
for(int i = newIdx + 1; i < pset.size(); i++){
if(pset[i] != value)
break;
numRepeat++;
}

for(int i = 0; i < size; i++){
vector<int> newSet = result[i];
for(int j = 0; j < numRepeat; j++){
newSet.push_back(value);
result.push_back(newSet);
}
}

return newIdx + numRepeat;
}

void genPowerSet(vector<int> &pset, vector<vector<int>> &result)
{
sort(pset.begin(), pset.end());

result.push_back(vector<int>{});
for(int i = 0; i < pset.size(); ){
i = genPowerSetIdx(pset, i, result);
}

return;
}

int main()
{
vector<int> pset;
vector<vector<int>> result;
pset = {1, 2, 2};

genPowerSet(pset, result);

printf("{");
for(int i = 0; i < result.size(); i++){
vector<int> &iset = result[i];
printSet(iset);
if(i < result.size() - 1)
printf(", ");
}
printf("}");
}``````

result:

``{NULL, {1}, {2}, {2, 2}, {1, 2}, {1, 2, 2}}``

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

``````void power_set(vector<int>& v, vector< vector<vector<int> > >& res){
res.push_back(vector<vector<int> >(1, vector<int>()));
if(v.size() == 0){
return;
}
res.push_back(res[0]);
res.back().push_back(vector<int>(1,v[0]));
if(v.size() == 1)
return ;
for(int i = 1; i < v.size(); i++){
int start = 0;
res.push_back(res.back());
if(v[i] == v[i-1]) start = res[res.size()-3].size();
vector<vector<int> > tmp = res[res.size()-2];
for(int j = start;j < tmp.size(); j++){
tmp[j].push_back(v[i]);
res.back().push_back(tmp[j]);
}
}``````

}

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

js code

``````function toCountMap(array) {
var map = {};
array.forEach(function (item){
if(item in map) {
map[item]++ ;
} else {
map[item] = 1;
}
});
return map;
}
function fromCountMap(map){
var buff = [];
for(var key in map){
var count = map[key];
for(var i=0;i<count;i++) {
buff.push(key);
}
}
return buff;
}

function cloneMap(map){
var clone = {};
for(var key in map) {
clone[key] = map[key];
}
return clone;
}

function allSubSet(map) {
var buff = [];
var numbers = [];
for(var number in map) {
numbers.push(number);
}

function r(index, tempMap) {
var n = numbers[index];
var count = map[n];

if(index >= numbers.length - 1 ) {
for(var c=0;c <= count;c++) {
var cMap = cloneMap(tempMap);
cMap[n] = c;
buff.push(cMap);
}
} else {
for(var c=0;c <= count;c++) {
var cMap = cloneMap(tempMap);
cMap[n] = c;
r(index+1, cMap);
}
}
}
r(0, {});
return buff;

}

function listAllSubArray(array){
return allSubSet(toCountMap(array)).map(fromCountMap);
}

// test code
JSON.stringify(listAllSubArray(["a", "b", "b", "c"]))``````

complexity O(2^k) where k is count different values

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

Can we assume that the input set is sorted and can contain duplicates as in S={1,2,2} instead of S={2,1,2}?

If we can assume so, the solution becomes simpler:
To generate a power set of a given a set of length n
1) Generate sets of size 0 to n.
Use the permutation/ combination algorithm for each sizes to generate the sets.
2) When doing so, you just need to remember the previously generated set.
For example, when generating sets of size 2, I would get {1,2} and {1,2} twice right after each other since they are sorted. So, I just record the previously generated set, compare with the currently generated set. If the set is different, print it.

Running time - 2^n
Space - Constant

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

ssds

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

python solution

``````from collections import defaultdict

seen = defaultdict(int)
def powerset(arr):
if len(arr) == 0: return [[]]

val      = arr[0]
sets     = powerset(arr[1:])
new_sets = []
for s in sets:
count = len([x for x in s if x == val])
if count == seen[val]:
new = s[:]
new.append(val)
new_sets.append(new)
seen[val] += 1
sets.extend(new_sets)
return sets``````

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

import java.util.Scanner;
class ARR
{
public static void main(String a[])
{
int m,s;
int k=0;
int arr[]=new int[5];
int temp[]=new int[5];
System.out.println("enter values for array");
Scanner sc=new Scanner(System.in);
for(int i=0;i<5;i++)
{
arr[i]=sc.nextInt();
}
for(int i=0;i<5;i++)
{
int f=0;
for(int j=i-1;j>=0;j--)
{
if(arr[i]==arr[j])
{
f=1;
break;
}
}
if(f==0)
{
temp[k]=arr[i];
k++;
}
}
for(s=1;s<=k;s++)
{
int i;
for( i=0;i<s;i++)
{System.out.print("{");
System.out.print(temp[i]);
for(int j=i+1;j<s;j++)
{
System.out.print(","+temp[j]);
}

System.out.println("}\n");
}
}
}
}

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

import java.util.Scanner;
class ARR
{
public static void main(String a[])
{
int m,s;
int k=0;
int arr[]=new int[5];
int temp[]=new int[5];
System.out.println("enter values for array");
Scanner sc=new Scanner(System.in);
for(int i=0;i<5;i++)
{
arr[i]=sc.nextInt();
}
for(int i=0;i<5;i++)
{
int f=0;
for(int j=i-1;j>=0;j--)
{
if(arr[i]==arr[j])
{
f=1;
break;
}
}
if(f==0)
{
temp[k]=arr[i];
k++;
}
}
for(s=1;s<=k;s++)
{
int i;
for( i=0;i<s;i++)
{System.out.print("{");
System.out.print(temp[i]);
for(int j=i+1;j<s;j++)
{
System.out.print(","+temp[j]);
}

System.out.println("}\n");
}
}
}
}

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

import java.util.Scanner;
class ARR
{
public static void main(String a[])
{
int m,s;
int k=0;
int arr[]=new int[5];
int temp[]=new int[5];
System.out.println("enter values for array");
Scanner sc=new Scanner(System.in);
for(int i=0;i<5;i++)
{
arr[i]=sc.nextInt();
}
for(int i=0;i<5;i++)
{
int f=0;
for(int j=i-1;j>=0;j--)
{
if(arr[i]==arr[j])
{
f=1;
break;
}
}
if(f==0)
{
temp[k]=arr[i];
k++;
}
}
for(s=1;s<=k;s++)
{
int i;
for( i=0;i<s;i++)
{System.out.print("{");
System.out.print(temp[i]);
for(int j=i+1;j<s;j++)
{
System.out.print(","+temp[j]);
}

System.out.println("}\n");
}
}
}
}

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

``````static List<int[]> AllSets(int[] a)
{
return AllSets(a, 0, new List<int>()).ToList();
}

static IEnumerable<int[]> AllSets(int[] a, int i, List<int> curr)
{
if (i == a.Length)
{
yield return curr.ToArray();
}
else
{
foreach(var s in AllSets(a, i + 1, curr))
{
yield return s;
}

foreach(var s in AllSets(a, i + 1, curr))
{
yield return s;
}

curr.RemoveAt(curr.Count - 1);
}
}``````

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

``````public class PowerSet {

static void go(int index, int [] inp,String out) {
if( index == inp.length) return;
int pre = -1;
for(int i=index;i<inp.length;i++) {
String _o = out;
if(pre != inp[i]) {
if(out.equals("")) _o +=  inp[i];
else _o +=","+inp[i];
System.out.println(_o);
go(i+1,inp,_o);
pre=inp[i];
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] ip  = {1,2,2};
Arrays.sort(ip);
go(0, ip, "");
}

}``````

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

C solution:

``````#include <stdio.h>
#include <math.h>

void print_subset(int *org_set, unsigned int set_map)
{
unsigned int i = 0;

printf ("{");

for (i = 0; set_map; i ++)
{
if (set_map & 0x1)
{
printf ("%d,", org_set[i]);
}
set_map >>= 1;
}
printf ("\b}");
}

int main (int argc, char *argv[])
{
int org_set[] ={1,2,3, 9,300,56, 7, 90};
unsigned int set_map = pow(2,sizeof(org_set)/sizeof(int));

unsigned int i = 0;

printf ("The number of subset is : %d\n", set_map);

printf ("{NULL}\n");

for (i = 1; i < set_map; i ++)
{
print_subset (org_set, i);
printf ("\n", i);
}

return 0;
}``````

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

what the logic> ? how does it prevent {2} coming twice in :

{1,2,3,2}

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

``````import java.util.ArrayList;
import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class PowerSet {

public static void main(String[] args) {
int []  ns = {0, 2, 1, 2};
System.out.println(powerSet(ns).toString());
}
public static Set<ArrayList<Integer>> powerSet(int [] ns){
AListComparator comp = new AListComparator();
Set <ArrayList<Integer>> all = new TreeSet<ArrayList<Integer>>(comp);

ArrayList<Integer> al = new ArrayList<Integer>();
perm(0, ns, all, al);
return all;
}

private static void perm(int size, int [] ns, Set<ArrayList<Integer>> all, ArrayList<Integer> al){
for(int i = size; i < ns.length; i++ ){
ArrayList<Integer> tal = new ArrayList<Integer>();
if( al != null )

ArrayList<Integer> tal2 = new ArrayList<Integer>();
//And further processing.
perm(i + 1, ns, all, tal2);
}
}

}
class AListComparator implements Comparator<ArrayList<Integer>>{

public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
if(o1 == o2){
return 0;
}else if ( o1 == null && o2 != null){
return -1;
}else if ( o1 != null && o2 == null ){
return 1;
}else if ( o1.size() < o2.size() ){
return -1;
}else if ( o1.size() > o2.size() ){
return 1;
}
for( int i = 0 ; i < o1.size(); i++ ){
if( o1.get(i) > o2.get(i))
return 1;
else if ( o1.get(i) < o2.get(i))
return -1;
}
return 0;
}
}``````

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

Look similar to oj.leetcode.com/problems/subsets/

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

the key thing is that if the inputs are sorted.
we should skip expending the powerset from current element, if it has the same value as previous.

``````vector<vector<int>> powersets(vector<int> &num)
{
vector<vector<int>> ret;
vector<vector<int>> vv;
vector<int> v;
vv.push_back(v);
ret.push_back(v);

vector<int> ends;
ends.push_back(-1);
for(int i=0; i<num.size(); i++)
{
vector<vector<int>> nvv;
vector<int> nends;
for(int j=0; j<vv.size(); j++)
{
vector<int> v = vv[j];
int pre = -1;
for(int k=ends[j]+1; k<num.size(); k++)
{
if (pre >= 0 && num[k] == num[pre]){
continue;
}
pre = k;
vector<int> nv(v);
nv.push_back(num[k]);
nvv.push_back(nv);
nends.push_back(k);
ret.push_back(nv);
}
}
vv = nvv;
ends = nends;
}
return ret;
}``````

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

This code will be ok.

``````{
void Trace(std::vector<std::vector<int> > &rs, std::vector<int> & v, std::vector<int> & cnt, std::vector<int> & path, int k) {
rs.push_back(path);
for (int i = k; i < v.size(); i++) {
if (cnt[i] > 0) {
cnt[i]--;
path.push_back(v[i]);
Trace(rs, v, cnt, path, i);
path.pop_back();
cnt[i]++;
}
}
}

std::vector<std::vector<int> > PSet(std::vector<int> & num) {
std::map<int, int> tmap;
for (int i = 0; i < num.size(); i++) {
if (!tmap.count(num[i])) tmap[num[i]] = 0;
tmap[num[i]]++;
}
std::vector<int> v;
std::vector<int> cnt;
for (std::map<int, int>::iterator i = tmap.begin(); i != tmap.end(); i++) {
v.push_back(i->first);
cnt.push_back(i->second);
}
std::vector<std::vector<int> > rs;
std::vector<int> path;
Trace(rs, v, cnt, path, 0);
return rs;
}``````

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

We map input into set of form <x : count(x)>. Since each x can be taken from 0 to count(x) times we have total

``Prod(count(x) + 1) for every distinct x``

different subsets.
We can enumerate this subsets using value system with variable base, using same mask approach as in regular subset enumeration. But in our case, i-th digit of mask indicating how many times we peek i-th element of our set (in fact, in regular subset enumeration we do the same thing).
Here is sample code in C#:

``````static IEnumerable<List<int>> AllSubsets(int[] arr)
{
// next 2 steps can be done in linear time using hash table. here i use LINQ for short
var items = arr.Distinct().ToArray(); // get distinct items
var count = items.Select(x => arr.Count(k => k == x) + 1).ToArray(); // get their counts

Array.Sort(items, count); // for estetic purposes

int resSize = count.Aggregate(1, (x, y) => x * y); // each number k can be taken from 0 to count(k) times, so it is |Prod(count(k)+1) for each k| subsets in total
for (int i = 0; i < resSize; i++)
{
var res = new List<int>();
for (int p = 0; p < items.Length; p++)
{
for (int c = mask % count[p]; c > 0; c--) res.Add(items[p]); // here c is p-s digit in mask
}
yield return res;
}
}``````

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

Sets make this easy in python

``````def powerset(s):
if len(s)==0:
return [[]]
nxt=powerset(s[1:])
return map(lambda l:[s[0]]+l ,nxt)+nxt

def uniqPset(s):
return set(map(tuple,powerset([1,2,2])))``````

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

Sets make this easy in python

``````def powerset(s):
if len(s)==0:
return [[]]
nxt=powerset(s[1:])
return map(lambda l:[s[0]]+l ,nxt)+nxt

def uniqPset(s):
return set(map(tuple,powerset([1,2,2])))``````

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

``````void print(vector<int> mySet) {

vector<int> solution(mySet.size());
vector<int> prevSolution;

sort(mySet.begin(), mySet.end());
int n;

function<void(int, int)> back = [&](int k, int prevI) {

if(k == n) {

if(prevSolution != solution) {
cout << "{";
for(int i = 0; i < k; i++) {
cout << solution[i];
if(i < k - 1) cout << ", ";
}
cout << "}"<< endl;
prevSolution = solution;
}
}
else {
for(int i = prevI + 1; i < mySet.size(); i++) {
solution[k] = mySet[i];
back(k + 1, i);
}
}
};
for(n = 0; n <= mySet.size(); n++) {
back(0, -1);
}
}``````

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

Time Complexity O(n * 2 ^ n), space complexity: Additional O(n) space for remembering the current solution and the previous one.

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

I don't get people on careercup. We don't want to read big pile of code - we can code too. We are just interested in the main idea of the solution in a couple of sentences.

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

A simple c# solution

``````using System;
using System.Linq;
using System.Collections.Generic;

public class Test
{
public static void Main()
{
int[] array = new int[] { 2, 3, 3, 4 };
PowerSet ps = new PowerSet(array);
ps.ComputePowerSet();
}

public class PowerSet
{
int[] array;
List<int> prevList = null;
List<List<int>> powerSet;
public PowerSet(int[] array)
{
this.array = array;
this.powerSet = new List<List<int>>();
}

public void ComputePowerSet()
{
// Computing PowerSet by finding all sets of size in each for loop
for (int i=0; i<= array.Length; i++)
{
Permute(new List<int>(), 0, i);
}

// Prinitng PowerSet
foreach (var set in this.powerSet)
{
PrintList(set);
}
}

public void Permute(List<int> list, int level, int length)
{
if (list.Count == length)
{
if (!powerSet.Any() || !list.SequenceEqual(powerSet[powerSet.Count - 1]))
{
}

return;
}

for (int i = level; i < array.Length; i++)
{
Permute(list, i + 1, length);
list.RemoveAt(list.Count - 1);
}
}

public static void PrintList(List<int> list)
{
Console.Write("{ ");
foreach(var elem in list)
{
Console.Write(elem + ", ");
}

Console.WriteLine("}");
}
}
}``````

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

Python

``````from collections import defaultdict

# a list of numbers
def foo(lst):
dic = defaultdict(int)
for num in lst:
dic[num] +=1

output = 1
for key in dic:
output *= dic[key] +1
return output

if __name__ == '__main__':
print foo([1,2])
print foo([1,2,2])
print foo([1,2,2,3])
print foo([1,3,5,2,2,4,4,4])``````

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

``````public class HelloWorld{

public static void main(String []args){
System.out.println("Hello World");
int[] arr = {1,2,3};
boolean[] bflag = new boolean[arr.length];
for(int i=1;i<=arr.length;i++)
sets(arr,bflag,0,i,0);
}

public static void sets(int[] arr, boolean[] bflag, int currS, int size, int index){
if(currS == size){
// print
for(int i=0;i<arr.length;i++){
if(bflag[i]){
System.out.print(arr[i] + "," + " ");
}
}
System.out.println(" ");
return;
}
if(index >= arr.length){
return;
}

bflag[index] = true;
sets(arr, bflag, currS+1, size, index+1);
bflag[index] = false;
sets(arr, bflag, currS, size, index+1);
}
}``````

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

Folks, why aren't we discussing our algorithms in psuedocode or in english (writing steps)? That is the most important part if we want to discuss our solutions.

For this problem, you can solve it by using "techniques" that you should already have in your mind (but then later you can find a custom technique if it's worth optimizing.. but in this case you won't be able to do better):

{First step, figure out if you can remove duplicates in O(n) }
{There is a standard technique for this: }
1) Hash the elements of your array (which removes duplicates)
-> Assume you picked the write hash table and you can do the operations in amortized average time of O(1)

2) Reverse the hash table into a simple array A[i], which will now have no duplicates {you can use the oringal array to store A}

[Steps 1 and 2 are a technique for removing duplicates of integers from an array in O(n) time]

[If you didn't know how to do above, you could do it less optimally
a) Sort your original list (nlgn or n if you are able to use bucket/count sort)
b) Linear scan and create a new array without duplicates

{ Or even less optimally:
Brute force O(n^2) to remove duplicates

POINT: Don't give up. Break your problem into steps and use brute force methods in some steps if you can't think of any better. }

3) Use a "n-bit generating" function to generate bits strings of length n
[You should have such a function memorized for use in these set generation problems... if not commit to memory how to make this function]

4) In the base case of 3), instead of printing the n-bit binary numbers, print sets from the array you created in 2) above in this way:
if your binary number is 0011010...
your output set will be { A[i] such that position i in bit string is 1 }

Algorithm runtime:
These type of problems always require a 2^n solution because you need to generate 2^n sets (and there is no way around this). And you can confirm this by noting:

1) Step 1: O(n) time, plus O(n)
2) Step 2): O(n) time, plus no extra space (as you can use your original array)
at this point you can also delete the hash table

3) Step 3: O(2^n) time, plus O(n) bits space

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

I want to make another point
1) In this case, if you thought of a solution in steps (where each step is something you know as a technique) then you will always win...

Because all the earlier steps before the 2^n step can be brute force and it will not change the optimality of the solution. So your interviewer shouldn't care if you used some n^k stuff before the 2^n step.

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

if you remove duplicate elements than
{1,2,2}
can never be the output.

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

Yes, I misunderstood the OP.
It is easy to modify for that situation too.

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

``````set < vector < int > > PowerSet(vector < int > a)
{
int n = a.size();
set < vector < int > > ret;
int num = (1 << n);
for(int i = 0; i < num; ++i)
{
vector < int > v;
for(int j = 0; j < n; ++j)
{
if(i & (1 << j)) v.push_back(a[j]);
}
ret.insert(v);
}
return ret;
}``````

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.