Facebook Interview Question
Software Engineer / DevelopersTwo solutions, one with complexity 2^n and the other with n!
Soln 1:
//input
arr[]
k
vector<set<string> > s;
void generateSets(set<int> v,int n,int ind) {
if(n == k) {
s.push_back(v);
}
if(ind == v.size()) return;
else {
generateSets(v,n+1,ind+1);
v.insert(arr[ind])
generateSets(v,n+1,ind+1);
}
}
//method call
generateSets(new set<int>(),0,0);
Soln 2:
//input
vector<int> arr
k
vector<set<int> > generateSets() {
sort(arr.begin(),arr.end());
set<int> s;
do {
for(int i=0;i<k;i++) {
v.insert(arr[i]);
}
s.push_back(v);
} while(next_permutation(arr.begin(),arr.end()));
}
#define SUBSET_LENGTH 3
void generateSubset(int array[], int subset[], int used[], int length, int index, int lastoffset)
{
int k;
if (index == SUBSET_LENGTH)
{
printf("subset %d%d%d\n", subset[0], subset[1], subset[2]);
return;
}
for (k = 0; k < length; k++)
{
if (used[k]) continue;
if (k < lastoffset) continue;
subset[index] = array[k];
used[k] = 1;
generateSubset(array, subset, used, length, index + 1, k);
used[k] = 0;
}
}
int main()
{
int array[4] = {1, 2, 3, 4};
int used[4];
int subset[SUBSET_LENGTH];
memset((void *)used, 0, sizeof(array)/sizeof(int));
memset((void *)subset, 0, SUBSET_LENGTH);
generateSubset(array, subset, used, sizeof(array)/sizeof(int), 0, 0);
return 0;
}
//Given an array, this function finds the startIdx of subset array of size k
// The indices are stored in the startId vector
// Recursively call
void FindSubset(int curPos, int k, int arraySize, vector<int>& startId)
{
if(curPos+k > arraySize)
return;
startId.push_back(curPos);
curPos++;
FindSubset(curPos, k, arraySize, startId);
}
int main ()
{
vector<int> startId;
int k = 4;
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
FindSubset(0, k, 10, startId);
int sizeSubSets = startId.size();
cout << "total subsets found:" << sizeSubSets << endl;
for(int i=0; i < sizeSubSets; i++)
{
int currPos = startId[i];
cout << "SubsetArray= {";
for(int j=currPos; j < currPos+k; j++)
{
cout << arr[j] << " ";
}
cout << "}" << endl;
}
return 0;
}
The simplest way is to think recursively..
method signature : allsubets(int[] input, i, k);
here i denotes the starting index of the input array to consider and k denotes the size of subsets to generate.
subsets_1 = allsubset(input, i+1, k-1) /* use i. */
for (subset s : subsets_1)
add input[i] to s
subsets_2 = allsubsets(input, i+1, k-1) /* don't use i */
return combine(subsets_1, subsets_2);
Note: not handling trivial case. Its easy enough.
Also we can easily memoize this.
#include <stdio.h>
void subarray(int arr[], int t[], int n, int ind, int k, int kk) {
int i;
if (n == 0)
return;
if (kk == k) {
for (i = 0; i < kk; i++)
printf("%d ", t[i]);
printf("\n");
return;
}
if (n - ind < k - kk)
return;
t[kk] = arr[ind];
subarray(arr, t, n, ind + 1, k, kk + 1);
subarray(arr, t, n, ind + 1, k, kk);
}
int main() {
int i, arr[100], t[100], n, k;
do {
printf("Enter array size:");
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", arr + i);
printf("Enter sub-array-size:");
scanf("%d", &k);
subarray(arr, t, n, 0, k, 0);
} while(n);
}
public class Set {
int[] elem;
int size;
Set(int n) {
elem = new int[n];
}
public Set clone() {
Set temp = new Set(elem.length);
int[] clonedElem = elem.clone();
int clonedSize = size;
temp.elem = clonedElem;
temp.size = clonedSize;
return temp;
}
public void add(int n) {
elem[size]=n;
size++;
}
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append("{");
for(int i=0;i<size;i++) {
sb.append(elem[i]);
sb.append(",");
}
sb.append("}");
return sb.toString();
}
}
public List<Set> setsOfSizeK(int[] a,int index, int k, Set s) {
List<Set> ls=new ArrayList<Set>();
for(int i=index;i<=a.length;i++) {
if(k>0 && i< a.length) {
Set temp = s.clone();
temp.add(a[i]);
List<Set> res = setsOfSizeK(a,i+1,k-1,temp);
if(!res.isEmpty())
ls.addAll(res);
} else if(k==0 && i<= a.length) {
ls.add(s);
break;
}
}
return ls;
}
@Test
public void testSetsOfSizeK() {
int[] a = {1,2,3,4};
List<Set> l = setsOfSizeK(a,0,2,new Set(2));
System.out.print(l.size());
}
I think it can be done in O(kn) where k is subarray size and n is the given array size.
Let A be the array of numbers with size n.
Let C be an array such that C[i,j] contains the possible subsets of size j from array A with size i.
We want C[n,k]. We will find it by Dynamic Programming using Memoized version.
Here is the algorithm:
SET(A,n,k)
for i<-1 to n
f
C[i,1]={A[i]}
for j<-1 to n
for i<-1 to k
C[j,i]=empty set
return MEMOIZED(A,C,n,k)
MEMOIZED(A,C,n,k)
if k=0 or n=0
C[n,k]=empty set
else if k=1 and C[n,k]=empty set
for j<-1 to n
C[n,k]=C[n,k] U {A[j]}// here U adds subset {A[j]} to set of subsets in C[n,k]
return C[n,k]
if n<k
return C[n,k]
if n=k
C[n,k]= MEMOIZED(A,C,n-1,k-1) U A[n] //here U will add A[n] to every subset in C[n-1,k-1]
else
C[n,k]= MEMOIZED(A,C,n-1,k) U (MEMOIZED(A,C,n-1,k-1) U A[n])
return C[n,k]
Clearly we reach each box in array C only once .So Time Complexity is O(kn)
Solution in C#:
using System;
using System.Collections.Generic;
public class Program
{
public static List<List<int>> sets = new List<List<int>>();
public static void FindSubsets(int[] superSet, int K)
{
FindSubsets(superSet, K, 0, new List<int>());
}
private static void FindSubsets(int[] superSet, int K, int index, List<int> set)
{
if (set.Count == K)
{
sets.Add(new List<int>(set));
return;
}
if (index == superSet.Length) return;
int num = superSet[index];
set.Add(num);
FindSubsets(superSet, K, index + 1, set);
set.Remove(num);
FindSubsets(superSet, K, index + 1, set);
}
public static void Main()
{
var nums = new int[] { 1, 2, 3, 4, 5, 6 };
FindSubsets(nums, 3);
foreach(var set in sets)
{
foreach (var num in set) Console.Write(num);
Console.WriteLine();
}
Console.ReadLine();
}
}
Here's code in C#.
- Anonymous September 07, 2011