## Amazon Interview Question for Senior Software Development Engineers

• 1
of 1 vote

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 length = s.length();
String interm =  "";
for (int i = 0; i < length; i++) {
if (((mask >> i) & 1) != 0) {
interm += s.charAt(i);
}
}
System.out.println(interm);
}
}``````

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

What if input string has length more than 32?

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

@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

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

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

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

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

Simple recursion

``````class Program
{
static void Main( string[] args )
{
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 );
}
}
}``````

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

It prints duplicate results

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

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

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

Iterative solution

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

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

What if input string has length more than 32?

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

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

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

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

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

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

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).

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()``````

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>();
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]);
}
index++;
printSets(c, index, list);
}``````

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.

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

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

}``````

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
BC
BD
CD
ABC
ABD
ACD
BCD
ABCD

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

package BinarySearch;

import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
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);
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==',')
{
temp="";
}
else if (ch=='.')
{
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);
}
k=l.get(in);
if(r=="")
{
r=r+k;
}else{
r=r+","+k;
}

}
}

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

}

}

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.