Microsoft Interview Question
Software Engineer / Developersvoid main()
{
int arr[8] = {1, 2, 3};
int i, j, k =1;
for(i=0 ; i<8; i++)
{
printf("{ ");
j = i;
k = 1;
while(j != 0)
{
if(j & 1)
printf("%d ", k);
j = j >> 1;
k = k + 1;
}
printf("}\n");
}
_getch();
}
#include <stdio.h>
#include <stdlib.h>
#define size 4
int arr[size] = {1,2,3,4};
int generate_powerset(int *temparr, int level, int start)
{
int i, j;
for(i=start; i<size; i++)
{
temparr[level] = arr[i];
printf("{ ");
for (j=0; j<=level; j++)
printf("%d ",temparr[j]);
printf("}\n");
if( i < size-1)
generate_powerset(temparr, level+1, i+1);
}
}
int main()
{
printf("{ }\n");
int temparr[size] = {0};
generate_powerset(temparr, 0, 0);
}
another approach could be,
with first no, generate 2 subset, {} and {x}
with 2nd no, add this no to each of the previous subsets and union them ..
with 3rd no, add this to each of the previous subsets, and union them .. and so on ..
so if need all subsets of {x,y,z}
in first iter, {}, {x}
in 2nd iter, {},{x},{y},{x,y}
in 3rd iter, {},{x},{y},{x,y},{z},{x,z},{y,z},{x,y,z}
char ** PowerSet(char *inputSet, int numOfElements)
{
char **outputSet = (char **) malloc((1<<numOfElements) * sizeof(char *));
outputSet[0]= (char *) malloc(2* sizeof(char));
strcpy(outputSet[0]," ");
for(int iCount =0; iCount < numOfElements;iCount++)
{
int elementAdd = 1<<iCount;
int i=0;
while(i<elementAdd)
{
outputSet[elementAdd+i]= (char *) malloc((strlen(outputSet[i]) +2) * sizeof(char));
strcpy(outputSet[elementAdd+i],outputSet[i]);
outputSet[elementAdd+i][strlen(outputSet[i]]=inputSet[iCount];
i++;
}
}
return outputSet;
}
char ** PowerSet_Rec(char *inputSet, int numOfElements)
{
char **resultSet = {{"$"}};
if( '/0' == *inputSet) return resultSet;
char removedChar=inputSet[0];
resultSet = PowerSet_Rec(inputSet+1,numOfElements-1);
Append resultSet AND {removedChar + resultSet}
}
My recursive version
#include<conio.h>
#include<process.h>
#include<string.h>
#include<stdio.h>
int count=0;
void power(char str[],int currinput,int shouldadd,char ptr[],int curroutput)
{
if(currinput==(strlen(str)))
{
if(shouldadd){
ptr[curroutput]=0;
printf("%d:%s\n",count++,ptr);}
return ;
}
if(shouldadd)
{
ptr[curroutput]=str[currinput];
curroutput++;
}
power(str,currinput+1,1,ptr,curroutput);
power(str,currinput+1,0,ptr,curroutput);
}
int main()
{
// clrscr();
char msg[10]="abcd";
char output[10];
printf("Null set\n");
power(msg,0,1,output,0);
power(msg,0,0,output,0);
getch();
}
padhe likhe wala ladka nahi lag rahe ho tum log.............. galat salat program daalkar tez bante ho.............. if u r not a 3rd grade programmer den give a general solution for any no of elements in d set
//print all subsets of a set
//arg = '' >> {}
//arg = 'a' >> {} {a}
//arg = 'ab' >>{} {a} {b} {ab}
// string getSubsets(n) = getSubsets(n - 1) + concatenate to getSubsets(n - 1)
void getSubsets(string& arg, vector<string>& strVec)
{
char ch;
if(arg.size() == 0)
{
strVec.push_back(""); //base case, return empty set
return;
}
if(arg.size() > 0)
{
ch = arg[arg.size() - 1]; //save the last char of the string
arg.pop_back(); //take the last char off the string
getSubsets(arg, strVec); //get subsets generated from string without the last char
}
int curSize = strVec.size();
for(int i = 0; i < curSize; i++)
{
string temp = strVec[i];
strVec.push_back(temp += ch); //concatenate char popped off from end of string to all subsets formed from string - popped character
}
}
int main()
{
string temp = "abc";
vector<string> strVec;
getSubsets(temp, strVec);
for(int i = 0; i < strVec.size(); i++)
cout<<"{"<<strVec[i]<<"}"<<endl;
keep_window_open();
return 0;
}
public class find_all_the_subsets_of_a_given_set {
public static void main(String args[]) {
Integer[] arr = { 1, 2, 3 };
ArrayList<ArrayList<Integer>> ar = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> out_ar = calc_subsets(ar, arr, arr.length - 1);
for (ArrayList<Integer> outer : out_ar) {
for (Integer inner : outer) {
System.out.print(inner + " ");
}
System.out.println();
}
}
public static ArrayList<ArrayList<Integer>> calc_subsets(ArrayList<ArrayList<Integer>> supr_arr, Integer[] arr,
int idx) {
ArrayList<ArrayList<Integer>> nested_arr = supr_arr;
if (idx == 0) {
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.add(arr[idx]);
nested_arr.add(tmp);
return nested_arr;
} else {
nested_arr = calc_subsets(nested_arr, arr, idx - 1);
int count = nested_arr.size();
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.add(arr[idx]);
nested_arr.add(tmp);
for (int i = 0; i < count; i++) {
tmp = new ArrayList<Integer>(nested_arr.get(i));
tmp.add(arr[idx]);
nested_arr.add(tmp);
}
}
return nested_arr;
}
}
Easier Solution:
- Lokesh February 07, 2010Generate 3-bit binary numbers for 0 to 2^3-1, i.e. 0 to 7
BINARY SUBSET
0 0 0 {}
0 0 1 {3}
0 1 0 {2}
0 1 1 {2, 3}
1 0 0 {1}
1 0 1 {1, 3}
1 1 0 {1, 2}
1 1 1 {1, 2, 3}