Amazon Interview Question
Software Development ManagersCountry: India
Interview Type: Written Test
Have thissssssssssssssssssssssss
import java.io.*;
public class StringPermutation {
//----------------------------------------------------------------------------
private static char source[] = {'c', 'a','o', 'n'};
private static char result[] = new char[4];
private static boolean picked[] = new boolean[4];
//----------------------------------------------------------------------------
public static void main(String[] args) {
// initialize that none of characters was picked
java.util.Arrays.fill(picked, false);
pickCharAt(0);
}
//----------------------------------------------------------------------------
private static void pickCharAt(int position) {
// print out if 6 positions already filled
if (position > 3)
System.out.println(String.valueOf(result));
// pick a remain character for current position
else
for (int i=0; i<4; i++) {
// if the character source[i] still not picked then pick it
if (!picked[i]) {
result[position] = source[i];
picked[i] = true;
// fetch for next position
pickCharAt(position + 1);
// return the character source[i] when recur back
picked[i] = false;
}
}
}}
output:
caon
cano
coan
cona
cnao
cnoa
acon
acno
aocn
aonc
anco
anoc
ocan
ocna
oacn
oanc
onca
onac
ncao
ncoa
naco
naoc
noca
noac
import java.util.LinkedHashSet;
import java.util.Set;
public class Permutation {
public static void main(String[] args) {
String a = "abc";
for (String s : all_perm(a)) {
System.out.println(s);
}
}
public static Set<String> concat(String c, Set<String> lst) {
Set<String> ret_set = new LinkedHashSet<String>();
for (String s : lst) {
ret_set.add(s + c);
}
return ret_set;
}
public static Set<String> all_perm(String a) {
Set<String> set = new LinkedHashSet<String>();
if (a.length() == 1) {
set.add(a);
} else {
for (int i = 0; i < a.length(); i++) {
set.addAll(concat(a.charAt(i) + "", all_perm(a.substring(0, i)
+ a.substring(i + 1, a.length()))));
}
}
return set;
}
}
Using 6 for loops to output 6! which is 120 permutations.
void permutation()
{
char input[6] = {'c', 'a', 'b', 'r' ,'o','n'};
char output[6];
for(int i = 0; i < 6; i++)
{
output[0] = input[i];
for(int j = 0; j < 6; j++)
{
if(input [j] != output[0])
{
output[1] = input[j];
}
for(int k = 0; k< 6; k++)
{
..........
printf(output);
}
}
}
}
public static void permute (char[] pString)
{
permute(pString, 0);
}
private static void permute(char[] pString, int startIndex)
{
for( int i = startIndex; i < pString.length; i++)
{
char tmp = pString[startIndex];
pString[startIndex] = pString[i];
pString[i] = tmp;
permute(pString, startIndex+1);
pString[i] = pString[startIndex];
pString[startIndex] = tmp;
}
if( startIndex == pString.length )
System.out.println(pString);
}
O(n!)
It is the permutation of string "cabro". The space complexity O(1). The time complexity is the number of the instances of the permutation, which is O(n!).
- chenlc626 March 24, 2013