Adobe Interview Question
MTSsCountry: India
Interview Type: In-Person
Its a modification of combinations algorithm, just that we need subsets of "r" elements. Just trace it down its pretty simple and straight forward.
I don't know python, so finding it difficult to understand. Can you transform it in c,c++ or java....
nitingupta180, he it is in Java:
public static void main(String[] args) {
int[] a = {5, 4, 2, 8, 6, 0};
int subGroupLength = 3;
int[] used = new int[subGroupLength];
Arrays.fill(used, -1);
allSubGroups(a, used, 0, 0);
}
public static void allSubGroups(int[] a, int[] used, int startIndex, int usedCount){
if(usedCount == used.length){
for(int i = 0; i < usedCount; i++)
System.out.print(a[used[i]]+" ");
System.out.println();
}else{
for(int i = startIndex; i < a.length; i++){
used[usedCount] = i;
allSubGroups(a, used, i+1, usedCount+1);
used[usedCount] = -1;
}
}
}
int giMask[100],giNoCom;
void printCombination(int piList[],int piLenList)
{
giNoCom++;
cout<<"{ ";
for(int liLocalIndex=0;liLocalIndex<=piLenList;liLocalIndex++)
{
if(giMask[liLocalIndex]==1)
{
cout<<" "<<piList[liLocalIndex]<<" ";
}
}
cout<<" } "<<endl;
}
void PrintPermutation(int piList[],int piCurrIndex,int piLenList,int piCount)
{
piCount--;
if(piCount)
{
giMask[piCurrIndex]=1;
for(int liLocalIndex=piCurrIndex+1;liLocalIndex<=piLenList;liLocalIndex++)
{
if((piLenList-liLocalIndex+1)>=piCount)
PrintPermutation(piList,liLocalIndex,piLenList,piCount);
}
giMask[piCurrIndex]=0;
}
else if(piCount==0)
{
giMask[piCurrIndex]=1;
printCombination(piList,piLenList);
giMask[piCurrIndex]=0;
}
}
int main()
{
int liList[]={6,2,4,8,9,10,16,20};
int liListLen=7,licount=4;
for(int liLocalIndex=0;liLocalIndex<=liListLen;liLocalIndex++)
{
PrintPermutation(liList,liLocalIndex,liListLen,licount);
}
cout<<"the total no of combination is "<<giNoCom<<endl;
return 0;
}
is this fine ?
C#
public static void PrintCombinations(int[] arr, int r, int start, string prv)
{
if (r == 1)
while (start < arr.Length)
Console.Write(@"{0} {1}{2}", prv, arr[start++], Environment.NewLine);
else
while (start < arr.Length)
PrintCombinations(arr, r - 1, start + 1, string.Format(@"{0} {1}", prv, arr[start++]));
}
working code
#include<iostream>
using namespace std;
void printsubset(int a[],int n,int start)
{ if(start==n) return;
for(int i=start;i<n-1;i++)
cout<<a[start]<<" "<<a[i+1]<<"\n";
printsubset(a,n,start+1);
}
int main()
{ int a[20]={6,2,4,8,9,10,16,20};
int n=8;
printsubset(a,n,0);
system("pause");
return 0;
}
try in devcpp
This thing worked for me, though added some extra lines at the end:
#include <iostream>
#include <vector>
using namespace std;
int iter=1;
int r=3;
void comb(int i,vector<int> a)
{
for (int j=i;j<a.size();j++)
{
if(iter==r)
cout<<"Variable iterations with iteration"<<iter<<":"<<a[j]<<" "<<endl;
else
{
cout<<"Fix Values for this iteration with iteration"<<iter<<":"<<a[j]<<endl;
iter++;
comb(j+1,a);
}
}
iter-=1;
cout<<endl;
}
int main()
{
vector<int> a;
a.push_back(5);
a.push_back(8);
a.push_back(9);
a.push_back(3);
a.push_back(0);
int i=0;
comb(i,a);
return 0;
}
#include<stdio.h>
/* A utility function that prints a given arr[] of length size*/
void printArray(int arr[], int size)
{
for(int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
return;
}
/* The core function that recursively generates and prints all sequences of
length k */
void printSequencesRecur(int a[],int arr[], int n, int k, int index)
{
int i;
if (k == 0)
{
printArray(arr, index);
}
if (k > 0)
{
for(i = 0; i<n; ++i)
{
arr[index] = a[i];
printSequencesRecur(a,arr, n, k-1, index+1);
}
}
}
/* A function that uses printSequencesRecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
void printSequences(int a[],int n, int k)
{
int *arr = new int[k];
printSequencesRecur(a,arr, n, k, 0);
delete(arr); // free dynamically allocated array
return;
}
/* Driver Program to test above functions */
int main()
{
int a[]={2,8,9,16};
int n = 3;
int k = 2;
printSequences(a,4,k);
getchar();
return 0;
}
public class CombinationArray {
int temp[];
public void printCombination(int arr[],int setSize){
temp=new int[setSize];
permute(arr,0,0);
}
public void permute(int arr[],int start,int tempstart){
if(tempstart==temp.length){
System.out.print("{");
for(int i=0;i< temp.length;i++){
System.out.print(temp[i] +" ");
}
System.out.println("}");
return;
}
for(int i=start;i<arr.length;i++){
temp[tempstart]=arr[i];
permute(arr,i+1,tempstart+1);
}
}
}
#include<iostream>
using namespace std;
void print(int a[],int temp[],int start,int n,int index,int r)
{
if(index==r) //i wish this helps..
{
for(int i=0;i<r;i++)
{
cout<<temp[i]<<" ";
}
cout<<"\n";
return;
}
for(int i=start;i<n&&n-i>=r-index;i++)
{
temp[index]=a[i];
print(a,temp,i+1,n,index+1,r);
}
return;
}
void print_combinations(int a[],int n,int r)
{
int temp[r];
print(a,temp,0,n,0,r);
}
int main()
{
int *a,n,r;
cout<<"enter the size of the array. \n";
cin>>n;
a=new int[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"Enter the value of r. \n";
cin>>r;
print_combinations(a,n,r);
return 0;
}
public class CombinationArray {
int temp[];
//call this method
public void printCombination(int arr[],int setSize){
temp=new int[setSize];
permute(arr,0,0);
}
public void permute(int arr[],int start,int tempstart){
if(tempstart==temp.length){
System.out.print("{");
for(int i=0;i< temp.length;i++){
System.out.print(temp[i] +" ");
}
System.out.println("}");
return;
}
for(int i=start;i<arr.length;i++){
temp[tempstart]=arr[i];
permute(arr,i+1,tempstart+1);
}
}
}
Python code:
uses extra O(r) space.
- sivabasava October 05, 2012