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

here's a coding interview problem from Facebook you're given an array of unique items so there are no duplicates in this array and you're supposed to write a function that takes this array of unique items or you can see as a set of unique items given in an array format and your function should find all of its subsets so for example one potential subset is an empty set and another subset of this entire set is the given set itself one two and the two other subsets or single item subsets one and two now your function doesn't have to return anything but it's supposed to print out all of the subsets in say standard output and you can print them in any order you like so if you decide to print the empty set you'll have an empty line to represent the empty set and if you decide to print a set of one after that you'll have one comma and with a set of two you have to come up I'm ending these lines with a comma just for simplicity just so that it's easier to implement your function and if you print one two at the end you'll have 1 comma 2 comma so that's the problem again you can print them in any order you like so think about this problem for a second pause the video right here and then come back to the video now the first thing you might consider when you think about this problem is how many subsets are there for the given array or for the given set the answer is there are two to the part and subsets where n is the number of items in the array so this is going to be 2 to the power of 2 which is 4 if n is equal to 2 as in this example 1 and 2 and let me quickly explain why that's the case let's say we're trying to construct a subset out of the given array for example 1 & 2 for us to do that there are a few decisions that we need to make first of all should we include 1 the first item in this new subset that we are trying to construct and then the second decision that we need to make is should we include two in this new subset so there are two decisions that we need to make and for each decision or for each item there are two available choices so the total number of available choices for us as we try to construct a new subset from this given array is 2 times 2 which is 4 this number right here and it's the same when we are trying to construct a subset out of an array of n items as well there are 2 choices that we could potentially make for each item and since there are n items there are 2 to the Parv and potential choices or 2 to the power of n potential subsets if we visualize this process it might look like this with this idea we can construct all of the subsets by starting with an empty set and I'm going to use this example 1 & 2 to explain this idea once we have an empty set we need to ask ourselves should we add 1 to this set the empty set and if the answer is no we'll still have an empty set and if the answer is yes we'll have a set of 1 after that for each of those subsets or each of those sets we need to ask ourselves should we add 2 to each of those sets if the answer is yes we'll have a set of 2 if we start with an empty set and a set of 1 & 2 if we start with a set of 1 and so on and this way we can construct all of the four subsets for this particular example so when you see this graph you might say well it looks kind of like a recursion tree so maybe we can solve this problem somehow using recursion let's see what the solution might look like now I'm going to explain my solution in suit code I'm going to write a function called all subsets which is going to take given array as the input for example 1 & 2 disarray and it's not going to return anything but it will print out all of its subsets to construct all of its subsets as I mentioned earlier we're going to start with an empty set so the first step in all subsets is going to be initialized an empty set but to represent each of these sets for example this empty set and this set of one we're going to use an array instead of a set data structure and it's going to be clear why we are doing this later so for example if you have a set of two and if you're given this array one and two a set of two can be represented with null and two now means that one is not in this set and two means that two is in this set and this way we can represent any subset of this array with an array of the same length so to initialize this initial empty set at the beginning of all subsets we can initialize an array whose length is the same as given arrays length or a given array that length and the content could be anything but it can be for example now now if the given arrays length is 2 and we're going to define a helper function which is going to call itself recursively we're going to call it helper and it's going to take three arguments give an array which is the given array which never changes subsets which represents the state of the current subset that we're constructing so for example this empty subset or this set of one represented in an array format an eye is going to represent the index of the current item that we're examining so if I is equal to 0 for example that means that we're trying to decide if we should include this item in the current subset that we're trying to construct and if I is equal to 1 that means that we're currently examining this item at index 1 now the first thing we need to do in the helper function is we need to check if I is equal to given arrays length or a given array length if the case for example in this example if I is equal to two which is given arrays length that would mean that I is pointing outside of array which means we already went through this whole array and finished constructing one of these subsets so at that point we can just print the current subset we have with say print subset of subset and here I'm assuming that we've already defined a function called print set which prints out all of the non null items in the given subset array and of course in our main function our subsets after defining an empty subset represented as an array and assigning it to subsets we need to call the helper function with given array the empty subset and 0 and of course we need to start with 0 because that's the first index now in the helper function if I is not equal to given arrays length yet for example if we're right here where I would be 1 what should we do if I is equal to 1 that means that we're trying to decide if we should include 2 in this subset that we're constructing so we'll need to call helper twice recursively once without adding two and the second time after attitude to this subset now to represent the first two recursive call where we don't add the current item that we're examining to the subset we can just set the item at the current index in the subset array to now we can do this with subset square brackets I equals now and after that we can call helper recursively with given array subset which is the updated subset I plus one to go to the next index and to represent the second recursive recall where we do add the current item that we're examining to the subset we can set the item at index I in the subset array to the current item for example 2 we can do this with of course subset square brackets I eCos given array square brackets I and then just like before called helper again recursively with given array subset and I plus one and that's my solution but what's the benefit of using an array instead of a set structure to represent each subset the benefit is that it becomes easier to keep track of the current state of the subset by using an array instead of a set structure for example subset might start at now now but as we go down this recursion tree at this point when we are here it'll be now two and you might ask what happens once we go down this branch the second recursive call from the first call well at that point we don't have to worry at all about the current state of this array because once we get to the end of this tree will override every single element anyway so for example once we get here this element will be overriding with one and this element will be now so as you can see by using an array we have to worry less about what the state of this subset looks like or how the state has been affected by previous recursive calls and this is not necessarily the case with a set structure it is possible to implement these functions using a set structure but it's just that if you do that you need to be extra careful about which recursive calls are made before which ones now once you understand that solution I'd recommend that you try solving this problem with an iterative solution instead so try solving this problem without recursion at all and once you have a good solution with that let me know in the comment section below also if there's any other interview question I should cover in the future let me know at CES dojo dot io / contribute where you can let me know the question anonymously ok I'll see you in the next video

Channel: CS Dojo

Views: 462,481

Keywords: facebook coding interview questions and answers, facebook programming interview question, facebook software engineer interview questions, coding interview questions, google coding interview question, amazon coding interview question, print all sets of a set, how to get a job at facebook, how to get a job as a software engineer, facebook software devleoper interview questions

Id: bGC2fNALbNU

Length: 10min 57sec (657 seconds)

Published: Mon Oct 02 2017