## Amazon Interview Question

SDE-2s**Country:**India

```
int[][] multiplied;
int increment = 0;
public int[][] MultiplyRecursion(int[][] toMultiply) {
multiplied = new int[(((toMultiply.length * toMultiply.length) - toMultiply.length) / 2)*4][2];
for (int i = 0; i < toMultiply.length; i++) {
RecuAdd(i,i+1, 0,toMultiply);
}
return multiplied;
}
public void RecuAdd(int i, int m, int n, int[][] toMultiply) {
if (m == toMultiply.length) {
m = i+1;
n=n+1;
}
if (n==2 || i == toMultiply.length-1)
return;
multiplied[increment] = new int[]{toMultiply[i][n],toMultiply[m][0]};
increment+=1;
multiplied[increment] = new int[]{toMultiply[i][n],toMultiply[m][1]};
increment+=1;
RecuAdd(i,m+1,n,toMultiply);
}
```

Similar idea:

```
function mult(left, rest, index) {
if (rest.length === index) {
console.log(left);
return;
}
var current = rest[index];
for(var i = 0; i < current.length; ++i) {
left.push(current[i]);
mult(left, rest, index + 1);
left.pop();
}
}
var tests = [
[],
[
['a', 'b'],
['c', 'd']
],
[
['a', 'b'],
['c', 'd'],
['e', 'f']
],
];
tests.forEach(function(test) {
mult([], test, 0);
//0: []
//1: ["a", "c"] ["a", "d"] ["b", "c"] ["b", "d"]
//2: ["a", "c", "e"] ["a", "c", "f"]["a", "d", "e"]["a", "d", "f"]["b", "c", "e"]["b", "c", "f"]["b", "d", "e"]["b", "d", "f"]
})
```

Here is a non recursive solution:

```
function mult(input) {
var left = input.length ? input.shift() : [];
while(input.length) {
var temp = [];
for(var i = 0; i < left.length; ++i) {
for(var j = 0; j < input[0].length; ++j) {
var item = (left[i] + input[0][j]);
temp.push(item);
}
}
input.shift();
left = temp;
}
return left;
}
var tests = [
[],
[
['a', 'b'],
['c', 'd']
],
[
['a', 'b'],
['c', 'd'],
['e', 'f']
],
];
tests.forEach(function(test) {
console.log( mult(test) );
});
```

```
/* The recursive formulation is too easy
So, let's improve on that.
Observe the problem can be recursively formulated
as cardinal product of two lists, left one, is a conjugate
(items themselves may be list), while right ine is a primitive one.
Thus, simple for loop suffices, which then yields the left list
for the next iteration.
*/
def _cross_( conjugate, primitive ){
result = list()
for ( l : conjugate ){
for ( r : primitive ){
// concatenate these lists
row = list(l)
row += r
result.add(row)
}
}
result // return them
}
def cross( arr_of_arr ){
if ( size(arr_of_arr ) <= 0 ) return [] // fixed
cur_index = 0
// generate left list, conjugate
left_list = list ( arr_of_arr[cur_index] ) as { list( $.o ) }
cur_index += 1
while ( cur_index < size(arr_of_arr) ){
left_list = _cross_(left_list,arr_of_arr[cur_index] )
cur_index += 1
}
left_list // return... and we are good
}
// sample test case
a = [ [ 'a' , 'b' ] , [ 'c' , 'd' ] ]
r = cross( a )
println(r)
```

just do the symbolic multiplication by following the recursion

the code

- ChrisK September 13, 2017