CareerCup

Iterative than recursive?


Cross( int *s1, int *s2, int *31, int noOfSets, int s1length,int s2length,int s3length)
{

Iterative than recursive?

Cross( int *s1, int *s2, int *s3, int noOfSets, int s1length,int s2length,int s3length)
{
int temp[noOfSets];
for (int i=0;i<s1length;i++)
{
int digit = 0;
temp[digit] = s1[s1length];
for (int j=0;i<s2length;i++)
{
digit =1;
temp[digit] = s2[s2length];
for (int i=0;i<s3length;i++)
{
digit = 2;
temp[digit] = s3[s3length];
for (len =0; len<noOfSets;len++)
{
cout<<temp[len];
}
cout<<endl;
}
}
}

effectively you would call s1length * s2length *s3length number of times to receive a cross each time.

so 2*2*3 = 12 cross combinations.

you would have called
int s1array[2] = {1,2};
int s2array[2] = {3,4};
int s3array[3] = {5,6,7};
cross(&s1array,&s2array,&s3array,3,2,2,3);

Please disregard the previous programs which had lotsa typos which might have confused you to be logical errors. This one compiles. Hard coding can be improved though.

#include <iostream>
using namespace std;

void Cross( int *s1, int *s2, int *s3, int noOfSets, int s1length,int s2length,int s3length)
{
int l_noOfSets =3;
int temp[3];
for (int i=0;i<s1length;i++)
{
int digit = 0;
temp[digit] = s1[i];
for (int j=0;j<s2length;j++)
{
digit =1;
temp[digit] = s2[j];
for (int k=0;k<s3length;k++)
{
digit = 2;
temp[digit] = s3[k];
for (int len =0; len<l_noOfSets;len++)
{
cout<<temp[len];
}
cout<<endl;
}
}
}
}

int main()
{
int s1array[2] = {1,2};
int s2array[2] = {3,4};
int s3array[3] = {5,6,7};
Cross(s1array,s2array,s3array,3,2,2,3);
return 0;
}

@king kong

Dude so r u going to use 'n' no of for loops if there are 'n' sets.. I have done the program this way during my interview but my interviewer told me that it was not an efficient way. here is my code below.


#include <iostream>
using namespace std;

int main()
{
int array1[] = {1,2};
int array2[] = {3,4};
int array3[] = {5,6,7};

int i,j,k;

printf("The final cross product of my lists is below\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
for(k=0;k<3;k++)
{
printf("%d %d %d",array1[i],array2[j],array3[k]);
printf("\n");
}

}

}

return 0;
}

Take different sets in separate single link lists:
list1: 1->2
list2: 3->4
list3: 5->6->7

Following function can be helpful:

void cal( list * l1 , list *l2 ,list* l3)
{
if(l3 == NULL)
return;
cout << l1->data << l2->data << l3->data <<endl;
cal(l1 , l2 , l3->next);
if (l2== NULL)
return;
cal(l1, l2->next , l3);

if(l3==NULL)
return;
cal(l1->next, l2, l3);
}

You need a recursive solution to this problem to generate all possible permutations.

Check out the phone string problem:
question?id=7712670

My solution for that problem is at the bottom of the page. This problem is similar.

My solution:

recursion(sets, resultSet){
     if(sets.size() == 0)
          return resultSet;
     else{
          topSet = sets.getSet();
          sets.remove(topSet);
          for-each element in topSet{
               recursion(sets, resultSet + element);
          }   
     }
}

import java.util.*;

public class SetsCrossProduct {

public static void main(String[] args) {
ArrayList<List<Integer>> sets = new ArrayList<List<Integer> >();
ArrayList<Integer> set1 = new ArrayList<Integer>();set1.add(1);set1.add(2);set1.add(3);
ArrayList<Integer> set2 = new ArrayList<Integer>();set2.add(5);
ArrayList<Integer> set3 = new ArrayList<Integer>();set3.add(6);set3.add(7);set3.add(8);set3.add(9);
sets.add(set1);sets.add(set2);sets.add(set3);
recurse(sets, sets.size(), 0, "");

}

public static void recurse (List<List<Integer> > sets,int n, int curSet, String s) {
for( int i = 0; i < sets.get(curSet).size(); i++) {
if ( curSet == n-1 ){
System.out.println(s+sets.get(curSet).get(i));
} else
recurse(sets, n, curSet+1, s+sets.get(curSet).get(i));
}
}

}

my solution:
:\_

meaning kick the interviewer for asking such tough questions

import java.util.*;

public class SetsCrossProduct {

	public static void main(String[] args) {
		ArrayList<List<Integer>> sets = new ArrayList<List<Integer> >();
		ArrayList<Integer> set1 = new ArrayList<Integer>();set1.add(1);set1.add(2);set1.add(3);
		ArrayList<Integer> set2 = new ArrayList<Integer>();set2.add(5);
		ArrayList<Integer> set3 = new ArrayList<Integer>();set3.add(6);set3.add(7);set3.add(8);set3.add(9);
		sets.add(set1);sets.add(set2);sets.add(set3);
		recurse(sets, sets.size(), 0, "");
		
	}
	
	public static void recurse (List<List<Integer> > sets,int n, int curSet, String s) {
		for( int i = 0; i < sets.get(curSet).size(); i++) {
			if ( curSet == n-1 ){
				System.out.println(s+sets.get(curSet).get(i));
			} else 
				recurse(sets, n, curSet+1, s+sets.get(curSet).get(i));
		}
	}

}

Can someone tel me how to solve this problem in C? Please provide me a better algo...

I write this in java

public class Main {

    
    static int sets [][]={{1,2},{3,4},{5,6,7}};
    static int count=0;
    
    public static void main(String[] args) 
    {
        // TODO code application logic here
        int a[]=new int[sets.length];
        crossProduct(a,0, sets.length);
        System.out.print("\n\nTotal Products "+count);
    }

    static void crossProduct(int[]a,int index,int n)
    {
        if(index==n)
        {
            System.out.print("\n");
            count++;
            for(int i=0;i<a.length;i++)
                System.out.print(a[i]+" ");
            return;
        }
        for(int j=0;j<sets[index].length;j++)
        {
            a[index]=sets[index][j];
            crossProduct(a,index+1,n);
        }
    }
}