Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
import java.util.List;
import java.util.ArrayList;
class Permutations {
private static List<String> permutations(String s) {
List<String> permutations = new ArrayList<String>();
if (s == null) {
return null;
} else if (s.length() == 0) {
permutations.add("");
return permutations;
}
List<String> remainder = permutations(s.substring(1));
for (String permutation : remainder) {
for (int i = 0; i <= permutation.length(); ++i) {
permutations.add(insertCharAt(permutation, s.charAt(0), i));
}
}
return permutations;
}
private static String insertCharAt(String s, char c, int i) {
return new StringBuilder(s).insert(i, c).toString();
}
}
O(N!) time and space. The problem cannot be solved in linear time because we have N! solutions (as Technoapurva said).
*
* @author akshay anand
*/
public class SUBsTRING {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
String str = "tesw";
// find all permutations
// permute(s);
Set<String> s = new HashSet<String>();
s = test(str,s);
System.out.println(s);
}
public static Set<String> test(String str, Set s){
if(str.length()==1){
s.add(str);
return s;
}
if(str.length()==2){
s.add(str.charAt(0)+""+str.charAt(1));
s.add(str.charAt(1)+""+str.charAt(0));
return s;
}
else
{
for(int i=0;i<str.length();i++){
String s1 = str.substring(0,i);
String s2 = str.substring(i, str.length());
s.add(s1+""+s2);
s.add(s2+""+s1);
s= test(s1,s);
s= test(s2,s);
}
}
return s;
}
*
* @author akshay anand
*/
public class SUBsTRING {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
String str = "tesw";
// find all permutations
// permute(s);
Set<String> s = new HashSet<String>();
s = test(str,s);
System.out.println(s);
}
public static Set<String> test(String str, Set s){
if(str.length()==1){
s.add(str);
return s;
}
if(str.length()==2){
s.add(str.charAt(0)+""+str.charAt(1));
s.add(str.charAt(1)+""+str.charAt(0));
return s;
}
else
{
for(int i=0;i<str.length();i++){
String s1 = str.substring(0,i);
String s2 = str.substring(i, str.length());
s.add(s1+""+s2);
s.add(s2+""+s1);
s= test(s1,s);
s= test(s2,s);
}
}
return s;
}
*
* @author akshay anand
*/
public class SUBsTRING {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
String str = "tesw";
// find all permutations
// permute(s);
Set<String> s = new HashSet<String>();
s = test(str,s);
System.out.println(s);
}
public static Set<String> test(String str, Set s){
if(str.length()==1){
s.add(str);
return s;
}
if(str.length()==2){
s.add(str.charAt(0)+""+str.charAt(1));
s.add(str.charAt(1)+""+str.charAt(0));
return s;
}
else
{
for(int i=0;i<str.length();i++){
String s1 = str.substring(0,i);
String s2 = str.substring(i, str.length());
s.add(s1+""+s2);
s.add(s2+""+s1);
s= test(s1,s);
s= test(s2,s);
}
}
return s;
}
/*end*/
public class Main {
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));
}
}
public static void main(String[] args) {
permutation("", "ABCD");
}
}
def permute_string(the_string):
string_list = list(the_string)
permute_string_internal('', 0, string_list)
def permute_string_internal(prefix, start_index, string_list):
if start_index < len(string_list):
char_at_start_index = string_list[start_index]
for index in range(start_index, len(string_list)):
char_at_index = string_list[index]
string_list[index] = char_at_start_index
string_list[start_index] = char_at_index
permute_string_internal(prefix + string_list[start_index], start_index + 1, string_list)
string_list[start_index] = char_at_start_index
string_list[index] = char_at_index
else:
print prefix
Below is the c++ code.
///
vector<string> permutations(string& str, const size_t idx = 0)
{
vector<string> result;
if (idx == str.length()) {
result.push_back (str);
}
for (size_t i = idx; i < str.length(); ++i) {
swapChar(str, idx, i);
result.push_back(permutations(str, idx + 1);
swapChar(str, idx, i);
}
return result;
}
\\\
Recursive and iterative solutions:
private static void permutationsRecursive(String letters) {
countRecursive= 0;
permutationsRecursive(letters, "");
}
private static void permutationsRecursive(String letters, String wordUntilNow) {
if (letters.length() > 0) {
for (int i = 0; i < letters.length(); i++) {
String newWordUntilNow = wordUntilNow + letters.charAt(i);
String newLetters = remove(letters, i);
permutationsRecursive(newLetters, newWordUntilNow);
}
}
else {
System.out.println(wordUntilNow);
}
}
private static final Hashtable<Integer, Long> factorials = new Hashtable<Integer, Long>();
private static long factorial(int n) {
long fac = 1;
while (n > 0) {
fac *= n--;
}
return fac;
}
private static void permutationsIterative(String letters) {
int size = letters.length();
long numberOfPermutations = factorials.get(size);
for (long
countIterative = numberOfPermutations; i = 0; i < numberOfPermutations; i++) {
String st = letters;
StringBuilder sl = new StringBuilder();
for (int j = size - 1; j >= 0; j--) {
int index = (int)((i / factorials.get(j)) % (j+1));
sl.append(st.charAt(index));
st = remove(st, index);
}
System.out.println(sl.toString());
}
}
It is impossible to solve this problem in O(n) time as the number of solutions is of the exponential order.
- technoapurva September 24, 2015