Amazon Interview Question Senior Software Development Engineers
Country: United States
Interview Type: Phone Interview
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++;
}
}
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
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++, 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";
}
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++;
}
}
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();
}
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;
}
}
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()
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);
}
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;
}
}
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);
}
}
}
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:
- echang October 06, 2016A
B
C
D
AB
AC
AD
BC
BD
CD
ABC
ABD
ACD
BCD
ABCD