Amazon Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
We fix the problem using DFS. Here's code in C++:
void printAttribute(vector<string>& combination)
{
cout << combination[0];
for(int i = 1; i < combination.size(); ++i){
cout << " - " << combination[i];
}
cout << "\n";
}
void permutate(vector<vector<string> >& attributes, int i, vector<string>& combination)
{
if(i == attributes.size()){
printAttribute(combination);
return;
}
for(int k = 0; k < attributes[i].size(); ++k){
combination[i] = attributes[i][k];
permutate(attributes, i + 1, combination);
}
}
void enumerateAttributeCombinations(vector<vector<string> >& attributes)
{
if(attributes.empty()) return;
vector<string> combination;
combination.resize(attributes.size());
permutate(attributes, 0, combination);
}
Below is the code, I have written , not able to do within time in written test. Hope it will be useful for anyone.
This is an non-recursive logic which will work for large value of N. time Complexity is O(n2).
-------------------------------------------------------------------------------------
package com.test;
import java.util.Scanner;
public class Solution
{
public static void main(String args[] ) throws Exception
{
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine(); //to read new line
String[][] attributes = new String[n][];
int i=0;
while(i < n)
{
String temp = in.nextLine();
String[] values = temp.split(" ");
attributes[i] = values;
i++;
}
printAttributesCombination(attributes);
}
static void printAttributesCombination(String[][] attributes)
{
int count[] = new int[attributes.length];
int totalcount[] = new int[attributes.length];
//initialize the totalcount and temp index count
initialize(count, totalcount, attributes);
while(isDone(count,totalcount))
{
printArray(attributes,count);
}
}
static void initialize(int count[], int totalcount[], String[][] attributes)
{
for(int i = 0; i < count.length; i++)
{
count[i] = 0;
totalcount[i] = attributes[i].length - 1;
}
count[count.length-1] = -1;
}
static boolean isDone(int count[], int totalCount[])
{
boolean prevIndexSet = true;
boolean canTerminateLoop = false;
int i = 0;
for(i = count.length - 1; i >= 0 ; i--)
{
if(count[i] == totalCount[i])
{
count[i] = 0;
prevIndexSet = true;
canTerminateLoop = true;
}
else
{
count[i] = count[i] + 1;
prevIndexSet = false;
canTerminateLoop = false;
}
if(!prevIndexSet)
break;
}
if(canTerminateLoop && i == -1 )
return false;
return true;
}
static void printArray(String[][] arr, int count[])
{
System.out.println();
for(int i = 0; i < arr.length; i++)
{
System.out.print(" " + arr[i][count[i]]);
}
}
}
-------------------------------------------------------------------------------------
Output:
==============
Sample1:-
============
3
a b c
d e f
g h i
a d g
a d h
a d i
a e g
a e h
a e i
a f g
a f h
a f i
b d g
b d h
b d i
b e g
b e h
b e i
b f g
b f h
b f i
c d g
c d h
c d i
c e g
c e h
c e i
c f g
c f h
c f i
Sample2:-
============
4
a b
a b c
d e
f i
a a d f
a a d i
a a e f
a a e i
a b d f
a b d i
a b e f
a b e i
a c d f
a c d i
a c e f
a c e i
b a d f
b a d i
b a e f
b a e i
b b d f
b b d i
b b e f
b b e i
b c d f
b c d i
b c e f
b c e i
call the method as attrib(lol); //lol = list of lists
void attrib(list<list<string> > &lol, list<string> &outlst = *(new list<string>)) {
int n = outlst.size();
if (n == lol.size()) {//outlst has attribute from last list
for(list<string>::iterator itr=outlst.begin();itr!=outlst.end();itr++) {
cout<<(*itr)<<'\t';
}
cout<<endl;
return;
}
list<list<string> >::iterator lolItr = lol.begin();
if (n) advance(lolItr,n);
list<string> currlst = *lolItr;
//Iterate over elements of n-th list.
for(list<string>::iterator itr=currlst.begin();itr!=currlst.end();itr++) {
outlst.push_back(*itr);
attrib(lol,outlst);
outlst.pop_back();
}
}
As simple as this, hope code is self explanatory:
void printCombinations(String[] colors,String[] sizes, String[] patterns){
for(i=0; i<colors.length(); i++){
for(j=0; j<sizes.length(); j++){
for(k=0; k<patterns.length(); k++){
System.out.println(colors[i]+"-"+sizes[j]+"-"+patterns[k]);
}
}
}
}
Here is recursive way of doing, since we are printing all n^m ( i.e pow(n,m)) combinations, I think complexity cannot be less O(n^m), is there a way less than O(n^m),
Any thoughts?
{{
//call print as
print(attr,0,"");
//the print
print(String[][] attr, int row, String line){
//last row of attributes
if(row == attr.length -1){
for( int i = 0; i < attr[row].length; i++){
System.out.println(line+"-"+attr[row][i]);
}
}else{
for( int e = 0; e < attr[row].length; e++){
//recurse for next row attributes
print(attr,++row,line+"-"+attr[row][e]);
}
}
}
}}
Here is recursive way of doing, since we are printing all n^m ( i.e pow(n,m)) combinations, I think complexity cannot be less O(n^m), is there a way less than O(n^m),
Any thoughts?
//call print as
print(attr,0,"");
//the print
print(String[][] attr, int row, String line){
//last row of attributes
if(row == attr.length -1){
for( int i = 0; i < attr[row].length; i++){
System.out.println(line+"-"+attr[row][i]);
}
}else{
for( int e = 0; e < attr[row].length; e++){
//recurse for next row attributes
print(attr,++row,line+"-"+attr[row][e]);
}
}
}
import java.util.ArrayList;
import java.util.List;
public class ProductCombinationInAmazon {
public void print(List<List<String>> catalog)
{
List<String> list = catalog.get(0);
for(int i =1 ; i < catalog.size() ; i++)
{
List<String> list1 = catalog.get(i);
List<String> merged = new ArrayList<String>();
for(String str1 : list)
{
for(String str2 : list1)
{
merged.add(str1+" "+str2);
}
}
list = merged;
}
for(String str : list)
{
System.out.println(str);
}
}
/**
* @param args
*/
public static void main(String[] args)
{
List<String> list1 = new ArrayList<String>();
list1.add("Red");
list1.add("Blue");
list1.add("Green");
List<String> list2 = new ArrayList<String>();
list2.add("XL");
list2.add("X");
list2.add("M");
list2.add("S");
List<String> list3 = new ArrayList<String>();
list3.add("Check");
list3.add("Lines");
List<List<String>> list4 = new ArrayList<List<String>>();
list4.add(list1);
list4.add(list2);
list4.add(list3);
new ProductCombinationInAmazon().print(list4);
}
}
static void Main(string[] args)
{
string[][] arr = { new[] { "red", "blue", "green" }, new[] { "XL", "X", "M", "S" }, new[] { "checks", "lines"} };
var res = new string[arr.Length];
PerformPrinting(arr , 0 , res);
}
private static void PerformPrinting(string[][] arr, int i, string[] res)
{
if (i == arr.Length)
Print(res);
else
{
for (int j = 0; j < arr[i].Length; j++)
{
res[i] = arr[i][j];
PerformPrinting(arr, i + 1, res);
}
}
}
static void Print(string[] res)
{
Console.WriteLine(String.Join("-" , res));
}
cloths = {
'colors':['red','blue','green','white','yellow'],
'size' :['s','m','xl','xxl'],
'pattern' :['checks','lines'],
'models' :['tshirt','shirt']
}
def combin(keys):
#print (keys)
if len(keys) == 1:
return cloths[keys[0]]
if keys:
key = keys[0]
r = combin(keys[1:])
rt = []
for ii in cloths[key]:
for jj in r:
rt.append(ii+'-'+jj)
return rt
if __name__ == '__main__':
k = list(cloths.keys())
k = sorted(k)
#print (sorted(k))
rt = combin(k)
pprint.pprint (rt)
I think this question is more about the OO Design.
As you would see something common in all of these are that these are attributes and they all have the same property ... they print their values.
so, if we have common interface say attributes:
interface attributes {
void printValue();
}
now each attribute that needs to be used is can actually inherit from the attribute interface and then define their own printValue() method.
so for example:
class Color implements attributes{
String value;
Color(String value){
this.value = value;
}
}
Now for any product, say a shirt
class Shirt {
ArrayList<attributes> listOfAttributes;
Shirt(){
listOfAttributes = new ArrayList<attributes>();
}
void addAttributes(attributes x){
this.listOfAttributes.add(x);
}
void printAttributes(){
for(attributes x : this.listOfAttributes()){
x.printValue();
}
}
What do you guys think ?
My non-recursive implementation in Javascript.
var ar = [['a', 'b', 'c'], [1, 2, 3], ['x', 'y', 'z']];
var coor = [];
// Print out with current coordinate
var printOut = function() {
for (var i = 0; i < coor.length; i++) {
process.stdout.write(ar[i][coor[i]] + ' ');
}
process.stdout.write('\n');
};
// Initialize coorrdinate array
for (var i = 0; i < ar.length; i++) coor.push(0);
// Print the first result
printOut();
for (var i = coor.length - 1; i >= 0; i--) {
if (coor[i] < ar[i].length-1) {
coor[i] += 1;
i += 1;
for (var j = i; j < coor.length; j++) {
coor[j] = 0;
i = j + 1;
}
printOut();
}
}
public class PrintAllPermutationsOfSomething {
public static void main(String[] args) {
String[][] posibilities = new String[][] {
{"R", "G", "B"},
{"M", "XL" , "L"},
{"Checks" , "Stripes"},
//{"store1", "store2"}
};
int allSize = 1;
for(int i=0; i < posibilities.length; i++) {
allSize = allSize * posibilities[i].length;
}
StringBuilder[] result = new StringBuilder[allSize];
int repeat = 1;
for(int i=0; i < posibilities.length; i++) {
repeat = repeat * posibilities[i].length;
int p =0;
while (p < allSize) {
for(int k=0;k < posibilities[i].length; k++) {
int t =0;
for(int j=0 ; j < allSize/repeat; j++ ) {
if(result[p] == null) {
result[p] = new StringBuilder();
}
//k = k %posibilities[i].length;
result[p].append("\t").append(posibilities[i][k]);
p ++;
//k = k + 1;
}
}
}
}
int ctr = 0;
for(int i=0; i < result.length; i++)
System.out.println(++ctr + "\t" +result[i].toString());
System.out.println("\n" + allSize);
}
}
/** Output
* 1 R M Checks
2 R M Stripes
3 R XL Checks
4 R XL Stripes
5 R L Checks
6 R L Stripes
7 G M Checks
8 G M Stripes
9 G XL Checks
10 G XL Stripes
11 G L Checks
12 G L Stripes
13 B M Checks
14 B M Stripes
15 B XL Checks
16 B XL Stripes
17 B L Checks
18 B L Stripes
18
*/
class Program
{
public static void Main(string[] args)
{
var classifications
= new List<List<String>>{
new List<String> {"1","2","3","4"},
new List<String> {"1","2","3"},
new List<String> {"1","2","3"}
};
IList<String> combinations = getPermutations(classifications);
foreach (var element in combinations)
{
Console.WriteLine(element.ToString());
}
Console.Write("Press any key to continue . . . ");
Console.ReadKey(true);
}
public static IList<String> getPermutations(List<List<String>> classifications)
{
if(classifications ==null || classifications.Count == 0)
return null;
if(classifications.Count == 1)
return classifications[0];
var broaderClassification = classifications[0];
var finerClassifications = classifications.Skip(1).Take(classifications.Count-1).ToList();
return getPermutations(broaderClassification, finerClassifications);
}
private static IList<String> getPermutations (IList<String> broaderClassification, List<List<String>> finerClassifications)
{
if(finerClassifications.Count==1)
{
return combine(broaderClassification, finerClassifications[0]);
}
else
{
return combine(broaderClassification,
getPermutations(finerClassifications[0], finerClassifications.Skip(1).Take(finerClassifications.Count-1).ToList()));
}
}
private static IList<String> combine(IList<String> list1, IList<String> list2)
{
IList<String> result = new List<String> (list1.Count * list2.Count);
foreach(var item1 in list1)
foreach(var item2 in list2)
result.Add(item1 + " " + item2);
return result;
}
}
class Program
{
public static void Main(string[] args)
{
var classifications
= new List<List<String>>{
new List<String> {"1","2","3","4"},
new List<String> {"1","2","3"},
new List<String> {"1","2","3"}
};
IList<String> combinations = getPermutations(classifications);
foreach (var element in combinations)
{
Console.WriteLine(element.ToString());
}
Console.Write("Press any key to continue . . . ");
Console.ReadKey(true);
}
public static IList<String> getPermutations(List<List<String>> classifications)
{
if(classifications ==null || classifications.Count == 0)
return null;
if(classifications.Count == 1)
return classifications[0];
var broaderClassification = classifications[0];
var finerClassifications = classifications.Skip(1).Take(classifications.Count-1).ToList();
return getPermutations(broaderClassification, finerClassifications);
}
private static IList<String> getPermutations (IList<String> broaderClassification, List<List<String>> finerClassifications)
{
if(finerClassifications.Count==1)
{
return combine(broaderClassification, finerClassifications[0]);
}
else
{
return combine(broaderClassification,
getPermutations(finerClassifications[0], finerClassifications.Skip(1).Take(finerClassifications.Count-1).ToList()));
}
}
private static IList<String> combine(IList<String> list1, IList<String> list2)
{
IList<String> result = new List<String> (list1.Count * list2.Count);
foreach(var item1 in list1)
foreach(var item2 in list2)
result.Add(item1 + " " + item2);
return result;
}
}
Iterative
void calculateChoicesIterative(String[][] spec){
int[] indecies = new int[spec.length];
while(indecies[0] < spec[0].length){
for(int i=0;i<spec[spec.length-1].length;i++){
StringBuilder entry = new StringBuilder();
for(int j=0;j<indecies.length-1;j++){
entry.append(spec[j][indecies[j]]);
}
entry.append(spec[spec.length-1][i]);
System.out.println(entry);
}
boolean reset = true;
for(int j=indecies.length-2;j>=0;j--){
if(reset){
reset=false;
if(indecies[j] < spec[j].length-1){
indecies[j]++;
}else{
if(j > 0){
reset = true;
indecies[j]=0;
}else{
indecies[j]++;
}
}
}
}
}
}
- Westlake March 08, 2014