Amazon Interview Question Testing / Quality Assurances
Country: India
Interview Type: In-Person
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.TreeSet;
public class Comb {
TreeSet hs = new TreeSet();
public TreeSet permutation(String prefix, String str) {
int n = str.length();
if (n == 0)
{
hs.add(prefix);
//System.out.println(prefix);
}
else
{
hs.add(prefix);
//System.out.println(prefix);
}
for(int i = 0;i < n;i++)
permutation(prefix+str.charAt(i), str.substring(0, i)+str.substring(i+1, n));
return hs;
}
void print (TreeSet hs)
{
Iterator itr = hs.iterator();
while(itr.hasNext())
{
String str = (String)itr.next();
System.out.println(str);
}
}
public static void main(String[] args) {
Comb b = new Comb();
String ss = "abc";
TreeSet hss = b.permutation("", ss);
System.out.println("Printing in acsending order....................");
b.print(hss);
int i;
ArrayList al = new ArrayList();
for (i = 1;i<=ss.length() ; i++)
{
Iterator itr = hss.iterator();
while(itr.hasNext())
{
String str = (String)itr.next();
if(str.length()==i)
{
al.add(str);
}
}
}
System.out.println("Printing in acsending order and ascending length....................");
for (i=0;i<al.size(); i++)
{
System.out.println((String)al.get(i));
}
}
}
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}
So basically what its asking is
all the subsets of the given string set.
That would include any anagrams as well as combinations of any number of characters in the string.
List<string> GetAllCombinations ( string s )
{
List<string> allSubsets;
if(s.Length == 0 || s == Null)
{
allSubsets = new List<string> ();
alSubsets.add(new string(""));
}
else
{
// Get first character.
char first = s[0];
// Get all subsets of the remaining string.
allSubsets = GetCombinations( s.Substring(1) );
List<string> moreSubsets = new List<string> ();
foreach( string t in allSubsets)
{
for(int i = 0; i < t.Length; i++)
{
// Insert the first character in every position of t
t.InsertCharAt( first, i );
moreSubsets.Add(t);
}
}
// Add all the strings in moreSubsets to the original list.
allSubsets.AddAll(moreSubsets);
}
return allSubsets;
}
I haven't have the code yet but you can try it out by having a same binary digits set
which means
hello have five letters so the comparative hash will be in binary of five digits so the total combination will be 2^5 =32 ; now HELLO means = all binary on set (11111); you can take this example to build a valid algorithm
Here you go
void printanagram (char *s){
int count;
int len;
len = strlen(s);
//Run loop via all possible combinations 0,2^len
for(count=0;count <= pow(2,len);count++){
int i,j;
for(i=1,j=0;i<=count;j++,i<<=1){
//Check if current count & with iterator is nonzero.
// or simply check if that bit is set to one
if(count&i)
printf("%c",s[j]);
}
printf("\n");
}
}
import java.util.HashSet;
import java.util.*;
class Anagram1{
private static String inputStr;
private static Set<String> set=new HashSet<>();
public static void permute(String arg){
inputStr = new String(arg);
System.out.println("inputStr = " + inputStr + " len:" + inputStr.length());
permute("", 0, new boolean[inputStr.length()]);
for(String x:set){
System.out.println(x);
}
}
private static void permute(String str, int index, boolean[] used){
if(index == inputStr.length()){
set.add(str);
return;
}
else{
for(int n = 0; n < inputStr.length(); n++){
if(used[n]){
continue;
}
used[n] = true;
set.add(str);
permute(str + inputStr.charAt(n), index+1, used);
used[n] = false;
}
}
}
}
public class StringPermutations { public static void main(String args[]) { permutation("hello"); } /* * A method exposed to client to calculate permutation of String in Java. */ public static void permutation(String input){ permutation("", input); } /* * Recursive method which actually prints all permutations * of given String, but since we are passing an empty String * as current permutation to start with, * I have made this method private and didn't exposed it to client. */ private static void permutation(String perm, String word) { if (word.isEmpty()) { System.err.println(perm + word); } else { for (int i = 0; i < word.length(); i++) { permutation(perm + word.charAt(i), word.substring(0, i) + word.substring(i + 1, word.length())); } } } }
import java.util.ArrayList;
public class annagrome {
public static void main(String[] args){
String arun="hello";
ArrayList<String> ang=new ArrayList<String>();
char[] ar=arun.toCharArray();
for(int i=0;i<ar.length;i++)
{
String ss=""+ar[i];
System.out.println("===="+ss);
for(int j=0;j<ar.length;j++)
{
if(i!=j)
{
ss=ss+ar[j];
ang.add(ss);
}
}
}
System.out.println(ang);
}
}
import java.util.ArrayList;
public class annagrome {
public static void main(String[] args){
String arun="hello";
ArrayList<String> ang=new ArrayList<String>();
char[] ar=arun.toCharArray();
for(int i=0;i<ar.length;i++)
{
String ss=""+ar[i];
System.out.println("===="+ss);
for(int j=0;j<ar.length;j++)
{
if(i!=j)
{
ss=ss+ar[j];
ang.add(ss);
}
}}
System.out.println(ang);
}
}
C#
static bool isAnagramm(string pattern, string input)
{
var a1 = pattern.ToArray();
var a2 = input.ToArray();
Array.Sort(a1);
Array.Sort(a2);
return new string(a1) == new string(a2);
}
Here is the python version for it
import itertools def permutation(word): for i in range(len(word)+1): perms = list(itertools.permutations(word,i)) #perms = list(itertools.combinations(word,i)) for i in perms: print ''.join(i)If combination is needed use the commented out line.
- Naveen April 14, 2014