Salesforce Interview Question
Country: United States
Interview Type: In-Person
Let's assume the string to be "abcde.....". Now looking at the possibilities (of all possible lengths) :-
a, b, c, d, e, ...... --- single letters
ab, ac, ad,........, ba, bc, bd....., ca, cb,cd,..... --- dual letters
abc, abd, abe,..... acb, acd, ace, .... --- three letters
and so on...
The concept in generating these sequences is that, when you consider all the single letters, store them in a array, [a,b,c,d,....]
while you are forming dual letter sequences, take a letter and pair up with all other letters in the array, ex. if I consider 'a', I take 'a' out of array and form ab, ac, ad....
Similarly, when you are considering 3 letter sequences, take the two letters for consideration and pair up with all others, i.e, while considering "ab", my array under consideration will be [c,d,e,f,....](a, b removed from single letter arrya) and so we get abc, abd, abe.......
similarly repeat the procedure for "ac"(a,c removed from dual letter array) with array [b, d, e, f....] and the rest.
Following this process, you can get a bunch of required sequences and carefully designing algo can lead to a dictionary order by default !!!
That's my guess!! Hopefully correct.
import java.util.ArrayList;
public class Permutation {
public static void main(String args[]){
// ArrayList<Character> set = new ArrayList<Character> ();
// set.add('a');
// set.add('b');
// set.add('c');
// helper(set,"",3);
permutations("abcd");
}
// time: n+n*(n-1)+n*(n-1)*(n-2)+...+n! = O(n!)
public static void permutations(String str) {
ArrayList<Character> set = new ArrayList<Character> ();
for(int i=0;i<str.length();i++)
set.add(str.charAt(i));
int i=1;
while (i <= str.length()) {
helper(set,"",i);
i++;
}
}
public static void helper(ArrayList<Character> set, String str, int m) {
if (m == 0) {
System.out.println(str);
}
for (int i = 0; i < set.size(); i++) {
Character c = set.get(i);
ArrayList<Character> newSet = (ArrayList<Character>) set.clone();
newSet.remove(c);
helper(newSet, str + c, m - 1);
}
}
}
import java.util.ArrayList;
public class Permutation {
public static void main(String args[]){
// ArrayList<Character> set = new ArrayList<Character> ();
// set.add('a');
// set.add('b');
// set.add('c');
// helper(set,"",3);
permutations("abcd");
}
// time: n+n*(n-1)+n*(n-1)*(n-2)+...+n! = O(n!)
public static void permutations(String str) {
ArrayList<Character> set = new ArrayList<Character> ();
for(int i=0;i<str.length();i++)
set.add(str.charAt(i));
int i=1;
while (i <= str.length()) {
helper(set,"",i);
i++;
}
}
public static void helper(ArrayList<Character> set, String str, int m) {
if (m == 0) {
System.out.println(str);
}
for (int i = 0; i < set.size(); i++) {
Character c = set.get(i);
ArrayList<Character> newSet = (ArrayList<Character>) set.clone();
newSet.remove(c);
helper(newSet, str + c, m - 1);
}
}
}
package com.interviews.salesforce;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* Given a string generate permutations of all possible lengths and print them
* in any order !
* Now print the permutations in dictionary order.
*
* @author Kailas Kore
*/
public class StringPermutation {
private static List<String> permutations;
private static char[] chars;
private static int possiblePermutations(int n, int l) {
int result = n;
for (int i = 1; i < l; i++) {
result = result * (n - i);
}
return result;
}
private static void printPermutations(int n, int l) {
int possiblePermutations = possiblePermutations(n, l);
System.out.println("length: " + l + " Possible Permutations: " + possiblePermutations);
if (permutations == null) {
permutations = new ArrayList<>(possiblePermutations);
for (char c : chars) {
permutations.add("" + c);
System.out.print(c + " ");
}
} else {
List<String> fixed = new ArrayList<>(permutations);
permutations = new ArrayList<>(possiblePermutations);
for (String str : fixed) {
for (char c : chars) {
if (str.indexOf(c) == -1) {
permutations.add(str + c);
System.out.print(str + c + " ");
}
}
}
}
System.out.println();
}
private static void permute(String input) {
int n = input.length();
if (n <= 1) {
System.out.println(input);
} else {
chars = input.toCharArray();
for (int l = 1; l <= n; l++) {
printPermutations(n, l);
}
}
}
public static void main(String[] args) {
System.out.println("Please input your string and hit ENTER :");
Scanner sc = new Scanner(System.in);
String input = sc.next();
permute(input.trim());
}
}
- Anonymous August 28, 2013