Facebook Coding Interview Question and Answer #1: All Subsets of a Set

Find and print all subsets of a given set! (Given as an array.)

[CSDojo]

Thanks as always for watching this video guys!

If there is any other interview question you'd like me to cover in the future, you can (anonymously) let me know at this link here :) -> www.csdojo.io/contribute

[veemacks]

If it's an interview for Facebook, make sure to print an ad between each set for bonus points.

[kolos]

I have a message for anyone who sees this examples as difficult:

Don't let your brain fool you. When encountering something we don't know, our brain is extremely, EXTREMELY good at convincing us that given task is either: too complicated for us, too boring for us or both. See through it. Look at the whole picture. For example. You have some skills that are easy for you now. Let's say typing on keyboard. Do you remember how hard it was in the beginning of developing that skill? And how your brain made same assumptions about what you are doing, that this is maybe stupid, or boring, and who the fuck placed those stupid keys in this non alphabetical order?. Try to remember exactly that feeling, then how you overcome it, and how it is easy for you now. Same shit here. Your brain is tricking you. It's not subject, it's just automatic reaction of our brain. See through it, persevere. It'll be hard, starting learning programming is hard, but in the end, you'll do it with fucking excitement and pleasure, I'm telling you. I was absolutely dumb at school, i didn't know what PI is in mathematics, fucking multiplying two digit numbers was my peak achievement. But. I always believed that if I'll decide firmly enough, I can learn anything, because anything can be interesting, extremely interesting, if you put enough focus and effort in it. Five years later, I'm middle Java developer of web applications. I did it, so can you.

[BenHarosh]

There's a way elegant way to solve it with a binary representation of the input array.
Since the elements in the array are unique they can be represented as 0 or 1 (present or NOT present).
Lets say we have an array [1, 3, 5, 7].
array[0] = 1;
array[1] = 3;
array[2] = 5;
array[3] = 7;

All we need to to is to define a printing method that prints all entries where 1 is on in the binary representation of our iteration.

In our example, the subsets can be represented by all the binary options from 0 to 4 (decimal, the array size) are:
0000 = {}
0001 = {1}
0010 = {3}
0011 = {1, 3}
0100 = {5}
0101 = {1, 5}
0110 = {3, 5}
0111 = {1, 3, 5}
and so on, till we get to 2^n options, in our case - 2^4 = 16 permutations.
1111= {1, 3, 5, 7}

[MatthewRiddell]

I wanted to share an iterative approach that I thought about while watching this video. Consider an example where you have eight elements. The total number of possible combinations is 2^8 (256). If we were going to use a for loop in C++, your loop might look like this: for(int i = 0; i < 256; i++). If you covert the index of 'i' into binary, you can visualize this as switches that tell you which elements to print out. For example, the last combination you print out will be where 'i' is equal to 255. That can be represented in binary as 1111 1111. Each index of this binary number represents an index in your initial array and as you look through this binary number from left to right, if the index is 1 then you print out the associated value from the array.

[phuongdinh]

Since we're printing out the power set of the original set, this is the shortest solution you can find

for i = 0 to 2^n:
print binary_representation_of(i) * original_set;

[manosriram]

This Worked for me in Python:
a = int(input("Enter Range:"))
ss=[]
b1=[]
lst=[]
ss1=[]
ss2=[]

for t in range(a):
b = int(input())
b1.append(b)

b1_len = len(b1)

for i in range(0, b1_len):
for j in range(i+1, b1_len):
lst = [b1[i], b1[j]]
ss.append(lst)


for t in range(0, a):
ss.append(b1[t])

ss.append(ss1)
print(ss)

[mappu]

You are really good. The complexity is explained in a very simple way. Shout out to you.

[sadhlife]

here's my solution

