Amazon Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: Phone Interview




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

Iterative solution

public static void allPossibleCombinations(String s) {
		int mask = 1;
		int length = s.length();
		while (mask < 1<<length) {
			String interm =  "";
			for (int i = 0; i < length; i++) {
				if (((mask >> i) & 1) != 0) {
					interm += s.charAt(i);
				}
			}
			System.out.println(interm);
			mask++;
		}
	}

- Anonymous October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if input string has length more than 32?

- Iuri Sitinschi October 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Iuri Sitinschi: then probably all other solutions based on recursion or non-constant space will error out with out of memory much earlier than this one ;)

there are 32! combinations to print

- pavel.em November 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

a
b
c
d
ab
ac
ad
bc
bd
cd
abc
abd
acd
bcd
abcd

- Tim October 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given array T (for example [a,b,c,d], the solution is a recursive function foo(T) :

- if length(T) is 2 elements a and b, then return [a, b, ab]
- else return
T[1], foo(T[2..n]), T[1] + foo( T[2..n] )

T[1] - is the first element in the list
T[2..n] - all elements except the first one
foo(T[2..n]) - all combinations of element 2 .. n
T[1] + foo( T[2..n] ) - concatenate first element with all combinations of 2..n elements

- slava.k October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple recursion

class Program
	{
		static void Main( string[] args )
		{
			string s = Console.ReadLine();
			string o = null;
			recurse( s, o, 0 );
		}

		private static void recurse( string s, string o, int start )
		{
			for ( int i = start; i < s.Length; i++ )
			{
				o = o + s[i];
				Console.WriteLine( o );
				recurse( s, o, i + 1 );
				o = o.Remove( o.Length - 1 );
			}
		}
	}

- c.prashanth85 October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It prints duplicate results

- Bahram November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

c++, implementation

void printCombination(vector<char> arr) {
	queue< pair<string, int> > q;
	string str;
	int i;

	str = "";
	for (i = 0; i < arr.size(); i++) {
		q.push(make_pair(str + arr[i], i));
	}

	while (q.size()) {
		str = q.front().first;
		i = q.front().second + 1;
		q.pop();
		for (; i < arr.size(); i++) {
			q.push(make_pair(str + arr[i], i));
		}
		cout << str;
		if (q.size()) cout << ",";
	}
	cout << "\n";
}

- kyduke October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

This is a dp problem. Similar to the one given in CTCI dynamic programming.
n = # of elements.
Find n=1: {}, A
n = 2: {}, A, B, AB
n = 3: {}, A,B,AB, C, AC, BC, ABC

So for n = 3. (copy elements from n =2) + (copy and add C to it) so on for n = 4.. etc

- justaguy October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iterative solution

public static void allPossibleCombinations(String s) {
		int mask = 1;
		int length = s.length();
		while (mask < 1<<length) {
			String interm =  "";
			for (int i = 0; i < length; i++) {
				if (((mask >> i) & 1) != 0) {
					interm += s.charAt(i);
				}
			}
			System.out.println(interm);
			mask++;
		}
	}

- John October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if input string has length more than 32?

- Iuri Sitinschi October 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Non Recursive
C#

public static void WriteCombinationsNonRec(char[] arr)
{
	if (arr == null) return;
	List<String> combinations = new List<String>();
			
	for (int i = 0; i < arr.Count(); i++ )
	{
		String current = arr[i].ToString();

		for (int j = combinations.Count() - 1; j >= 0; j--)
		{
			combinations.Add(combinations[j] + current);
		}
		combinations.Add(current);
	}

	PrintStrings(combinations);
}
private static void PrintStrings(List<String> combinations)
{
	foreach (String s in combinations)
	{
		Console.Write("{0},", s);
	}
	Console.WriteLine();
}

- IC October 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we need ALL possible combinations, e.g. 'AB' and 'BA' are two different combinations

public class StringCombinations {

    public List<String> getCombinations(char[] input) {
        if (input == null) return Collections.emptyList();

        return getCombinations(new String(input));
    }

    private List<String> getCombinations(String input) {
        if (input.length() == 1) return Collections.singletonList(input);

        List<String> permutations = new ArrayList<>();
        String letter = String.valueOf(input.charAt(0));
        String remainder = input.substring(1);

        List<String> words = getCombinations(remainder);

        for (String word : words) {
            for (int i = 0; i <= word.length(); i ++) {
                permutations.add(insertLetterAt(word, letter, i));
            }
        }

        permutations.add(letter);
        permutations.addAll(words);
        return permutations;
    }

    private String insertLetterAt(String word, String letter, int index) {
        String prefix = word.substring(0, index);
        String postfix = word.substring(index);
        return prefix + letter + postfix;
    }
}

- zaitcev.anton October 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Anton. Combination is when order is not important. So, 'AB' and 'BA' is the same combination.

- Iuri Sitinschi October 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is better to call it subsets, because actually combination it is when we choose k something out of n ("C" in combinatorics).

- Iuri Sitinschi October 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def combigen(string):
    """Return a list of all possible combinations of characters in a given
    string.

    >>> combigen('')
    []
    >>> combigen('A')
    ['A']
    >>> combigen('AB')
    ['A', 'B', 'AB']
    >>> combigen('ABC')
    ['A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']
    """
    if not string:
        return []
    if len(string) == 1:
        return [string]

    cs = []  # combinations
    char1 = string[0]
    cs.append(char1)
    sub_cs = combigen(string[1:])
    for c in sub_cs:
        cs.append(c)
        cs.append(char1 + c)
    return cs


if __name__ == '__main__':
    import doctest
    doctest.testmod()

- constt October 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printAllSets(char[] c) {
		List<String> list = new ArrayList<String>();
		list.add("");
		printSets(c, 0, list);
	}
	
	private static void printSets(char[] c, int index, List<String> list) {
		if(index==c.length) return;
		int len = list.size();
		for(int i=0; i<len; i++) {
			System.out.println(list.get(i) + c[index]);
			list.add(list.get(i) + c[index]);
		}
		index++;
		printSets(c, index, list);
	}

- Shivam Maharshi October 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If I understand correctly, the runtime is 2^n for each of these solution.
Please correct me, if I misunderstood.

- varun anand October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the question of generating the power set. The sub-problem can be easily worked out. For the C++ code and sub-problem description, refer to: cpluspluslearning-petert.blogspot.co.uk/2014/04/dynamic-programming-generate-power-set.html

- peter tang October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A C++ solution, it does not work with char arrays with more than 64 elements:

void allCombinations(const std::vector<char>& iChVect)
{
    if (iChVect.size() > sizeof(uint64_t))
        return;
    
    for (int i = 0; i <= std::pow(2, iChVect.size()); ++i)
    {
        for (int j = 0; j < sizeof(uint64_t); ++j)
        {
            if ((static_cast<uint64_t>(std::pow(2, j)) & i) != 0)
            {
                std::cout << iChVect[j];
            }
        }
        std::cout << std::endl;
    }

}

- Anonymous February 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My c++ solution without recursion:

#include <vector>
#include <iostream>
#include <algorithm>

// class generator:
struct c_unique {
  int current;
  c_unique() {current=0;}
  int operator()() {return ++current;}
} UniqueNumber;

int main()
{
	std::vector<char> mychars={'A','B','C','D'};
	int n=mychars.size();

	for(int r=1; r<=n; r++){

		std::vector<int> myints(r);
		std::vector<int>::iterator first = myints.begin(), last = myints.end();

		std::generate(first, last, UniqueNumber);

		std::for_each(first, last, [&mychars] (int n) {std::cout << mychars.at(--n); });
		std::cout << std::endl;

		while((*first) != n-r+1){
			std::vector<int>::iterator mt = last;

			while (*(--mt) == n-(last-mt)+1);
			(*mt)++;
			while (++mt != last) *mt = *(mt-1)+1;

			std::for_each(first, last, [&mychars] (int n) {std::cout << mychars.at(--n); });
			std::cout << std::endl;
		}
	}
}

Here are outputs:
A
B
C
D
AB
AC
AD
BC
BD
CD
ABC
ABD
ACD
BCD
ABCD

- echang October 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package BinarySearch;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class StringSet {

public static void main(String S[])
{
//Map<String,Integer> m=new HashMap<String,Integer>();
List<String> l =new ArrayList<String>();
// String []arr = null;
String temp="";
//String str_arr = (String) new String();
// int x=0;
try
{
FileInputStream file = new FileInputStream("D:\\test.txt");
DataInputStream dis = new DataInputStream(file);
BufferedReader br = new BufferedReader(new InputStreamReader(dis));
// System.out.println(br.readLine());
String Contents="";
String str="";


while ((Contents = br.readLine()) != null) {
str+=Contents;
}
char[]char_array =str.toCharArray();
System.out.println(char_array);
for(int i=0;i<str.length();i++)
{

char ch=str.charAt(i);
if (ch==',')
{
l.add(temp);
temp="";
}
else if (ch=='.')
{
l.add(temp);
temp="";
}
else
{
temp=temp+ch;
}


}
System.out.println(l);
new File("D:/Java").mkdir();
File statText = new File("D:/Java/SubString.txt");
FileOutputStream is = new FileOutputStream(statText);
OutputStreamWriter osw = new OutputStreamWriter(is);
Writer w = new BufferedWriter(osw);

Set<String> ldup =new HashSet<String>();
// List<String> ldu =new ArrayList<String>();
int on=0,in=0;
for(on=0;on<l.size();on++)
{
String k="",q="",r="",t="" ,s="";

for(in=on;in<l.size();in++)
{
q="";
int ka=l.size();
if(in<ka-1)
{
t=l.get(in+1);
s=l.get(on);
q=s+","+t;
//System.out.println("m:"+q);
ldup.add(q);
}
k=l.get(in);
if(r=="")
{
r=r+k;
}else{
r=r+","+k;
}
ldup.add(r);

}
}

System.out.println(ldup);
Iterator i=ldup.iterator();
while(i.hasNext())
{
String str1=(String) i.next();
w.write("{"+str1+"}");
w.append(System.lineSeparator());
}
w.close();
// System.out.println(ldup);

}
catch(Exception e)
{
System.out.println(e);
}

}

}

- himanshutime@gmail.com October 12, 2016 | 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