Amazon Interview Question
SDE-2sCountry: 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)
Multiplication using expansion, written in C++98.
#include <vector>
#include <iostream>
using namespace std;
void display(vector<vector<char> > result){
cout << "{ ";
for(int i = 0; i < result.size(); i++){
cout << "{ ";
for(int j = 0; j < result[i].size(); j++)
(j != result[i].size() - 1) ? cout << result[i][j] << ", " : cout << result[i][j] << " }";
(i != result.size() - 1) ? cout << ", " : cout << " ";
}
cout << "}\n";
}
void expand(vector<vector<char> >& original, int ext){
if(ext == 0)
return;
int size = original.size();
for(int j = 0; j < ext; j ++)
for (int i = 0; i < size; i++)
original.push_back(original[i]);
}
void multiply(vector<char> set, vector<vector<char> >& result){
if(result.empty()){
for(int i = 0; i < set.size(); i++){
vector<char> re = vector<char>();
re.push_back(set[i]);
result.push_back(re);
}
}
else{
int size = result.size();
expand(result, set.size() - 1);
for(int i = 0; i < set.size(); i++)
for(int j = 0; j < size; j++)
result[i * size + j].push_back(set[i]);
}
}
void multiply(vector<vector<char> > charset, vector<vector<char> >& result){
if(charset.empty())
return;
for (int i = 0; i < charset.size(); i++)
multiply(charset[i], result);
}
int main(){
vector<vector<char> > charset = vector<vector<char> >();
vector<char> set1 = vector<char>();
set1.push_back('a');
set1.push_back('b');
vector<char> set2 = vector<char>();
set2.push_back('c');
set2.push_back('d');
vector<char> set3 = vector<char>();
set3.push_back('e');
set3.push_back('f');
charset.push_back(set1);
charset.push_back(set2);
charset.push_back(set3);
vector<vector<char> > result = vector<vector<char> >();
multiply(charset, result);
display(result);
return 0;
}
#include <vector>
#include <iostream>
using namespace std;
void display(vector<vector<char> > result){
cout << "{ ";
for(int i = 0; i < result.size(); i++){
cout << "{ ";
for(int j = 0; j < result[i].size(); j++)
(j != result[i].size() - 1) ? cout << result[i][j] << ", " : cout << result[i][j] << " }";
(i != result.size() - 1) ? cout << ", " : cout << " ";
}
cout << "}\n";
}
void expand(vector<vector<char> >& original, int ext){
if(ext == 0)
return;
int size = original.size();
for(int j = 0; j < ext; j ++)
for (int i = 0; i < size; i++)
original.push_back(original[i]);
}
void multiply(vector<char> set, vector<vector<char> >& result){
if(result.empty()){
for(int i = 0; i < set.size(); i++){
vector<char> re = vector<char>();
re.push_back(set[i]);
result.push_back(re);
}
}
else{
int size = result.size();
expand(result, set.size() - 1);
for(int i = 0; i < set.size(); i++)
for(int j = 0; j < size; j++)
result[i * size + j].push_back(set[i]);
}
}
void multiply(vector<vector<char> > charset, vector<vector<char> >& result){
if(charset.empty())
return;
for (int i = 0; i < charset.size(); i++)
multiply(charset[i], result);
}
int main(){
vector<vector<char> > charset = vector<vector<char> >();
vector<char> set1 = vector<char>();
set1.push_back('a');
set1.push_back('b');
vector<char> set2 = vector<char>();
set2.push_back('c');
set2.push_back('d');
vector<char> set3 = vector<char>();
set3.push_back('e');
set3.push_back('f');
charset.push_back(set1);
charset.push_back(set2);
charset.push_back(set3);
vector<vector<char> > result = vector<vector<char> >();
multiply(charset, result);
display(result);
return 0;
}
#include <vector>
#include <iostream>
using namespace std;
void display(vector<vector<char> > result){
cout << "{ ";
for(int i = 0; i < result.size(); i++){
cout << "{ ";
for(int j = 0; j < result[i].size(); j++)
(j != result[i].size() - 1) ? cout << result[i][j] << ", " : cout << result[i][j] << " }";
(i != result.size() - 1) ? cout << ", " : cout << " ";
}
cout << "}\n";
}
void expand(vector<vector<char> >& original, int ext){
if(ext == 0)
return;
int size = original.size();
for(int j = 0; j < ext; j ++)
for (int i = 0; i < size; i++)
original.push_back(original[i]);
}
void multiply(vector<char> set, vector<vector<char> >& result){
if(result.empty()){
for(int i = 0; i < set.size(); i++){
vector<char> re = vector<char>();
re.push_back(set[i]);
result.push_back(re);
}
}
else{
int size = result.size();
expand(result, set.size() - 1);
for(int i = 0; i < set.size(); i++)
for(int j = 0; j < size; j++)
result[i * size + j].push_back(set[i]);
}
}
void multiply(vector<vector<char> > charset, vector<vector<char> >& result){
if(charset.empty())
return;
for (int i = 0; i < charset.size(); i++)
multiply(charset[i], result);
}
int main(){
vector<vector<char> > charset = vector<vector<char> >();
vector<char> set1 = vector<char>();
set1.push_back('a');
set1.push_back('b');
vector<char> set2 = vector<char>();
set2.push_back('c');
set2.push_back('d');
vector<char> set3 = vector<char>();
set3.push_back('e');
set3.push_back('f');
charset.push_back(set1);
charset.push_back(set2);
charset.push_back(set3);
vector<vector<char> > result = vector<vector<char> >();
multiply(charset, result);
display(result);
return 0;
}
#include <vector>
#include <iostream>
using namespace std;
void display(vector<vector<char> > result){
cout << "{ ";
for(int i = 0; i < result.size(); i++){
cout << "{ ";
for(int j = 0; j < result[i].size(); j++)
(j != result[i].size() - 1) ? cout << result[i][j] << ", " : cout << result[i][j] << " }";
(i != result.size() - 1) ? cout << ", " : cout << " ";
}
cout << "}\n";
}
void expand(vector<vector<char> >& original, int ext){
if(ext == 0)
return;
int size = original.size();
for(int j = 0; j < ext; j ++)
for (int i = 0; i < size; i++)
original.push_back(original[i]);
}
void multiply(vector<char> set, vector<vector<char> >& result){
if(result.empty()){
for(int i = 0; i < set.size(); i++){
vector<char> re = vector<char>();
re.push_back(set[i]);
result.push_back(re);
}
}
else{
int size = result.size();
expand(result, set.size() - 1);
for(int i = 0; i < set.size(); i++)
for(int j = 0; j < size; j++)
result[i * size + j].push_back(set[i]);
}
}
void multiply(vector<vector<char> > charset, vector<vector<char> >& result){
if(charset.empty())
return;
for (int i = 0; i < charset.size(); i++)
multiply(charset[i], result);
}
int main(){
vector<vector<char> > charset = vector<vector<char> >();
vector<char> set1 = vector<char>();
set1.push_back('a');
set1.push_back('b');
vector<char> set2 = vector<char>();
set2.push_back('c');
set2.push_back('d');
vector<char> set3 = vector<char>();
set3.push_back('e');
set3.push_back('f');
charset.push_back(set1);
charset.push_back(set2);
charset.push_back(set3);
vector<vector<char> > result = vector<vector<char> >();
multiply(charset, result);
display(result);
return 0;
}
I assume that
if multiplying {{a,b}, {c,d}} = {{a,c}, {a,d}, {b,c}, {b,d}}
then, multiplying {{a,b}, {c,d}, {e,f}} = multiplying {{a,c}, {a,d}, {b,c}, {b,d}} by {e,f} = {a,e}, {a,f}, {c,e}, {c,f}, {a,e}, {a,f}, {d,e}, {d,f}, {b,e}, {b,f}, {c,e}, {c,f}, {b,e}, {b,f}, {d,e}, {d,f}
void Multiply(vector<vector<char>> const &a, vector<vector<char>> &out, char c1 = 0, int idx = 0)
{
if (idx < 0 ||
idx >= a.size() ||
(c1 == 0 && idx != 0))
{
return;
}
for (char c2 : a[idx]) {
if (c1 != 0 &&
idx == a.size() - 1)
{
out.push_back({c1, c2});
}
Multiply(a, out, c1, idx + 1);
Multiply(a, out, c2, idx + 1);
}
}
#include<stdio.h>
void main()
{
int i,j,m,n,k,l;
printf("enter the no of subarray do you want\n\n");
scanf("%d",&m);
printf("enter the elements do you want to insert in every subset\n");
scanf("%d",&n);
char first[m][n];
for(i=0;i<m;i++)
{
printf("start entering elements in the sub array %d:",i+1);
for(j=0;j<n;j++)
{
scanf("%s",&first[i][j]);
}
}
printf("\n");
for(i=0;i<m;i++)
{
printf("\nentered elements in the sub array %d:",i+1);
printf("{");
for(j=0;j<n;j++)
{
printf("%c",first[i][j]);
if(j<n-1)
printf(",");
}
printf("}");
}
printf("\n\n");
for(i=0;i<1;i++)
{
printf("{");
for(j=0;j<n;j++)
{
for(k=i+1;k<m;k++)
{
for(l=0;l<n;l++)
{
printf("{%c,%c}",first[i][j],first[k][l]);
}
}
}
printf("}");
}
}
#include<stdio.h>
void main()
{
int i,j,m,n,k,l;
printf("enter the no of subarray do you want\n\n");
scanf("%d",&m);
printf("enter the elements do you want to insert in every subset\n");
scanf("%d",&n);
char first[m][n];
for(i=0;i<m;i++)
{
printf("start entering elements in the sub array %d:",i+1);
for(j=0;j<n;j++)
{
scanf("%s",&first[i][j]);
}
}
printf("\n");
for(i=0;i<m;i++)
{
printf("\nentered elements in the sub array %d:",i+1);
printf("{");
for(j=0;j<n;j++)
{
printf("%c",first[i][j]);
if(j<n-1)
printf(",");
}
printf("}");
}
printf("\n\n");
for(i=0;i<1;i++)
{
printf("{");
for(j=0;j<n;j++)
{
for(k=i+1;k<m;k++)
{
for(l=0;l<n;l++)
{
printf("{%c,%c}",first[i][j],first[k][l]);
}
}
}
printf("}");
}
}
#include<stdio.h>
void main()
{
int i,j,m,n,k,l;
printf("enter the no of subarray do you want\n\n");
scanf("%d",&m);
printf("enter the elements do you want to insert in every subset\n");
scanf("%d",&n);
char first[m][n];
for(i=0;i<m;i++)
{
printf("start entering elements in the sub array %d:",i+1);
for(j=0;j<n;j++)
{
scanf("%s",&first[i][j]);
}
}
printf("\n");
for(i=0;i<m;i++)
{
printf("\nentered elements in the sub array %d:",i+1);
printf("{");
for(j=0;j<n;j++)
{
printf("%c",first[i][j]);
if(j<n-1)
printf(",");
}
printf("}");
}
printf("\n\n");
for(i=0;i<1;i++)
{
printf("{");
for(j=0;j<n;j++)
{
for(k=i+1;k<m;k++)
{
for(l=0;l<n;l++)
{
printf("{%c,%c}",first[i][j],first[k][l]);
}
}
}
printf("}");
}
}
public static print(char[][] arr) {
int k =0;
char[][] result = new char[2^input.length][2];
for(int i=0;i<arr.length;i++) {
char f = arr[i][0];
char s = arr[i][1];
for(int j = i+1; j< arr.length;j++) {
char nf = arr[j][0];
char ns = arr[j][1];
result[k] = new char[]{f, nf};
result[k+1] = new char[]{f, ns};
result[k+2] = new char[]{s, nf};
result[k+3] = new char[]{s, ns};
k+=4
}
}
}
public static void print(char[][] arr) {
int k =0;
char[][] result = new char[2^input.length][2];
for(int i=0;i<arr.length;i++) {
char f = arr[i][0];
char s = arr[i][1];
for(int j = i+1; j< arr.length;j++) {
char nf = arr[j][0];
char ns = arr[j][1];
result[k] = new char[]{f, nf};
result[k+1] = new char[]{f, ns};
result[k+2] = new char[]{s, nf};
result[k+3] = new char[]{s, ns};
k+=4
}
}
}
just do the symbolic multiplication by following the recursion
the code
- Chris September 13, 2017