CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Facebook Interview Question for Software Engineer / Developers


More Questions from This Interview



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

void PrintSubsets()
{
int source[3] = {1,2,3};
int currentSubset = 7;
int tmp;
while(currentSubset)
{
printf("(");
tmp = currentSubset;
for(int i = 0; i<3; i++)
{
if (tmp & 1)
printf("%d ", source[i]);
tmp >>= 1;
}
printf(")\n");
currentSubset--;
}
}

- Rayden November 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Mind blowing solution

- Shashi December 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

really mindblowing solution... u r great... Thanks alot..

- ranganath111 January 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are the man....

- Varadh March 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice solution. thanks!

- santhosh November 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution.

However, it makes the assumption that there are no duplicate values and that the input is small (n <= 32).

e.g. For {1,1,2,3}, the solution above will print the following twice: {1,2,3},{1,2},{1,3},{1}

Consider how you'd handle duplicate values and larger inputs.

Also, if you're asked not to print but to return them, then this solution would still be O(n * 2^n) running time, whereas you may be able to achieve O(2^n) with a different approach.

- arwid March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To make it more variable:

int source[size] = {//fill in numbers here}
     currentSubset = 1 << size;
   //change for loop from "i < 3" to "i < size"

- Anonymous April 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How about this one?

vector<int> L;

void PrintSubset(const vector<int>& v, const int idx)
{
for (int i = idx; i < v.size(); ++i)
{
L.push_back(v[i]);
Print(L);
PrintSubset(v, i + 1);
L.pop_back();
}
}

PrintSubset([1,2,3], 0);

Output:

1
12
123
13
2
23
3

- Rum April 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include <stdio.h>

#define N (3)

void printSet(int s[N])
{
int i;

printf("\n{ ");

for(i=0; i<N; i++)
{
printf("%d ",s[i]);
}

printf("}\n");
}

void allSubset(int s[N], int k, int n)
{
int i;

if(k == n) /* we found one solution */
{
printSet(s);

return;
}

/* either we select the kth element */
s[k] = 1;
allSubset(s, k+1, n);

/* or we don't select the element */
s[k] = 0;
allSubset(s, k+1, n);

return;
}

void allSubset_driver()
{
int a[N] = {1,2,3};
int s[N], i;

/* initialize set */
for(i=0; i<N; i++)
{
s[i] = 0;
}

allSubset(s, 0, N);
}

int main()
{
allSubset_driver();

- Anonymous September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void print_all_subset(const int numbers[], const size_t size, const int begin_index, int print[])
{
    if ( begin_index == size )
    {
        for ( unsigned i = 0; i < size; i ++ )
        {
            if ( print[i] ) cout << numbers[i] << " ";
        }
        cout << endl;
        return;
    }
    print[begin_index] = 1;
    print_all_subset(numbers, size, begin_index + 1, print);
    print[begin_index] = 0;
    print_all_subset(numbers, size, begin_index + 1, print);
}

void print_all_subset(const int numbers[], const size_t size)
{
    vector<int> print;
    print.resize(size);
    print_all_subset(numbers, size, 0, &print[0]);
}

- dumbcoder November 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Fixing the number of recursive function:

void print_all_subset_internal(const int numbers[], const size_t size, const int begin_index, int print[])
{
    if ( begin_index == size )
    {
        for ( unsigned i = 0; i < size; i ++ )
        {
            if ( print[i] ) cout << numbers[i] << " ";
        }
        cout << endl;
        return;
    }
    print[begin_index] = 1;
    print_all_subset_internal(numbers, size, begin_index + 1, print);
    print[begin_index] = 0;
    print_all_subset_internal(numbers, size, begin_index + 1, print);
}

void print_all_subset(const int numbers[], const size_t size)
{
    vector<int> print;
    print.resize(size);
    print_all_subset(numbers, size, 0, &print[0]);
}

- dumbcoder November 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The above idea explained

If there are n objects than all 2^n subsets can be determined by iterating from 0 to 2*n and in each iteration by selecting the elements at the position having set bit in the counter.
Like for given ex
000--{}
001--{1}
010--{2}
011--{2,3}
100--{3}
101--{1,3}
110--{2,3}
111--{1,2,3}

- nitin November 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@raden
Nice solution !!

- Coder November 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Rayden and Nitin
great sol and awesome explaination :) thanks guys

- pratik.nitk December 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Rayden and Nitin

Good Solution dudes keep it up..Thanks a lot

- User May 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Rayden and Nitin I am inspired from Solution,Please folk have a another piece of code


#include<stdio.h>

int main()
{
int i,j,a[100],total;

printf("Enter the total Number:");
scanf("%d",&total);


for(i=0;i<total;i++){
printf("Enter the %d Number : ",i+1);
scanf("%d", &a[i]);
printf("\n");
}

i=1<<total;
while(i>0){

printf("{");
for(j=total-1,k=0;j>=0;j--){
if( 1<<j & i)
printf("%d",a[k]);
k++;
}
i--;
printf("}\n");

}

return 0;

}

- Rex June 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

output will look like this:

{ 1 1 1 }

{ 1 1 0 }

{ 1 0 1 }

{ 1 0 0 }

{ 0 1 1 }

{ 0 1 0 }

{ 0 0 1 }

{ 0 0 0 }

- Anonymous September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printSubSetsV2(int[] set)
        {
            int n = set.Length;
            int currentSubset = (int) Math.Pow(2, n) - 1;                     

            while(currentSubset != 0)
            {
                Console.Write(currentSubset + ": { ");
                for(int i = 0; i< n; ++i)
                {                    
                    if (BitManipulation.GetBit(currentSubset, i))
                        Console.Write(set[i]);                   
                }

                Console.WriteLine(" }");            
                currentSubset --;
            }
        } //end

- iA May 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

class BitManipulation
    {

        public static bool GetBit(int n, int i)
        {
            return ((1 << i) & n) == 0 ?false: true;
        }
    }

- iA May 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;


public class Subset_of_set {

	public static ArrayList<ArrayList<Integer>> getSubset(ArrayList<Integer> set)
	{
		ArrayList<ArrayList<Integer>> allsubset = new ArrayList<ArrayList<Integer>>();
		int max = 1<<set.size();
		for(int i = 0;i<max;i++)
		{
			ArrayList<Integer> subset = converInttoSet(i,set);
			allsubset.add(subset);

		}

		return allsubset;


	}

	private static ArrayList<Integer> converInttoSet(int i,ArrayList<Integer> set)
	{
		ArrayList<Integer> subset=  new ArrayList<Integer>();
		int index =0;
		for(int k = i;k>0; k>>=1)
		{
			if((k&1)>0)
				subset.add(set.get(index));	
			index++;
		}
		return subset;
	}

	public static void main(String[] args) {

		ArrayList<Integer> a = new ArrayList<>();
		for (int i = 0; i < 5; i++) 
		{
			a.add(i+1);
		}
		ArrayList<ArrayList<Integer>> result = getSubset(a);

		System.out.println(result);
	}

}

- RS January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;


public class Subset_of_set {

	public static ArrayList<ArrayList<Integer>> getSubset(ArrayList<Integer> set)
	{
		ArrayList<ArrayList<Integer>> allsubset = new ArrayList<ArrayList<Integer>>();
		int max = 1<<set.size();
		for(int i = 0;i<max;i++)
		{
			ArrayList<Integer> subset = converInttoSet(i,set);
			allsubset.add(subset);

		}

		return allsubset;


	}

	private static ArrayList<Integer> converInttoSet(int i,ArrayList<Integer> set)
	{
		ArrayList<Integer> subset=  new ArrayList<Integer>();
		int index =0;
		for(int k = i;k>0; k>>=1)
		{
			if((k&1)>0)
				subset.add(set.get(index));	
			index++;
		}
		return subset;
	}

	public static void main(String[] args) {

		ArrayList<Integer> a = new ArrayList<>();
		for (int i = 0; i < 5; i++) 
		{
			a.add(i+1);
		}
		ArrayList<ArrayList<Integer>> result = getSubset(a);

		System.out.println(result);
	}

}

- RS January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;


public class Subset_of_set {

	public static ArrayList<ArrayList<Integer>> getSubset(ArrayList<Integer> set)
	{
		ArrayList<ArrayList<Integer>> allsubset = new ArrayList<ArrayList<Integer>>();
		int max = 1<<set.size();
		for(int i = 0;i<max;i++)
		{
			ArrayList<Integer> subset = converInttoSet(i,set);
			allsubset.add(subset);

		}

		return allsubset;


	}

	private static ArrayList<Integer> converInttoSet(int i,ArrayList<Integer> set)
	{
		ArrayList<Integer> subset=  new ArrayList<Integer>();
		int index =0;
		for(int k = i;k>0; k>>=1)
		{
			if((k&1)>0)
				subset.add(set.get(index));	
			index++;
		}
		return subset;
	}

	public static void main(String[] args) {

		ArrayList<Integer> a = new ArrayList<>();
		for (int i = 0; i < 5; i++) 
		{
			a.add(i+1);
		}
		ArrayList<ArrayList<Integer>> result = getSubset(a);

		System.out.println(result);
	}

}

- RS January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//generate all combination of bool array s[] and print corresponding a[] elements
void allSubset(int s[], int k, int n,int a[]) 
{
int i; 

if(k == n) /* we found one solution */ 
{
	for(int j=0;j<n;j++){
		if(s[j]!=0){
			cout<<a[j];
		}
	}
cout<<endl;

return; 
} 

/* either we select the kth element */ 
s[k] = 1; 
allSubset(s, k+1, n,a); 

/* or we don't select the element */ 
s[k] = 0; 
allSubset(s, k+1, n,a); 

return; 
} 


int main() 
{

	int a[]={2,3,4,8};
	int n=sizeof(a)/sizeof(a[0]);
int s[n]={0}; /* initialize set to 0*/ 

allSubset(s, 0, n,a); 

}

- JerryGoyal May 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void print_all(int *ar,int sz) {
    int total_comb = pow(2,sz) - 1;
    for(int i = 0; i <= total_comb; i++) {
        cout<<"\n( ";
        for(int j = 0 ; j < sz ; j++){
            if(i & 1<<j) cout<<ar[j]<<", ";
        }
        cout<<" ) ";
    }
}

- Pawan Bhardwaj July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void print_all(int *ar,int sz) {
    int total_comb = pow(2,sz) - 1;
    for(int i = 0; i <= total_comb; i++) {
        cout<<"\n( ";
        for(int j = 0 ; j < sz ; j++){
            if(i & 1<<j) cout<<ar[j]<<", ";
        }
        cout<<" ) ";
    }
}

- Anonymous July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my solution

void print_all(int *ar,int sz) {
    int total_comb = pow(2,sz) - 1;
    for(int i = 0; i <= total_comb; i++) {
        cout<<"\n( ";
        for(int j = 0 ; j < sz ; j++){
            if(i & 1<<j) cout<<ar[j]<<", ";
        }
        cout<<" ) ";
    }
}
//end

- Anonymous July 13, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More