## Amazon Interview Question for SDE-2s

• 0

Country: India

Comment hidden because of low score. Click to expand.
1
of 1 vote

just do the symbolic multiplication by following the recursion

``````rec(res, i) = [
rec(res + {a}, i-1) for all a in arr2d[i] 	if i >= 0
res 								if i < 0
]
result = {rec({}, len(arr2d))}``````

the code

``````#include <vector>
#include <iostream>

using namespace std;

void symbolicMulRec(const vector<vector<char>>& input, vector<char>& current, size_t& resCtr)
{
if (current.size() == input.size()) { // base case
if (current.size() == 0) return; // empty reesult, input.size() == 0
cout << (resCtr++ == 0 ? "{" : ",{") << current[0];
for (size_t i = 1; i < current.size(); ++i) {
cout << "," << current[i];
}
cout << "}";
} else {
current.push_back(' ');
for (char c : input[current.size() - 1]) {
current.back() = c;
symbolicMulRec(input, current, resCtr);
}
current.pop_back();
}
}

void symbolicMul(const vector<vector<char>>& input)
{
cout << "{";
vector<char> current;
size_t resCtr = 0;
symbolicMulRec(input, current, resCtr);
cout << "}" << endl;
}

int main()
{
symbolicMul({});
symbolicMul({ {}, {} });
symbolicMul({ { 'a', 'b'}, {'c', 'd'} });
symbolicMul({ { 'a', 'b' },{ 'c', 'd' }, {'e', 'f'} });
/* output
{}
{}
{{a,c},{a,d},{b,c},{b,d}}
{{a,c,e},{a,c,f},{a,d,e},{a,d,f},{b,c,e},{b,c,f},{b,d,e},{b,d,f}}
*/
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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++) {
}
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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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"]
})``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) );
});``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/* 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 // 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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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("}");
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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("}");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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("}");
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.