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

23
28



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

Is there any other interview question you’d like me to cover in the future? You can (anonymously) let me know at: www.csdojo.io/contribute

Nguồn:https://wijstaanvooronzegrondrechten.org/

23 COMMENTS

  1. 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

  2. I think below iterative solution (in python) might work:
    def compute_all_subset(arr):
    allSubset = []
    allSubset.append([])
    for item in arr:
    allSubsetLength = len(allSubset)
    for i in range(0,allSubsetLength):
    temp = allSubset[i].copy()
    temp.append(item)
    allSubset.append(temp)
    return allSubset

  3. honestly, it is not that the problem cannot be solved. If I am faced with this problem in real life like as a homework problem, I might get stuck for the first 10 minutes, and then I might put it down, do something else, maybe have lunch, and then I think of something, and then I try it, and yes, I was able to solve it the second time I thought about it, using the binary representation… so I can solve it… it is just that within that 20 minutes per interview question time frame, you might not show a solution like a straight line from point A to point B. So does that mean you are not good? I am sure many programmers, they might do something in the morning, and in the afternoon or the next day, they thought, hold on a second, there is a much better way! Does that mean they are not good, because they don't give the perfect solution in a 20 minute time frame?

  4. from functools import reduce

    def power_set(array):
    return reduce(lambda subsets, i: subsets + list(map(lambda x: x + [array[i]], subsets)), range(len(array)), [[]])

  5. Hmmm – are we sure recursion is a good solution here? If we just for loop from 0 to 2^N then we can use the loop counter as a bit-mask to determine whether an element is in the next subset (and print).

  6. Here is the iterative solution to the same problem, please find the 'subsetIterative' function:

    https://github.com/nawazish-github/elements-of-programming-interviews-java/blob/byte-by-byte/src/main/java/recursion/Subset.java

  7. my solution on python:

    def subsets(array):
    import itertools
    n=len(array)
    for i in list(itertools.product("10", repeat=n)):
    output = ""
    for j in range(len(i)):
    if int(i[j]) == 1:
    output += str(array[j])+","
    print(output)

  8. Python Solution

    li=[]

    n=input()

    a=n.split()

    for i in a:

    li.append(int(i))

    print(li)

    print(" ")

    for i in li:

    print(i,end=",")

    print()

    for i in li:

    print(i,end=",")

  9. I found solution using a different aproach:

    function getSubsets(arr) {

    function subsets(arr, x) {

    console.log(arr);

    for (let i = x; i < arr.length; i++) {

    const aux = […arr];

    aux.splice(i, 1);

    subsets(aux, i);

    }

    }

    subsets(arr, 0);

    }

  10. def subset(s, sub):

    if not s:

    print(sub)

    return

    s1 = sub[:]

    s1.append(s[0])

    s2 = s1[:-1]

    subset(s[1:], s1)

    subset(s[1:], s2)

    def print_subset(s):

    subset(s, [])

    print_subset([1,2,3,4])

  11. 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

  12. I am trying to solve a problem for the past one week and being new to competitive programming, it is a tough one for me. The problem states:-

    Given two binary cyclic sequences(A and B) of equal length 'n'. Our target is to make sequence A to be equal to sequence B. The only implementation that we can do to sequence A is if A(i) is the element at the ith index of sequence A, if we want to flip A(i), then we will also have to flip A(i+1) and A(i+2). So basically at a time we can flip any three consecutive elements of sequence A. Let's call flipping the three elements as a 'move'. Now our target is to make sequence A to be equal to sequence B in the least moves possible. And our output should print out the min. number of moves needed for the same.

    Please comment below if you'd need more detailing on the problem statement. Any help or hint would be appreciated!

  13. It's much easier when you realize that all the subsets for a given set can be represented by bits when you count in binary up to 2^n. For example: 000, 001, 010, 011… can represent the subsets for a list of length 3. You can code this in 5 lines in python with no recursion and O(1) memory like so:

    for i in range(2 ** len(set)):

    for j in range(len(set)):

    if i & (1 << j):

    print(set[j], ",",sep='',end='')

    print() # new line

  14. Iterative solution.
    Given a set and a subset of this set, you can interpret this subset as a binary number, for each element in the set: if it's a member of the subset, the value will be 1 and otherwise 0, this is how you build the binary number for a given subset.
    Which means that you can interpret back the binary number to the subset.
    The amount of subsets is 2^the length of the big set
    Let's define: n = length of a given set.
    There are 2^n binary numbers that can be interpreted to subsets of the set by the method I showed.
    From the number 0 to the number 2^(n-1).

    Algorithm.
    Define n = length of the given set.
    Define s = an empty set.
    Loop i from 0 to 2^(n-1):
    Define b = i in binary.
    Define sub = interpret i to subset.
    Add sub to s.
    End loop.
    Return s.

  15. It works, Master… Thx a lot… My case in C language :

    int main() {
    int given_array[] = {5, 10, 15, 20};
    all_subsets(given_array, 4); //The number '4' is the size of 'give_array'

    return 0;
    }

    void print_set(int subset[], int size) {

    for (int i = 0; i < size; i++) {

    printf("%d, ", subset[i]);

    }

    printf("n");

    }

    void helper(int given_array[], int size, int subset[], int i) {

    if (i == size) {

    print_set(subset, size);

    }

    else {

    subset[i] = 0;

    helper(given_array, size, subset, i + 1);

    subset[i] = given_array[i];

    helper(given_array, size, subset, i + 1);

    }

    }

    void all_subsets(int given_array[], int size) {

    int subset[size];

    helper(given_array, size, subset, 0);

    }

  16. 7:58
    No return on helper function you're pulling from the initial subset each iteration

    8:05

    you aren't printing one overall link

LEAVE A REPLY

Please enter your comment!
Please enter your name here