Amazon Interview Question for SDE-2s


Country: United States
Interview Type: Phone Interview




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

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

/* find the next enumeration */
bool hasNext(vector<int>& limits, vector<int>& perm)
{
    const int N = limits.size();

    for (int i = 0; i < N; i++) {
        perm[i]++;
        if (perm[i] < limits[i])
            return true;
        for (int j = 0; j <= i; j++)
            perm[j] = 0;
    }

    return false;
}

int main()
{
    vector<vector<string>> map = {  // things to enumerate
        { "Checks", "Lines" },
        { "XL", "X", "M", "S" },
        { "Red", "Blue", "Green"}};

    const int N = map.size();
    vector<int> perm(N, 0);
    vector<int> limits(N);

    for(int i = 0; i < N; i++)
        limits[i] = map[i].size();

    do {
        for (int i = N - 1; i >= 0; i--)
            cout << map[i][perm[i]] << "\t";
        cout << endl;
    } while (hasNext(limits, perm));
    return 0;
}

/* output:
Red     XL      Checks
Red     XL      Lines
Red     X       Checks
Red     X       Lines
Red     M       Checks
Red     M       Lines
Red     S       Checks
Red     S       Lines
Blue    XL      Checks
Blue    XL      Lines
Blue    X       Checks
Blue    X       Lines
Blue    M       Checks
Blue    M       Lines
Blue    S       Checks
Blue    S       Lines
Green   XL      Checks
Green   XL      Lines
Green   X       Checks
Green   X       Lines
Green   M       Checks
Green   M       Lines
Green   S       Checks
Green   S       Lines
*/

- Westlake March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- uuuouou March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Thirumaleshwar Kunamalla March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ganesh Ram Sundaram March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I believe the challenge here is we do not know how many levels deep (ie we don't know the number of attributes) and therefore can't, at compile time, know how many for loops we need

- Anonymous April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Balaji March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Balaji March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Suman March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- GK March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- sathiyamoorthy.subramaniam March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?

- vin March 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

edit :

class Color implements attributes{
	String value;
	Color(String value){
		this.value = value;
	}
	
	void printValue(){
		System.out.print(this.value);
	}
}

- vin March 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- dungbx March 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- AnonyJava April 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- There's a neater way with recursion (c# impl below) April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- There's a neater way with recursion (c# impl below) April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]++;
						}
					}
				}
			}
		}
	}

- Ding November 19, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More