Facebook Interview Question
Software Engineer / DevelopersCountry: United States
void permutation(int arry[], int n, int k)
{
int total_num_comb = pow(n,k);
for(i=0; i<total_num_comb; i++) // list all the combination
{
for(j=0; j<k; j++)
{
// elements of the set are arry[(i / pow(n,j))%5]
}
}
}
if need to remove set with same value then remove the set if all its element index value is same...
Complexcity of this code O(n*k)
but its better than recursion i guess....
thank you......
#include <stdio.h>
#include <stdlib.h>
int k_org;
int* output;
print()
{
int temp=0;
for(temp=0;temp<k_org;temp++)printf("%d ",output[temp]);
printf("\n");
}
combination(int* input,int size,int k)
{
if(k>size)return;
if(k==0){print(output);return;}
int temp=0;
for(temp=0;temp<size;temp++)
{
output[k-1]=input[temp];
combination(input+temp+1,size-temp-1,k-1);
}
}
main()
{
int input[]={1,2,3,4,5,6,7,8};
int size=sizeof(input)/sizeof(int);
int k=3;k_org=k;
output=(int*)malloc(k*sizeof(int));
combination(input,size,k);
}
non-recursive java:
//assume valid input
int[][] getSubsets(int[] set, int length) {
int temp = length-1; //amount of elements in each subset minus the first element
int size = 0;
for(int i=set.length - temp; i > 0; i--)
size+=i;
int[][] retSet = new int[size][length];
int currset = 0;
for(int i = 0 ; i < set.length - temp; i++) { //gets the starting element of each set
for(int j = i+1; j<set.length; j+= length) {
retSet[currset][0] = set[i]; //set the starting value of the current set
for(int k=j; k<j+length; k++) {
retSet[currset][k-j+1] = set[k]; //k-j +1 to store the second, third...etc. element in the current set
}
currset++;
}
}
public static ArrayList<ArrayList<Integer>> getAllSubSet(int num,int length){
if(length<1){
return null;
}
if(num<1){
return null;
}
if(length>num){
return null;
}
ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
for(int i=1;i!=num+1;i++){
ArrayList<Integer> tmp=new ArrayList<Integer>();
tmp.add(i);
compute_process(num,length,i+1,1,result,tmp);
}
return result;
}
public static void compute_process(int num,int len,
int curNum,int curLen,
ArrayList<ArrayList<Integer>> result,
ArrayList<Integer> current){
if(curNum>num){
if(current.size()==len){
result.add(current);
}
return;
}
if(curLen==len){
result.add(current);
return;
}
ArrayList<Integer> next=copyList(current);
current.add(curNum);
compute_process(num,len,curNum+1,curLen+1,result,current);
compute_process(num,len,curNum+1,curLen,result,next);
}
public static ArrayList<Integer> copyList(ArrayList<Integer> obj){
ArrayList<Integer> result=new ArrayList<Integer>();
for(int i=0;i!=obj.size();i++){
result.add(obj.get(i));
}
return result;
}
Can be done with dynamic programming.
Basically Sol(n,k) = Sol(n-1,k) U "Sol(n-1,k-1) concat {n}"
I am attaching a recursive solution here.
def solve( n, k ) :
if( k > n ) : return [ [] ]
if( k == 0 ) : return [ [] ]
if( k == n ) : return [[ x for x in range( 1, n+1 ) ]]
return solve( n-1, k ) + [ [n] + x for x in solve( n-1, k-1 ) ]
recursive version 2, got rid of "k==n" clause
def solve( n, k ) :
if( k > n ) : return [ ]
if( k == 0 ) : return [ [] ]
return solve( n-1, k ) + [ [n] + x for x in solve( n-1, k-1 ) ]
or iterative one with DP
def solve( n, k ) :
result = {}
for i in range( 0, n+1 ) :
for j in range( 0, k+1 ) :
if( j > i ) : result[ (i,j) ] = [ ]
elif( j == 0 ) : result[ (i,j) ] = [ [] ]
else :
result[ (i,j) ] = result[ (i-1,j) ] + [ [i] + x for x in result[ (i-1,j-1) ] ]
return result[ (n,k) ]
Use Narayan Pandita's algorithm on 0000...11111 where there are n-k zeroes and k ones. It is a bit vector representation of the set.
(C++ has std::next_permutation and std::next_combination for this, I believe).
We can also write a recursive version, which uses linear amount of space (and not Theta(n^k)).
Pseudo code:
//set is the input set.
// set_len is the required length of the subset.
// so_far is the subset we have constructed so far.
// start is the starting point in the set (think of it as an array) of the unconsidered elements.
// Call as Subsets(set, empty_list, required_len, 0);
void Subsets(List set, List so_far, int set_len, int start) {
if (so_far.Length == set_len) {
printList(so_far, 0); // Print the set seen so far.
return;
}
// If we have to pick the rest of elements.
if (so_far.Length + set.Count - start == set_len) {
printList(so_far, 0);
printList(set, start);
return;
}
// Add current element to set seen so far.
so_far.Add(set[start]);
// Recurse
Subsets(set, so_far, set_len, start+1);
// Don't include current element
so_far.Remove(set[start]);
Subsets(set, so_far, set_len, start+1);
// so_far has been restored to what we had been called with.
}
Exercise: Modify the above recursive version to print all subsets of size less than or equal to k.
def subset(numbers, size):
if (size == 0):
raise Exception("size is 0")
if size == 1:
return [[x] for x in numbers]
if len(numbers) < size:
raise Exception("Invalid: len(%s) < size(%d)" % (str(numbers), size))
if len(numbers) == size:
return [numbers]
first = numbers[0]
rest = numbers[1:]
ss = subset(rest, size-1)
[x.append(first) for x in ss]
ss2 = subset(rest, size)
ss.extend(ss2)
return ss
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> ss = subsets(5, 2);
for(ArrayList<Integer> s : ss){
for(Integer i : s)
System.out.print(i + " ");
System.out.println();
}
}
private static ArrayList<ArrayList<Integer>> subsets(int n, int k){
ArrayList<ArrayList<Integer>> ss;
if(k == 1){
ss = new ArrayList<ArrayList<Integer>>();
for(int i=1;i<=n;i++){
ArrayList<Integer> s = new ArrayList<Integer>();
s.add(i);
ss.add(s);
}
return ss;
}else{
ArrayList<ArrayList<Integer>> newss = new ArrayList<ArrayList<Integer>>();
ss = subsets(n, k-1);
for(ArrayList<Integer> s : ss){
for(int i = s.get(s.size() - 1) + 1; i <= n; i++){
ArrayList<Integer> news = (ArrayList<Integer>) s.clone();
news.add(i);
newss.add(news);
}
}
return newss;
}
}
#include <iostream>
using namespace std;
const int MAX = 1000;
int a[MAX];
bool b[MAX];
void f1(int n, int k, int indexn, int indexk){
int i, j;
for(i = indexn; i <= n - k + indexk; i++){
if(!b[i]) {
b[i] = true;
a[indexk] = i;
if(indexk == k) {
for(j = 1; j <= k; j++) {
printf("%d ", a[j]);
}
printf("\n");
} else {
f1(n, k, indexn + 1, indexk + 1);
}
b[i] = false;
}
}
}
void f(int n, int k) {
int i;
for(i = 1; i <= n; ++i) {
a[i] = i;
b[i] = false;
}
f1(n, k, 1, 1);
}
int main() {
f(4,2);
return 0;
}
<?php
function myprint($index,$max,$deep,$max_deep,$array) {
if($deep == $max_deep) {
echo "{";
$flag = false;
foreach($array as $value) {
if($flag === true)
echo ",";
$flag = true;
echo $value;
}
echo "}\n";
}
for($id = $index+1; $id <= $max ;$id ++) {
$array []= $id;
myprint($id,$max,$deep+1,$max_deep,$array);
array_pop($array);
}
}
myprint(0,10,0,2,array());
?>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
void print_comb(string temp,int i,int j,int k)
{
if(j-i+1<k || k==0)
{
cout << temp<<endl;
return;
}
char ch[50];
string rem=temp;
for(int a=i;a<=j-k;a++)
{
sprintf(ch,"%d",a);
temp=rem;
temp+=ch;
print_comb(temp,a+1,j,k-1);
}
}
int main()
{
int n,k;
cout << "Enter n : ";
cin >> n;
cout << "Enter k : ";
cin >> k;
print_comb("",1,n,k);
return 0;
}
#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <vector>
using namespace std;
vector<vector<int> > calcCombinations(vector<int> ip){
vector<vector<int> > op;
if(ip.size() <= 2){
op.push_back(ip);
return op;
}
vector<int> res;
while(ip.size() > 0){
int num = ip.back();
ip.pop_back();
for(int j = 0; j<ip.size(); j++){
res.clear();
res.push_back(num);
res.push_back(ip[j]);
op.push_back(res);
}
}
return op;
}
int main(){
int input[] = {16, 25, 30, 5, 7};
vector<int> ip(input, input + sizeof(input)/sizeof(int));
vector<vector<int> > op = calcCombinations(ip);
int num1, num2;
vector<int> res;
while(!op.empty()){
res = op.back();
op.pop_back();
num1 = res.back();
res.pop_back();
num2 = res.back();
res.pop_back();
cout<<num1<<", "<<num2<<endl;
}
getch();
return EXIT_SUCCESS;
}
Rather than generating all subsets in 2^n time we can do an C(n, k) algorithm for k size subset generation
HashSet<HashSet<Integer>> allSetSizeK(int[] A, int k) {
boolean[] M = new boolean[A.length];
HashSet<HashSet<Integer>> result = new HashSet<HashSet<Integer>>();
setSizeK(result, A, 0, 0, k, M);
return result;
}
void setSizeK(HashSet<HashSet<Integer>> result, int[] A, int count, int index, int k, boolean[] M) {
if (count == k) {
HashSet<Integer> h = new HashSet<Integer>();
for (int i = 0; i < index; i++) {
if (M[i])
h.add(A[i]);
}
result.add(h);
return;
}
if (index == A.length)
return;
M[index] = true;
setSizeK(result, A, count + 1, index + 1, k, M);
M[index] = false;
setSizeK(result, A, count, index + 1, k, M);
}
Here is my answer. For each element of the array, we have two options, use it or not use it. So we can use an additional array to store the options.
public static void findSubSet(int[] n, int k){
boolean[] usedIndex = new boolean[n.length];
print(n, k , usedIndex, 0, 0);
}
private static void print(int[] n, int k, boolean[] usedIndex, int currentSize, int startIndex) {
if(currentSize == k) {
System.out.print("{");
for(int i = 0; i < n.length; i++) {
if(usedIndex[i])
System.out.print(n[i]+" ")
}
System.out.print("}");
System.out.println();
return;
}
if (startIndex == n.length)
return;
// first option, we use the current item
usedIndex[startIndex] = true;
print(n, k, usedIndex, currentSize+1, startIndex+1);
// Second option, we don't use the current item
usedIndex[startIndex] = false;
print(n, k , usedIndex, currentSize, startIndex+1);
}
public static void subset(List<Integer> list, int n, int k, int count, int cursor, int cursor2, int[] result)
{
if (cursor >= k)
{
if (count == k)
{
System.out.println(Arrays.toString(result));
}
return;
}
for (int i = cursor2; i < n; i++)
{
result[cursor] = list.get(i);
subset(list, n, k, count+1, cursor+1, i+1, result);
}
}
#include<iostream>
using namespace std;
void permutation(char *A,char *x,int k,int m){
int i;
if (k==m){
x[k]='\0';
cout<<x<<"\t";
}
else{
for(i=0;A[i]!='\0';i++) {
x[k]=A[i];
permutation(A,x,k+1,m);
}
}
}
int main(){
char A[]={'1','3','a','s','t','i','\0'};
char x[5];
int k,m=4;
permutation(A,x,1,m);
return 0;
}
#include<iostream>
using namespace std;
void permutation(char *A,char *x,int k,int m){
int i;
if (k==m){
x[k]='\0';
cout<<x<<"\t";
}
else{
for(i=0;A[i]!='\0';i++) {
x[k]=A[i];
permutation(A,x,k+1,m);
}
}
}
int main(){
char A[]={'1','3','a','s','t','i','\0'};
char x[5];
int k,m=4;
permutation(A,x,1,m);
return 0;
}
- shailendraagarwal11 February 10, 2013