Amazon Interview Question Software Engineer / Developers




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.

- Metta on September 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jiangok2006 on October 04, 2010 | Flag
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??

- codeNombre on September 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Metta on September 22, 2010 | Flag
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);
}
}
}

- surender on September 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Algotron on September 22, 2010 | Flag Reply
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)
        {
            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);
        }
    }
}

- mattj777 at yahoo on September 22, 2010 | Flag Reply
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.

- Neo on September 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Goutam on September 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice code... it works :)

- tapesh on September 24, 2010 | Flag
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;
	}


}

- HSJ on October 04, 2010 | Flag Reply
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
{
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>

- saksharhere on October 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think its concept of CATALAN Number

- Sunil on October 16, 2010 | Flag Reply
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

- Manish on October 17, 2010 | Flag Reply
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);
}
}

}

- coolpk on November 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is permutation, not combination

- Anonymous on January 09, 2011 | Flag Reply
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..

- genthu on January 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- weijiang2009 on February 06, 2011 | Flag Reply
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);
			}
		}

}

- A on January 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous on May 17, 2013 | Flag Reply
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);
    
      
    }

}

- rohiteshrao on February 08, 2014 | Flag Reply


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

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.

Learn More

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.

Learn More