it uses the fact that the subsets of, for eg. [3, 5, 7], will always be (subsets of [5, 7] + [append 3 in every subset of [5, 7])
(p.s. this is also a way to understand why the power set of n+1 elements is always 2 times the size of power set of n elements)

The code(Python3):

def get_all_subsets(s):
subsets = []
if len(s) == 0:
subsets.append([])
else:
s_copy = s.copy()
first_element = s_copy.pop(0)
subsets += [x for x in get_all_subsets(s_copy)]
subsets += [[first_element, *x] for x in get_all_subsets(s_copy)]
return subsets

print(get_all_subsets([5, 7, 8]))

[synergysession]

I have implemented this using java. It is a wonderful approach. Thanks dude. Below is the implementation:


public class FindAllSubsets {

public static void printAllSubsets(int[] array) {
int[] subset = new int[array.length];
helper(array, subset, 0);
}

private static void helper(int[] array, int[] subset, int i) {
if(i==array.length)
print(subset);
else {
subset[i]=0;
helper(array, subset, i+1);
subset[i]=array[i];
helper(array, subset, i+1);
}
}

private static void print(int[] subset) {
boolean flag=false;
for(int i:subset) {
if(i!=0) {
flag=true;
System.out.print(i+", ");
}
}
if(!flag)
System.out.print("-");
System.out.println();
}

public static void main(String[] args) {
int[] arr = {1, 2};
printAllSubsets(arr);
}

}

[JCho-pijz]

I rarely give compliments bc I always have something that bothers me about the video (i don't compliment tech videos) but WOW!!!! you're exceptional. your videos are AMAZING!!!! I have a physics degree went into DS/ML like most of us do and now I'm switching to CS. Your videos are so clear cut your speech is impeccable, perfect pace, sound and visual, and a nice flow. I can tell you did multiple takes or practice (if not that's REALLY impressive). combined with all you have a great knowledge base and present it *flawlessly*. Most of my interviews were things you covered and your videos are also the right amount of time. It's short enough to maintain interest and long enough to give you thoroughly. It's kind of a shame that people will only really tune in during interviews or when they are learning CS/DS. You structured it well with depth and breadth. You go into a great overview and then have videos that go into more specific which is WAY better than having one long video. I wish I saw these videos before just doing a bunch of leetcode problems. It's a great clean organized way of explaining the tools. I didn't know how many leetcode problems were enough but this is great! I used your info so much on interviews. It's so memorable and keeps my attention (I have ADHD so I'm really picky with videos). I'll definitely share your channel with people interviewing or anyone new to coding. If you decide to leave YouTube please keep these videos up. Also, you don't have that annoying "Aren't you amazed how smart I am?" arrogant vibe. You have a very humble, enthusiastic energy. Okay, this comment is way too long it's kind of creepy, but I'm a girl so how dangerous can I be? I just really wanted to let you know your videos are powerful and I really appreciate the time you take to edit them, it makes watching/learning so much easier. I know it's a lot of effort and it might not be obvious to people watching bc we're so focused on learning but I thought you should know it sets you apart.

[studyonline]

The iterative approach is a beautiful solution. Check out for it to get mesmerised with its beauty.

[dylanparrish-subda]

This was awesome!

For an iterative solution, I built out a tree. When the added node had a depth == len(passed_array) I added that node to a list. The data of each node contained the full set up to that point, so at the end, I was able to iterate through each node in the list of final-sets and call print on it.

[sundararamanvenkataramani]

How about this solution ?
Since we know the number of subsets
Represent that number in its binary form and essentially go from 0 till that number - 1.
For the above example
Now we start with 00 and go all the way till 11 where each position denotes the element and 1 denotes it’s included
So for e.g. : [1, 2]
00 : []
01 : [2]
10 : [1]
11 : [1, 2]

[luckysharmsy]

Have a facebook swe interview soon! I know it's not going to be the same questions but this is helping me brush up so thank you!!

[bladeshots]

Use a Map map<Integer, String[]> to arrive at an iterative solution. The key stores the index for visited elements in array i, e 0, 1, 2...etc.
The String[] stores different possible string with all previous map values.
Time complexity should be O(n * log(n)).
Print all the values for each key and you should have all the subsets

[JacquesDonnelly]

For n=0 to 2^n, convert n to a binary number. Create mapping from each binary value to the set. If 0 don't include in output, if 1 include in output.

[medhurstt]

My first thought was masking the elements of the array with a binary number. (I think someone else may have seen this solution too). The solution becomes counting to 2 to the power of elements in the array and at each step, mask the elements of the array with the binary number. 0 means dont print the element, 1 means do print it.

eg for his example we're counting to 4 and masking with {0, 0}, {0, 1}, {1, 0}, {1, 1) resulting in the empty array for {0, 0), {2} because the "1" element is masked out from {1, 2} when you apply {0, 1} to it and so on. Minimal memory needed.

[jaspreetsingh-nrgr]

If, say you are given an eight element set: make a list of all possible 8-bit binary strings and wherever 1 occurs in the string, that is the index of the element from the set that we should include in our list, the take the union(possible to do in python) and print .

[NathanSchwermann]

Simple iterative solution

val set = mutableSetOf(setOf<Int>())
listOf(1, 2, 3).forEach {next ->
set += set.map { it + next }
}