Facebook Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

def print_substr (string):
strset = dict()
for cnt in range(0,len(string)):
for from in range(0,len(string)):
to=frm+cnt+1
if to <= len(string):
strset[string[frm:to]]=0.0

for substr,dummy in strset.iteritems():
print substr

- swanh February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Remove dups from string and then user simple algo which based on binary representation on subset.

- glebstepanov1992 February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"aaa" -> [remove dups] -> "a" -> {"", "a"}, but should be {"", "a", "aa", "aaa"}

- 123 February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

1) first remove duplicates from the string
2) Use recursion and inside each call the same function, one using the character at that position and other without it.
the total number of possible solution is 2^n

- kr.neerav February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"aaa" -> [remove dups] -> "a" -> {"", "a"}, but should be {"", "a", "aa", "aaa"}

- 123 February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess in the question it says subsets of chars and sets don't have duplicate value so {'a'} is the only valid output and not {'a','a'}, {'a','a','a'}

- kr.neerav February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i= 0; i < s.length(); i++)
		{
			ArrayList<Character> tempList = new ArrayList<Character>();
			tempList.add(s.charAt(i));
			for(Character c : tempList)
				System.out.println(c);
			for(int j = i+1; j < s.length(); j++)
			{
				tempList.add(s.charAt(j));
				for(Character c : tempList)
					System.out.print(c);
				System.out.println();
			}

}

- Anonymous February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem is from Glassdoor I believe. The interview candidate said they had to use recursion without extra memory.

"Note: The interviewer gave me a big hint: "What happens if you sort the array and simply generate all the subsets?"

The best solution I've found so far is:

/*
    Prints all unique subsets of the string.
    Given a string write a function which prints all the subsets of the string.
    Now make the function to return only unique solutions.
    Careercup Facebook problem 

    The differences between subsets and substrings are two:
    1. substrings may have repeat characters
    2. substrings are ordered ("rm" != "mr")

    Ex. For the subsets of the string "rum" there are eight: "r", "ru", "rum", "u", "um", "m", "rm", "".
    For the substrings of the string "rum" there are seven: "r", "ru", "rum", "u", "um", "m", ""
     */
    public static void uniqueSubsets(String original, StringBuilder current, ArrayList<String> myList, int index)
    {
        current.append(original.charAt(index));

        myList.add(current.toString());


        for(int i=index+1; i<original.length(); ++i)
            uniqueSubsets(original, current, myList, i);

        current.deleteCharAt(current.toString().length()-1);
    }

It seems a bit weird though and does not include empty string.

- Johnb February 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void solve(int index, string gen, set<string> response, string input){
    response.add(gen);
    for(int i=index;i<input.size();i++){
        solve(i,gen+input[index],response,input);
    
    }

}

int main(){
    string input;
    cin>>input;
    set<string> response;
    for(int i=0;i<input.size();i++){
        solve(i,"",response,input);
    
    }

}

- amiu February 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function getSubsets($string) {
	$result = array();
	$chars = str_split($string);
	$strLength = strlen($string);
	$subsetAmount = 1 << $strLength; 
	for($mask=0; $mask < $subsetAmount; $mask++) {
		$subset = "";
		for($j=0; $j<$strLength; $j++) {
			if (($mask << $j >> ($strLength-1)) & 1) {
				$subset .= $string[$j];
			} else {
				$subset .= '_';
			}
		}
		$result []= $subset;
	}
	return $result;
}

- giladsof February 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I used a set to keep track of already printed subsets.
I did not see any constraints on space so here is a solution in EXPSPACE/EXPTIME

temp = ''
printed_sets = set()

def  subsetList(s):  
    global temp
    if len(s) == 0:
        if temp not in printed_sets:
            print temp
            printed_sets.add(temp)
        return
    temp_ = temp
    temp = temp + s[0]    
    subsetList(s[1:])
    temp = temp_
    subsetList(s[1:])

- Ehsan February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I used a dict to keep track of printed subsets.
This one takes EXPSPACE in the length of input, also EXPTIME.

temp = ''
printed_sets = set()

def  subsetList(s):  
    global temp
    if len(s) == 0:
        if temp not in printed_sets:
            print temp
            printed_sets.add(temp)
        return
    temp_ = temp
    temp = temp + s[0]    
    subsetList(s[1:])
    temp = temp_
    subsetList(s[1:])

