Microsoft Interview Question
Software Engineer / Developers#include <iostream>
using namespace std;
void combination(int combindex);
const int arysize = 5;
const int outsize = 3;
int ary[] = {1,2,3,4,5};
bool used[arysize];
int comb[outsize];
int main(void){
for(int i = 0;i<arysize;i++){
used[i] = false;
}
combination(0);
}
void combination(int combindex){
for(int i=0;i<arysize;i++){
if(used[i] == false){
comb[combindex] = ary[i];
used[i] = true;
}
else
continue;
if(combindex == outsize-1){
for(int j = 0;j<outsize;j++){
cout <<comb[j]<<",";
}
cout << endl;
}
else{
combination(combindex+1);
}
used[i] = false;
}
}
Can the following be a solution?
if the array is 1234 and say k is 3.
then we have to output 123,234,341,412.
#include<stdio.h>
int main()
{
int a[10];
int i,j,k=3;
for(i=0;i<10;i++)
a[i]=i;
printf("\n");
printf("\nThe array elements are");
for(i=0;i<10;i++)
{
printf("%d->",a[i]);
}
printf("\n");
for(i=0;i<10;i++)
{
for(j=i;j<i+k;j++)
{
printf("%d ",(a[j]%10));
}
printf("\n");
}
return 0;
}
void PrintAllSubsets(int A[], int nALen, int B[], int nBLen, int k)
{
if (nALen <=0 || nBLen <= 0)
return ;
if (nBLen == 1)
{
for (int i=0; i<nALen; ++i)
{
B[0] = A[i];
printf("%s", "sub-array : ");
for (int j=0; j<k; ++j)
printf("%d ", B[j-k+1]);
printf("%s\n", " ");
}
}
for (int i=0; i<nALen-nBLen+1; ++i)
{
B[0] = A[i];
PrintAllSubsets(&A[i+1], nALen-(i+1), &B[1], nBLen-1, k);
}
}
// Sample
const int ALen = 10;
const int BLen = 3;
int A[ALen], B[BLen];
for (int i=0; i<ALen; ++i)
A[i] = i;
PrintAllSubsets(A, ALen, B, BLen, BLen);
bool Combination(int *arr, int n, int k)
{
if(arr == NULL || n =< 0 || k =< 0 || k>n)
return false;
int *result = new int[k];
DoCombination(arr,n,result,k,0,0);
delete[] result;
}
void DoCombination(int *arr, int n, int* result, int k, int pos, int count)
{
if(arr == NULL || result == NULL || n <= 0 || k <= 0 || k>n || pos >= k || count >= n)
return;
for(int i=count; i<=(n-k-pos), i++)
{
result[pos] = a[i];
if(pos == k-1)
{
PrintBuffer(result,k);
continue;
}
DoCombine(arr,n,result,k,pos+1,count+1);
}
}
Here is my version
#include <stdio.h>
void combinations(char * str, int start, int * result, int len, int k, int count);
void main()
{
int i=0,k=0, count = 0;
char str[100];
printf("Enter the string \n");
gets(str);
printf("Enter the size of the combinations to be produced \n");
scanf("%d", &k);
while(str[i] != '\0')
i++;
int result[100];
combinations(str,0, result, i, k, count);
printf("\n");
}
void combinations(char * str, int start, int * result, int len, int k, int count)
{
if(start == len)
{
if(k==count)
{
printf("\n");
for(int j=0;j<len;j++)
if(result[j] == 1)
printf("%c", str[j]);
}
return;
}
for(int i=0;i<2;i++)
{
if(i && count <= k)
{
result[start] = 1;
count++;
}
else
result[start] = 0;
combinations(str,start+1,result,len,k,count);
}
}
Subset(char arr[], int k, int count, int size){
if count == size print ith element with X[i] = 1; return;
if k> length(arr) print ith element with X[i] = 1; return; // subset with size less than 'size'
x[k] =1: subset ( arr, k+1, count +1 ,size);
x[k] =0; subset ( arr, k+1, count, size);
}
This is a typical combinatorial search algorithm. Find all possible subsets and only print out subset with length k.
- vodangkhoa November 13, 2007