Amazon Interview Question
Software Engineer / Developersf(A)={A}
f(B)={B}
f(C)={C}
f(A,B)={AB, BA}=A*f(B)+B*f(A)
f(A,C)={AC,CA}=A*f(C)+C*f(A)
f(B,C)={BC,CB}=B*f(c)+C*f(B)
f(A,B,C)=A*f(B,C)+B*f(A,C)+C*f(A,B)
=A*(B*f(C)+C*f(B)) + B*(A*f(C)+C*f(A)) + C(A*f(B)+B*f(A))
void f(arr s)
{
foreach x in s
print({x}, {s-x})
}
void print(arr S1, arr S2)
{
if(S1.len==k)
print(S1);
else
foreach x in S2
print(S1+x, S2-x);
}
I still cant figure out, how did you manage to get all the possible combinations using your recursive call.
For Example:
A recursive Perm(This, is) can generate "This is" but not sure how to get the "is This" part.
In my opinion there are two parts of recursion here one is generating the possibilities for a given starting word and then changing a the given starting word.
What do you think??
codeNombre, that part is taken care of by "Place B at every position of Perm(A)", not the recursion.
For example,
/// Places the given string insertThis at all possible /// positions of the list of words given. For eg.,
/// insertThis = "is" and wordList = "This" will generate
// "This is" and "is This"
void InsertAtAllPositions(string insertThis, List<string> wordList)
{
// Iterate through all positions
for(int i = 0; i < wordList.Length; i++)
{
StringBuilder stringBuilder = new StringBuilder();
for(int j = 0; j < i; j++)
{
stringBuilder.Append(wordList[j])
}
// Insert given word
stringBuilder.Append(insertThis);
for(int j = i; j < wordList.Length; j++)
{
stringBuilder.Append(wordList[j])
}
// now stringBuilder contains one combination
// Add stringBuilder.ToString to a list A
}
// A contains all the permutations
}
}
This is about it
# include <iostream>
# include <string>
# include <vector>
# include <algorithm>
# include <sstream>
using namespace std ;
vector <string> a(10) ;
bool b[10] ;
void fun( int n , vector < string > &vec)
{
for(int i = 1 ; i <= 3 ; i++ )
{
if(b[i] == false)
{
a[n] = vec[i-1] ;
b[i]= true ;
if( n < 3)
fun(n+1,vec) ;
else
{
for( int i = 1 ; i <=n ; i++)
cout<<a[i]<<" " ;
cout<<"\n" ;
}
b[i] = false ;
}
}
}
int main()
{
// fun(1) ;
string test("This is String") ;
vector< string > first ;
istringstream in(test);
while(in)
{
string rem ;
in>>rem ;
first.push_back(rem) ;
cout<<rem<<"\n" ;
}
fun(1,first) ;
system("PAUSE") ;
}
Assuming you have parsed the words into a collection, this can be done by recursively generating the permutations.
In Java:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Permutations
{
public static List<String> permutations(final List<String> words)
{
final List<String> perms = new ArrayList<String>();
// Base case.
if (words.size() == 1)
{
perms.add(words.get(0));
}
// Take each word and append to it the recursively computed permutations of the remaining elements.
else
{
for (final String head : words)
{
for (final String permutation : permutations(subList(head, words)))
{
perms.add(head + permutation);
}
}
}
return perms;
}
public static List<String> subList(final String elementToRemove, final List<String> elements)
{
final List<String> subList = new ArrayList<String>();
for (final String s : elements)
{
if (!s.equals(elementToRemove))
{
subList.add(s);
}
}
return subList;
}
public static void main(final String[] args)
{
for (final String s : permutations(Arrays.asList("This ", "is ", "String ")))
{
System.out.println(s);
}
}
}
The solution should be generic. The recursive function would be f(a,b) returns ab and ba. for the terminating condition of no. of tokens = 2. In case of higher the f should be calling itself like f(a,b,c) = a + f(b,c) + b + f(a,c) + c + f(a,b). By a,b,c I mean a vector or arraylist which contains a,b,c as string literals.
Will post the code soon.
void Permute(string str){
int size=str.size();
int Q=1; //number of permutation.
for (int i=1; i<=size; i++)
Q=Q*i;
string holes(str);
string balls(str);
for (int i=0; i<Q; i++)
{
holes.resize(str.size()); // clear all the holes
balls.assign(str); //make balls ready.
int ball_number;//=i/(size-1); // find the first ball;
int hole_number=0; //locate the first hole.
int resultNumber=Q;
int position=i;
while (balls.size()-1>0)
{
resultNumber=resultNumber/balls.size();
ball_number=position/resultNumber; // find the first ball;
// choose one ball and drop it in the hole.
holes[hole_number]=balls[ball_number];
//remove the seleted ball
balls.erase(ball_number,1);
hole_number++; //move to next hole
//find the offset to pick the next ball.
position=position%resultNumber;
}
// for the last ball
holes[hole_number]=balls[0];
cout<<holes<<endl;
}
}
void main()
{
Permute("abc");
}
public class ActualStringCombination {
/**
* @param args
*/
public static void main(String[] args) {
// String s= "abcdef";
String s[]= {"This", "is", "String"};
printCombinations(s);
}
private static void printCombinations(String s[]) {
// char[] ch = s.toCharArray();
permutation(s, 0, s.length-1);
}
private static void permutation(String[] s, int firstIndex, int lastIndex) {
if(lastIndex - firstIndex == 1) {
print(s);
swap(firstIndex, lastIndex, s);
print(s);
/*restore the order in string array*/
swap(firstIndex, lastIndex, s);
} else {
/* swap String at firstindex with all the next Strings in the array*/
for(int i = firstIndex, j= 0; i <= lastIndex ; i++, j++) {
swap(firstIndex, firstIndex+j, s);
/*With current initial String(s) find combinations for rest of the strings */
permutation(s, firstIndex +1, lastIndex);
/*restore the order in string array */
swap(firstIndex, firstIndex+j, s);
}
}
}
private static void print(String[] s) {
for(int i =0;i < s.length;i++){
System.out.print(s[i]+"\t");
}
System.out.println();
}
private static void swap(int firstIndex, int lastIndex, String[] s) {
String temp = s[lastIndex];
s[lastIndex]=s[firstIndex];
s[firstIndex]=temp;
}
}
<pre lang="java" line="1" title="CodeMonkey67975" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}
</pre><pre title="CodeMonkey67975" input="yes">bolo boss</pre>
First store the individual words of the string in array of string and pass that to following function
void arrange(string s[],int l,int k)
{
if(l==k){
for(int i=0;i<k;i++)
cout<<s[i]<<" ";
cout<<endl;
return;
}
for(int i=l;i<k;i++){
swap(s[l],s[i]);
arrange(s,l+1,k);
}
return;
}
initially l=0 and k is number of words in string
public static void permutation(ArrayList<String> str){
String prefix = "";
permutation(prefix, str);
}
public static void permutation(String prefix, ArrayList<String> str){
int n = str.size();
if(n == 0){
System.out.println(prefix);
}else{
for(int i = 0 ; i < str.size() ; i++){
ArrayList<String> strClone = (ArrayList<String>) str.clone();
permutation(prefix + " " + strClone.remove(i), strClone);
}
}
}
public class PermWord {
public static void wperm(String[] a, int n) {
if (n == 1) {
StringBuilder sb = new StringBuilder();
for(String i : a)sb.append(i).append(" ");
System.out.println(sb.toString());
return;
}
for (int i = 0; i < n; i++) {
swap(a, i, n-1);
wperm(a, n-1);
swap(a, i, n-1);
}
}
private static void swap(String[] a, int i, int j) {
String c;
c = a[i]; a[i] = a[j]; a[j] = c;
}
public static void main(String[] args) {
int N =3;
String a = "Hello My Friends";
String[] c = a.split("\\s+");
wperm(c,3);
}
}
If A,B,C are three words, to generate all permutations of the three words,
- Metta September 21, 2010Perm(A,B,C) = Place C at every position in Perm(A,B)
Perm(A,B) = Place B at every position in Perm(A)
Perm(A) = A
So, we get
Perm(This) = This
Perm(This,is) = This is, is This
Perm(This, is, string) = This is string, This string is, string This is; is This string, is string This, string is This
So, you can write a simple recursive method to do this.