Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
Just a twist:
static void permutate(String[] words, String permutation){
if (words.length == 0){
System.out.println(permutation);
}
else {
String w = words[0];
for (int i = 0; i < w.length(); i++){
permutate(ArrayUtils.subArray(words, 1, words.length, permutation + w.charAt(i));
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
String[] words = {"red", "fox", "super"};
permutate(words, "");
}
var permutate = function (A, B, s) {
if (!A.length) {
B.push(s);
return;
}
var word = A[0];
var i;
for (i = 0; i < word.length; i++) {
permutate(A.slice(1), B, s + word.charAt(i));
}
};
var permutateList = function (A) {
var B = [];
permutate(A, B, "");
return B;
};
console.log(permutateList(["red", "fox", "super"]));
In C#
static void Main(string[] args)
{
string[] words = { "red", "fox", "super" };
printPermutate(words, 0, "");
Console.ReadKey(); // Optional
}
public static void printPermutate(string[] words, int index, string print)
{
string word = words[index];
for (int x = 0; x < word.Length; x++)
{
if ((print + word[x].ToString()).Length == words.Count())
{
Console.WriteLine(print + word[x].ToString());
}
else if (index+1 < words.Count())
{
printPermutate(words, index + 1, print + word[x].ToString());
}
}
}
this does the job without recursion but prints results in a different order:
public static void main(String[] args) {
String[] strs = {"red", "fox", "super"};
solveMultiPerms(strs);
}
public static void solveMultiPerms(String[] strs) {
String[][] sets = new String[strs.length][];
for (int i = 0; i < strs.length; i++) {
sets[i] = new String[strs[i].length()];
char[] chars = strs[i].toCharArray();
for (int j = 0; j < chars.length; j++) {
sets[i][j] = new Character(chars[j]).toString();
}
}
List<String> results = new ArrayList<>();
int[] state = new int[sets.length];
int p = 0;
boolean stillHasMore = true;
StringBuilder sb = null;
while (stillHasMore) {
sb = new StringBuilder();
for (int i = 0; i < state.length; i++) {
sb.append(sets[i][state[i]]);
}
results.add(sb.toString());
state[p]++;
while (stillHasMore && state[p] == sets[p].length) {
state[p] = 0;
p++;
if (p == sets.length) {
stillHasMore = false;
} else {
state[p]++;
}
}
p = 0;
}
for (String string : results) {
System.out.println(string);
}
}
#include<stdio.h>
void printList(char **l, int length) {
for(int i=0; i<length; i++)
printf("%s ", l[i]);
printf("\n");
}
void swapList(char *s[], int i, int j) {
char *temp = s[i];
s[i] = s[j];
s[j] = temp;
}
void permuteList(char **l, int start, int len) {
if(start==len)
printList(l, len);
for(int i=start; i<len; i++) {
swapList(l, start, i);
permuteList(l, start+1, len);
swapList(l, start, i);
}
}
int main() {
char *list[3] = {"the", "quick", "brown"};
permuteList(list, 0, 3);
return 0;
}
Sorry I didn't make this question clear, this question is supposed permutate the characters instead of who string, as input {"red", "fox", "super" }, the expected output is
rfs
rfu
rfp
rfe
rfr
ros
rou
rop
roe
ror
rxs
rxu
rxp
rxe
rxr
efs
efu
efp
efe
efr
eos
eou
eop
eoe
eor
exs
exu
exp
exe
exr
dfs
dfu
dfp
dfe
dfr
dos
dou
dop
doe
dor
dxs
dxu
dxp
dxe
dxr
A javascript implementation:
function permutate( arr , str ) {
str = str ? str : '';
var tmpArr;
if (arr.length > 0) {
tmpArr= arr[0].split('');
for (var i=0; i< tmpArr.length; i++) {
permutate (arr.slice(1),str+arr[0][i]);
}
}
else {
console.log(str);
}
}
Exmaple:
permutate(["red","fox","super"]);
Seems easy enough to do a recursion.
public static IEnumrable<string> PermuteLetters(List<string> words)
{
HashSet<string> result = new HashSet<string>();
PermuteLettersHelper(
words,
String.Empty,
0,
result);
return result;
}
private static PermuteLettersHelper(
List<string> words,
string S,
int index,
HashSet<string> result)
{
if(index >= words.Count)
{
if(!result.Contains(S))
{
result.Add(S);
}
}
else
{
foreach(char c in words[index])
{
PermuteLettersHelper(words, S + c, index + 1, result);
}
}
}
Iterative solution-
public static void permuteStrings() {
List<String> inlist = Arrays.asList("quick","fox");
List<String> result = new ArrayList<>();
for(String each : inlist) {
char[] carray = each.toCharArray();
List<String> temp = new ArrayList<>();
for(char c : carray) {
if(result.size() > 0) {
for(String eachRes : result) {
StringBuilder sb = new StringBuilder(eachRes);
sb.append(c);
temp.add(sb.toString());
}
} else {
temp.add(String.valueOf(c));
}
}
result = temp;
}
System.out.println(result);
}
Here is my version of solution on C#
private IEnumerable<Char> getSymbol(string word) {
foreach (char c in word) {
yield return c;
}
}
public IEnumerable<String> getPermutations(int index, string[] words) {
foreach (char c in getSymbol(words[index])) {
if (index < words.Length - 1) {
foreach(string s in getPermutations(index + 1, words)) {
yield return c + s;
}
}
else {
yield return c.ToString();
}
}
}
public void permuteChar(String[] str){
if (str==null) return;
int[] indices = new int[str.length];
while (indices[0]!=str[0].length()){
StringBuilder s = new StringBuilder();
for (int i=0; i<str.length; i++)
s.append(str[i].charAt(indices[i]));
for (int i=str.length-1; i>=0; i--)
if (indices[i]==str[i].length()-1 && i!=0)
indices[i]=0;
else {
indices[i]++;
break;
}
System.out.println(s.toString());
}
}
public void permuteChar(String[] str){
if (str==null) return;
int[] indices = new int[str.length];
while (indices[0]!=str[0].length()){
StringBuilder s = new StringBuilder();
for (int i=0; i<str.length; i++)
s.append(str[i].charAt(indices[i]));
for (int i=str.length-1; i>=0; i--)
if (indices[i]==str[i].length()-1 && i!=0)
indices[i]=0;
else {
indices[i]++;
break;
}
System.out.println(s.toString());
}
}
Iterative solution:
fn (String [] words) {
Set<String> results = new HashSet<String>();
Set<String> tempResults = new HashSet<String>();
for (String w : words) {
for (Character c : w) {
for (String result : results) {
tempResults.add(result + c);
}
}
results = tempResults;
tempResults = new HashSet<String>();
}
for (String result : results) {
print(result);
}
}
public class Test {
public static void main(String[] args) {
String a[] = {"red","fox","super"};
permut(a,"",0);
}
public static void permut(String[] a, String res, int j) {
if(res.length() == a.length) {
System.out.println(res);
return;
}
for(int i=0;i<a[j].length();i++) {
permut(a,res+a[j].charAt(i),j+1);
}
}
This is my solution.
import java.util.ArrayList;
import java.util.List;
public class ListPermutator {
private static void permutateList(int[] counters, int[] lengths,
int currentLevel, List<String> inputList, List<String> outputList) {
if (currentLevel == counters.length) {
String result = "";
for (int i = 0; i < counters.length; ++i) {
result += inputList.get(i).charAt(counters[i]);
}
outputList.add(result);
} else {
for (counters[currentLevel] = 0; counters[currentLevel] < lengths[currentLevel]; counters[currentLevel]++) {
permutateList(counters, lengths, currentLevel + 1, inputList, outputList);
}
}
}
public static List<String> permutateList(List<String> inputList) {
List<String> outputList = new ArrayList<String>();
int[] counters = new int[inputList.size()];
int[] lengths = new int[inputList.size()];
for (int i = 0; i < inputList.size(); ++i) {
counters[i] = 0;
lengths[i] = inputList.get(i).length();
}
permutateList(counters, lengths, 0, inputList, outputList);
return outputList;
}
public static void main(String[] args) {
List<String> inputList = new ArrayList<>();
inputList.add("red");
inputList.add("fox");
inputList.add("super");
List<String> output = permutateList(inputList);
for (String result : output) {
System.out.println(result);
}
}
}
Recursive and linear implementation.
words : input
result : result
private List<String> result = new ArrayList<String>();
private String[] words;
// start with constructWord("");
public void constructWord(String prefix) {
if (prefix.length() == words.length - 1) {
for (char c : words[prefix.length()].toCharArray()) {
result.add(prefix + c);
}
} else {
for (char c : words[prefix.length()].toCharArray()) {
constructWord(prefix + c);
}
}
}
public void contstructLinear() {
result.clear();
result.add("");
int currentIndex = 0;
while (currentIndex != words.length) {
for (String s : result) {
Set<String> newWords = new HashSet<String>();
for (char c : words[currentIndex].toCharArray()) {
newWords.add(s + c);
}
result.remove(s);
result.addAll(newWords);
}
currentIndex += 1;
}
}
void printAllCombination(const vector<string> &a)
{
int n = a.size(), i = 0; string s(n, ' '); vector<int> index(n, -1);
while (i >= 0)
{
++index[i];
if (index[i] > 0)
{
while (index[i] < a[i].size() && a[i][index[i]] == a[i][index[i] - 1]) ++index[i];
}
if (index[i] < a[i].size())
{
s[i] = a[i][index[i]];
if (i == n - 1) cout << s << endl;
else ++i;
}
else index[i--] = -1;
}
}
public static void permuteListOfStrings(List<String> values, String result) {
if (result.length() == values.size()) {
System.out.println(result);
return;
}
for (int j = 0; j < values.get(result.length()).length(); j++) {
permuteListOfStrings(values, result + values.get(result.length()).charAt(j));
}
}
public static void permuteListOfStrings(List<String> values, String result) {
if (result.length() == values.size()) {
System.out.println(result);
return;
}
for (int j = 0; j < values.get(result.length()).length(); j++) {
permuteListOfStrings(values, result + values.get(result.length()).charAt(j));
}
}
function permutate($words, $depth, $permutation)
{
if($depth == count($words))
{
echo $permutation . "\n";
}
else
{
$word = $words[$depth];
$letters = str_split($word);
for($i = 0; $i < count($letters); $i++)
{
$letter = $letters[$i];
permutate($words, $depth+1, $permutation . $letter);
}
}
}
permutate(array('to','an','ex'), 0, "");
public class PermutateStrings {
static List<String> perms(List<String> words, int current) {
if (current == words.size())
return new ArrayList<String>();
String word = words.get(current);
List<String> results = new ArrayList<String>();
List<String> sub = perms(words, current + 1);
if (sub.isEmpty()) {
for (int i = 0; i < word.length(); i++) {
results.add("" + word.charAt(i));
}
} else {
for (int i = 0; i < word.length(); i++) {
for (String subWord : sub) {
results.add(word.charAt(i) + subWord);
}
}
}
return results;
}
public static void main(String[] args) {
System.out.println(perms(Arrays.asList("red", "fox", "super"), 0));
}
}
Very naive, but simple to understand solution
void permutate(List<String> strings) {
for (int i = 0; i < strings.size(); i++) {
String ith = strings.get(i);
for (int j = (i + 1); j < strings.size(); j++) {
String jth = strings.get(j);
permutate(ith, jth);
}
}
}
void permutate(String lhs, String rhs) {
for (int i = 0; i < lhs.length; i++) {
char ith = lhs.charAt(i);
for (int j = 0; j < rhs.length; j++) {
char jth = rhs.charAt(j);
System.out.println(String.format("%s%s", ith, jth));
}
}
}
Use backtracking :
#include <iostream>
#include <vector>
using namespace std;
void permute(vector<string> v, string s, int curr){
if(curr == v.size()){
cout<<s<<endl;
return;
}
for(int i=0;i<v[curr].length();i++){
s.push_back(v[curr][i]);
permute(v,s,curr+1);
//Triggerd backtracking
s.erase(s.end()-1);
}
}
int main(){
int N;
string input;
vector<string> v;
cout<<"Size = ";
cin>>N;
cout<<endl;
for(int i=0;i<N;i++){
cout<<"input "<<i+1<<" : ";
cin>>input;
v.push_back(input);
}
cout<<"Result : "<<endl;
permute(v,"",0);
return 0;
}
Use backtracking :
#include <iostream>
#include <vector>
using namespace std;
void permute(vector<string> v, string s, int curr){
if(curr == v.size()){
cout<<s<<endl;
return;
}
for(int i=0;i<v[curr].length();i++){
s.push_back(v[curr][i]);
permute(v,s,curr+1);
//Triggerd backtracking
s.erase(s.end()-1);
}
}
int main(){
int N;
string input;
vector<string> v;
cout<<"Size = ";
cin>>N;
cout<<endl;
for(int i=0;i<N;i++){
cout<<"input "<<i+1<<" : ";
cin>>input;
v.push_back(input);
}
cout<<"Result : "<<endl;
permute(v,"",0);
return 0;
}
Backtracking Solution :
#include <iostream>
#include <vector>
using namespace std;
void permute(vector<string> v, string s, int curr){
if(curr == v.size()){
cout<<s<<endl;
return;
}
for(int i=0;i<v[curr].length();i++){
s.push_back(v[curr][i]);
permute(v,s,curr+1);
//Triggerd backtracking
s.erase(s.end()-1);
}
}
int main(){
int N;
string input;
vector<string> v;
cout<<"Size = ";
cin>>N;
cout<<endl;
for(int i=0;i<N;i++){
cout<<"input "<<i+1<<" : ";
cin>>input;
v.push_back(input);
}
cout<<"Result : "<<endl;
permute(v,"",0);
return 0;
}
Here is the working code in C++.
void permuate(string seed, int depth, string* list, int inputLength, int maxlen)
{
if (seed.length() == maxlen || depth >= inputLength)
{
cout << seed << endl;
return;
}
string source = list[depth];
for(int i = 0; i < source.length(); i++)
{
string newSeed = seed;
newSeed.push_back(source.at(i));
permuate(newSeed, depth+1, list, inputLength, maxlen);
}
}
func permutate(word1:String , word2:String , word3:String ) -> [String] {
var permutedStrings = [String]()
var permutedWord = ""
for a in word1 {
for b in word2 {
for c in word3 {
permutedWord = "\(a)\(b)\(c)"
permutedStrings.append(permutedWord)
}
}
}
return permutedStrings
}
var arr = permutate("red", "fox", "super")
void permuteList(char **arr, char buffer[], int blen, int len, int size) {
if (blen == size) {
buffer[size] = '\0';
printf("%s\n", buffer);
return;
}
int i;
for (i = 0; i < size; i++) {
buffer[blen] = arr[len][i];
permuteList(arr, buffer, blen+1, len+1, size);
}
}
int main() {
char *list[3] = {"the", "quick", "brown"};
int size = sizeof(list)/sizeof(list[0]);
char buffer[size+1];
// buffer[size] = '\0';
permuteList(list, buffer, 0, 0, sizeof(list)/sizeof(list[0]));
return 0;
}
void permuteList(char **arr, char buffer[], int blen, int len, int size) {
if (blen == size) {
buffer[size] = '\0';
printf("%s\n", buffer);
return;
}
int i;
for (i = 0; i < size; i++) {
buffer[blen] = arr[len][i];
permuteList(arr, buffer, blen+1, len+1, size);
}
}
int main() {
char *list[3] = {"the", "quick", "brown"};
int size = sizeof(list)/sizeof(list[0]);
char buffer[size+1];
// buffer[size] = '\0';
permuteList(list, buffer, 0, 0, sizeof(list)/sizeof(list[0]));
return 0;
}
void permuteList(char **arr, char buffer[], int blen, int len, int size) {
if (blen == size) {
buffer[size] = '\0';
printf("%s\n", buffer);
return;
}
int i;
for (i = 0; i < size; i++) {
buffer[blen] = arr[len][i];
permuteList(arr, buffer, blen+1, len+1, size);
}
}
int main() {
char *list[3] = {"the", "quick", "brown"};
int size = sizeof(list)/sizeof(list[0]);
char buffer[size+1];
// buffer[size] = '\0';
permuteList(list, buffer, 0, 0, sizeof(list)/sizeof(list[0]));
return 0;
}
Here is an example to print output without return anything and without worry about the performance.
public static void printPermutate(String[] listStr)
{
recPrint(listStr, "", 0);
}
public static void recPrint(String[] listStr, String current, int index)
{
if(index == listStr.length-1)
{
for(char ea : listStr[index].toCharArray())
{
System.out.println(current+ea);
}
}
else
{
for(char ea : listStr[index].toCharArray())
{
recPrint(listStr,current+ea,index+1);
}
}
}
public static void main(String[] args)
{
String arr[] = {"red", "fox", "super", "hegde"};
permute(arr, "");
}
public static void permute(String arr[], String str_so_far)
{
if (arr.length == 1)
{
String first_str = arr[0];
for (int i = 0; i < first_str.length(); i++)
System.out.println(str_so_far + first_str.substring(i, i + 1));
}
else
{
String first_str = arr[0];
String rem_arr[] = new String[arr.length - 1];
for (int i = 1; i < arr.length; i++)
{
rem_arr[i - 1] = arr[i];
}
for (int i = 0; i < first_str.length(); i++)
{
permute(rem_arr, str_so_far + first_str.substring(i, i + 1));
}
}
}
public static void permute(String[] arr , int depth , String result){
if(depth==arr.length){
System.out.println(result);
return;
}
for(int i=0;i<=arr[depth].length()-1;i++){
permute(arr, depth+1, result+arr[depth].substring(i,i+1));
}
}
public static void main(String[] args) {
String[] arr = {"red", "fox", "super" };
permute(arr,0,"");
}
String[] strs = {"Hello", "World", "Test"};
permutesolver(strs, "", 0, strs.length);
private void permutesolver(String[] str , String chosen , int k, int size)
{
if(k == size) {
System.out.println(chosen);
}
else {
for (int i = 0; i < str[k].length(); i++) {
chosen = chosen + str[k].charAt(i); //chose
permutesolver(str, chosen, k + 1, size); // explore
chosen = chosen.substring(0, chosen.length() - 1); //unchoose.
}
}
}
This worked for me - Try it out.
public PermuteStrings()
{
String[] strs = {"Hello", "World", "Test"};
permutesolver(strs, "", 0, strs.length);
}
private void permutesolver(String[] str , String chosen , int k, int size)
{
if(k == size) {
System.out.println(chosen);
}
else {
for (int i = 0; i < str[k].length(); i++) {
chosen = chosen + str[k].charAt(i);
permutesolver(str, chosen, k + 1, size);
chosen = chosen.substring(0, chosen.length() - 1);
}
}
}
This gives the correct output but can be made neater, will appreciate if someone can help fix the number of recursive calls made -
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static Set<String> resultStrings = new HashSet<String>();
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(permuteSetOfString("fox", "red", "super"));
}
public static Set<String> permuteSetOfString(String a, String b, String c){
char first = a.charAt(0);
if(a.length() > 1){
permuteSetOfString(a.substring(1),b,c);
}
char second = b.charAt(0);
if(b.length() > 1){
permuteSetOfString(a,b.substring(1),c);
}
char third = c.charAt(0);
if(c.length() > 1){
permuteSetOfString(a,b,c.substring(1));
}
String result = first + "" + second + "" + third + "";
resultStrings.add(result);
return resultStrings;
}
}
I hope my Java solution helps:
- inucoder April 19, 2015