- Ehsan February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A set can be used to prevent printing duplicates. In any case, this is an EXPTIME problem and adding a set makes it EXPSPACE.

temp = ''
printed_sets = set()

def  subsetList(s):  
    global temp
    if len(s) == 0:
        if temp not in printed_sets:
            print temp
            printed_sets.add(temp)
        return
    temp_ = temp
    temp = temp + s[0]    
    subsetList(s[1:])
    temp = temp_
    subsetList(s[1:])

- Ehsan February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def stringSubset(abc):
if (len(abc) == 1):
return [""]+[abc];
else:
result = []
a = abc[0]
bc = abc[1:len(abc)]
rest = stringSubset(bc)
if (bc[0] == a):
return [a+x for x in rest]
return [a+x for x in rest]+rest

- sbeast February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hash should limit selected items. The global hash of values can be used only for algorithm verification.

// Printing all possible sub sets, only unique solutions
var items = ["A", "B", "C", "A", "B", "D"];
var results = [];
function print(prefix, position) {
	var hash = {};
	for (var index = position + 1; index < items.length; index += 1) {
		var item = items[index];
		if (!hash.hasOwnProperty(item)) {
			hash[item] = true;
			var newItem = prefix.slice();
			newItem.push(item);
			results.push(newItem);
			print(newItem, index);
		}
	}
}

print([], -1);

results;

- Andrey Yeliseyev February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void print_subset(int *A, int K)
{
  int i;
  for(i=0; i<K; i++)
    fprintf(stderr, "%d  ", A[i]);
  fprintf(stderr, "\n");
}

void print_combination(int *A, int *B, int k, int pos, int start, int N, int K)
{
  int i;

  if(k==0){
    print_subset(B, K);
    return;
  }

  if(start >= N)
    return;

  for(i=start; i<N; i++){
    B[pos] = A[i];
    print_combination(A, B, k-1, pos+1, i+1, N, K);
  }
}

int main()
{
  int A[5] = {1,2,3,4,5};
  int B[5] = {0};

  int i;

  for(i=1; i<=5; i++)
    print_combination(A, B, i, 0, 0, 5, i);
}

- tecxon123 February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Input: "rum"
Output:
r
ru
rum
rm
u
um
m

public static void main(String[] args) {
		 perm("rum", "", 0);
	 }

	 public static void perm(String str1, String added, int k) {
		 if(added.length() >0) {
			 System.out.println(added);
		 }
		 for(int i=k; i<str1.length(); i++) {
			 perm(str1, added + str1.charAt(i), i+1);			 	
		 }

- Anonymous August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Input: "rum"
Output:
r
ru
rum
rm
u
um
m

public static void main(String[] args) {
		 subsets("rum", "", 0);
	 }
public static void subsets(String str1, String added, int k) {
		 if(added.length() >0) {
			 System.out.println(added);
		 }
		 for(int i=k; i<str1.length(); i++) {
			 perm(str1, added + str1.charAt(i), i+1);
			 	
		 }
	}

- m1 August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//recursive way
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        List<Integer> prefix=new ArrayList<Integer>();
        recurHelper(nums,0,prefix,result);
        return result;
    }
    
    public void recurHelper(int[] nums,int i, List<Integer> prefix,List<List<Integer>> result){
        //base case
        if(i==nums.length){
            result.add(new ArrayList(prefix));
            return;
        }
        int count=0;
        while(i+count<nums.length && nums[i]==nums[i+count]) count++;
        //include nums[i] count times
        for(int c=1;c<=count;c++){
            prefix.add(nums[i]);
            recurHelper(nums,i+count,prefix, result);
        }
        //reset prefix to where a[i] not included at all
        for(int c=1;c<=count;c++){
            prefix.remove(prefix.size()-1);
        }
        //not include nums[i] at all
        recurHelper(nums,i+count,prefix,result);
    }

- andrew October 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

this should do the work(C++)

void solve4(string z)
{
	std::set<string> ssa;

	for(int i=0;i<z.length();i++)
		for(int j=i+1;j<z.length()+1;j++)
		{
			string k=z.substr(i,j);
			if(ssa.find(k)==ssa.end())
			{
				ssa.insert(k);
				cout<<k<<endl;
			}
		}

}

- kkr.ashish February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"all unique subsets" not substrings

- 123 February 11, 2014 | Flag


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