Facebook Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
Remove dups from string and then user simple algo which based on binary representation on subset.
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
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();
}
}
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.
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);
}
}
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;
}
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:])
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:])
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:])
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;
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);
}
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);
}
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);
}
}
//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);
}
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;
}
}
}
def print_substr (string):
- swanh February 11, 2014strset = 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