## Amazon Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
0
of 0 vote

If A,B,C are three words, to generate all permutations of the three words,
Perm(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.

Comment hidden because of low score. Click to expand.
0

``````f(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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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??

Comment hidden because of low score. Click to expand.
0

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
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

it could be done rather a similar kind of done with character permutations,
instead of char replace with char*

func(char** a, size)
{
if(size ==0)
print(all strings);
else
{
for(i = 0 to n-1)
{
swap(*a,i);
func(*a+1,size-1);
swap(*a,i);
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

# 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") ;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
{
}
// 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)))
{
}
}
}
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))
{
}
}
return subList;
}

public static void main(final String[] args)
{
for (final String s : permutations(Arrays.asList("This ", "is ", "String ")))
{
System.out.println(s);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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
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");
}

Comment hidden because of low score. Click to expand.
0

nice code... it works :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

<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
{
String s;
}
}

</pre><pre title="CodeMonkey67975" input="yes">bolo boss</pre>

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think its concept of CATALAN Number

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

comb(i) {
if(i == n) { print res; return; }
for(j = 0; j < n; ++j) {
if(res doesn't contain word[j]) {
res[i] = word[j];
comb(i+1);
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is permutation, not combination

Comment hidden because of low score. Click to expand.
0
of 0 vote

First split the input string into words and keep the words in a char* array[] ..The it will better to work on permutation using indexes rather than with strings..working with integers will be easier..

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def fun(String testString):
wordList = list(testString)
#print all the combinations.``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````for(i = 5; i < 10; i++){
cout << nextpermutation();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void writer(String str, String builtStr)
{
String s;

for(int i = 0;i < str.length(); i++)
{
s = str.replace(str.charAt(i) + "", "");
writer(s, builtStr + str.charAt(i));
}

if(str.length() == 0)
System.out.println(++counter+":"+builtStr);
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.