Name: Facebookコーディングインタビューの質問と回答#1：セットのすべてのサブセット (Facebook Coding Interview Question and Answer #1: All Subsets of a Set)
Uploaded: 2021-01-14T10:23:02.000Z
Duration: 10 min 58 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

For on Facebook you're given an array of unique items, so there are no Democrats in disarray.

And you're supposed to write a function that takes this array off unique items.

Or you can see, as a set of unique items given in on a very formal on your function should find all of its substance.

So, for example, one potential subset is on empty set on another subset off.

This entire set is the given said itself one, too, and the two other subsets are single items.

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 off one after that, you have one comer, and with a set of two you'll 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 D print 12 At the end, you have one comma, two comma.

You can print them in any order you like.

So think about this problem for a second positivity right here and then come back to the media.

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 park and subsets where N is the number of items in the array.

So this is going to be, too to the part of, too, which is four.

If an is equal to two, as in this example, one and two, and let me quickly explain why that's the case.

Let's say we're trying to construct a substance out of the Given array, for example, one on two.

For us to do that, there are a few decisions that we need to make.

First of all, should we include one, the first item in this new subset that we're trying to construct?

And then the second decision that we need to make a studio include two in this new subset.

So there are two decisions that we need to make on for each decision or for each item.

So the total number of available choices for us as we try to construct a new substance from this given array is two times two, which is four.

This number right here on it's the same when we're trying to construct a subset out of an array off and items as well.

There are two choices that we could potentially make for each item on since their n items there, too, to the party and potential choices or two to the part of and 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.

I'm going to use this example one unto to explain this idea.

Once we have an empty set, we need to ask ourselves, Should we add one to this set the empty set, and if the answer is no, will still happen and to sit.

And if the answer is yes, we'll have a set of one after that.

For each of those subsets or each of those sets we need to ask ourselves, Should we add to to each of those sets?

If the answer is yes, we'll have a set of two.

If we start with an empty set and a set of one and two, if we start with a set of one and sewn on 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 Rikers entry.

So maybe we can solve this problem somehow.

Using Wilkerson, Let's see what the solution might look like.

Now I'm going to explain my solution in CID code.

I'm going to write a function called All Subsets, which is going to take given array, as Thean put for example, one and two disarray.

And it's not going to return anything, but it will print out all of its substance to construct all of its substance.

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, Empty said.

But to represent each of these sets, for example, this empty set on this set a one.

We're going to use an array instead of a set data structure, and it's going to be clear why we're doing this later.

So, for example, if you have a set of two, and if you were given this array one and two, a set of two can be represented with no on two.

No means that one is not in the set on two means.

That, too, is in the set, and this way we can represent any subset off this array within the rate of the same length.

So to initialize this initial empty set at the beginning off all subsets, we can initialize Honore, whose length is the same as giving a race length or given a ray that length on the content could be anything but he can't be, for example, no no.

If the given a raise length is too and we're going to define ah helper function, which is going to call itself recursive Lee, we're going to call it Helper, and it's going to take three arguments given array, which is the given array which never changes Subset, which represents the state of the current substance that we're constructing.

So, for example, this empty subset or this set of one represent it in an array format on I is going to represent the index of the current item that we're examining.

So if I is equal to zero, 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 one, that means that we're currently examining this item at the next one.

Now the first thing we need to do in the helper function is we need to check if I is equal to given a raise length or a given a rate that length.

If that's the case, for example, in this example, if I is equal to two, which is given a race length, that would mean that eyes pointing outside ovary, 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 Prince Set, which prints out all of the non al items in the given subset array and, of course, in our main function, all subsets.

After defining an empty subset represented as an array on assigning it to subset, we need to call the helper function with given array the empty subset on zero.

And, of course, we need to start with zero because that's the first index now in the helper function.

If I is not equal to given a race length yet, for example, if we're right here where I would be one, what should we do if eyes equal to one?

That means that we're trying to decide if we should include two in this substance that we're constructing.

So we'll need to call Helper twice weaker Sibley once without adding to and the second time after adding tooth to the subset.

Now to represent the 1st 2 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 and the subset array to now we can do this with subset square brackets I equals now on.

After that, we can call it help for me personally with given array subset, which is the update is upset I plus one to go to the next index and to represent the second because he would call where we do add the current item that we're examining to the subset.

We can set the item at the next I in the subset Ray to the current item, for example, to we can do this with, of course, subset square brackets.

I Eco's given a racecar buckets I and then just like before called Helper.

Again, we curse ugly with given a race upset on my 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.

No, But as we go down this Ryker Asian tree at this point when we're here, you'll be now, too.

And you might ask, what happens once we go down this branch?

The second rickerson call from the first call.

Well, at that point, we don't have to worry at all about the current state off 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 override it with one on 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 rickerson 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 records who calls their maid before which ones.

Now, once you understand that solution, I recommend that you try solving this problem with an iterative solution instead.

So try solving this problem without rickerson at all at once.

Let me know in the comments section below.

 Also, if there's any other interview question I should cover in the future, let me know at siesta joe dot io slash Contribute where you can let me know the question anonymously. 

字幕リスト動画再生

Facebookコーディングインタビューの質問と回答#1：セットのすべてのサブセット (Facebook Coding Interview Question and Answer #1: All Subsets of a Set)

potential

assume

quote

potentially