Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

If there are k distinct characters, the i^th character repeated n_i times, then the total number of permutations is given by

(n_1 + n_2 + ..+ n_k)!
------------------------------------------------ 
        n_1! n_2! ... n_k!

which is the multinomial coefficient.

Now we can use this to compute the rank of a given permutation as follows:

Consider the first character(leftmost). say it was the r^th one in the sorted order of characters.

Now if you replace the first character by any of the 1,2,3,..,(r-1)^th character and consider all possible permutations, each of these permutations will precede the given permutation. The total number can be computed using the above formula.

Once you compute the number for the first character, fix the first character, and repeat the same with the second character and so on.

- Loler October 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Of course, if it is a long string, we would probably need a BigInt package to do the computations (the rank itself could be a large number), and there might also be mathematical ways to simplify it.

- Anonymous October 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I can see how your algorithm would work for a word without duplicate letters, but when there are duplicates, I don't think this would be correct.

- Omega June 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class Permute{

static ArrayList<String> permutedStrings = new ArrayList<String>();
static HashSet<String> checkSet = new HashSet<String>();

public static void main(String args[]) {

String input = args[0];



Character[] inputChars = new Character[input.length()];

for(int i=0; i < input.length(); i++){
inputChars[i] = input.charAt(i);
}

Arrays.sort(inputChars);
//Character[] inputChars = new Character[]{'a','b','c'};
printPermutation("",inputChars);


for(int i=0; i< permutedStrings.size(); i++){

if(input.equalsIgnoreCase(permutedStrings.get(i))){

System.out.println("lexigrahical index is " + i);

}

}


}

public static void printPermutation(String input, Character[] chars){

if(chars.length == 0) {

if(checkSet.add(input)) {

permutedStrings.add(input);
System.out.println(input);

}

}

for(int i=0; i < chars.length; i++){

Character c = chars[i];

ArrayList newCharArray = new ArrayList();
newCharArray.addAll(Arrays.asList(chars));
newCharArray.remove(i);

String newInput = input+c;

//System.out.println("printing chars --->" + Arrays.toString(chars));
//System.out.println("printing out the new Array -->" + newCharArray);
//System.out.println("printing input --->" + newInput);
//System.out.println("---------------------------------------");

Character[] newArray = new Character[chars.length-1];
printPermutation(newInput, (Character[])newCharArray.toArray(newArray));

}


}

- random October 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> v; //element in Set in Sorted Order
int index,N;
vector<int> Set; //Set whose rank need to be determined
list<int> l; //element in Set in Sorted Order & need to refill whenever need find Rank of a Given Set
list<int>::iterator it,it1;
int FindRank(int N,int index)
{
if(N==1)return 1;
int count,T,R;
count=0;T=1;R=0;
it=l.begin();
while((*it)!=Set[index])it++,count++;
l.erase(it);
for(int i=2;i<N;i++)T*=i;
R=T*count;++index;
return R+FindRank(N-1,index);
}

- nikhilg October 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry ....it's Wrong...:(

- nikhilg October 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <string>
#include <list>
#include <map>
#include <fstream>
#include <cmath>
#include <queue>
#include <deque>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <complex>
#include <math.h>
#include<conio.h>
#include<iostream>
using namespace std;

vector<int> v;
vector<int> Set;
list< pair<int,int> > l;
list< pair<int,int> >::iterator it,it1;
int N,index;
int Fact[12];

int GteRankOfRepeteatedSet(int N,int index)
{
int T,D,R,P,Q;
P=1;Q=0;
if(N==1)return 1;
for(it=l.begin();it!=l.end();it++)
P*=Fact[(it->second)];
it=l.begin();
while((it->first)!=Set[index]){
D=P*Fact[(it->second)-1]/Fact[it->second];
Q+=Fact[N-1]/D;
it++;
}

if(it->second>1)it->second-=1;
else l.erase(it);
++index;
return Q+GteRankOfRepeteatedSet(N-1,index);
}

int main()
{
scanf("%d",&N);
int j,i,count;
for(int i=0;i<N;i++)
{scanf("%d",&j);v.push_back(j);}

Fact[0]=1;Fact[1]=1;Fact[2]=2;
for(int i=3;i<12;i++)Fact[i]=i*Fact[i-1];

i=0;
while(i<v.size()){
count=1;j=i+1;
while(j<v.size() && v[j]==v[i])j++,count++;
l.push_back(make_pair(v[i],count));
i=j;
if(i>=v.size())break;}

for(int i=0;i<N;i++)
{scanf("%d",&j);Set.push_back(j);}
cout<<endl<<GteRankOfRepeteatedSet(N,0)<<endl;


system("pause");
return 0;
}

- nikhilg October 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

enter N=10
element in V = 1 1 2 2 2 3 3 3 4 4
set to find rank = 3 2 1 3 2 1 3 2 4 4

Rank = 14584

- nikhilg October 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

enter 5
1 1 3 4 4
then 4 1 2 4 1

floating point exception.

- Psycho October 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

provide the proper i/p dude....
u have provided:
1 1 3 4 4
then Set :
4 1 2 4 1
which is not the permutation of (1,1,3,4,4).

- nikhilg October 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes! My bad!

- Psycho October 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm proposing a dynamic programming solution. Not sure if it's entirely correct, but here's the reasoning:

Let's use the string 'bcacba' as an example. If we go from left to right and consider how many permutations of this string has a higher lexicographical order, we'd get that for the first position, the permutation could be:
Any permutation that has the same character at this position (2 possibilities) AND where the rest of the sub string has a higher order.
Or
Any permutation that has a higher order character at this position (2 possibilities) AND where the rest of the sub string doesn't matter. (Because if we chose a higher order character at this position, then the final string will have higher order no matter what)

If we translate this into a formula, let's define some functions:
- S is the string, S(k) is the character at index k, S[i, j) is the sub string i->j, N is the number of characters
- P(k) is the number of higher order permutations in the sub string S[k, N)
- E(k) is the total number of characters equal to S(k) in S[k, N)
- H(k) is the total number of characters with higher order than S(k) in S[k, N)

So translated into a formula, we would get that
P(k) = E(k)*P(k+1) + H(k)*(N-k-1)!

This formula can be calculated backwards, so with 'bcacba', we would get
P(N-1) = 0 // there is only one character, so no permutation with higher order
P(N-2) = 1*0 + 1*(2-1)! = 1
'ab'
P(N-3) = 1*1 + 2*(3-1)! = 5
'abc'
'acb'
'bac'
'bca'
'cab'
P(N-4) = 2*5 + 0*3! = 10
'aabc'
'aacb'
'abac'
'abca'
'acab'
'aabc' << the two 'a's are swapped, so duplicates but different permutations
'aacb'
'abac'
'abca'
'acab'

etc.

- Martin October 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What are your thoughts on this? Worked on paper for me with a couple small examples. Taking for granted that words with same spelling are equivalent.

1. build a sorted map to hold the count for each character
2. for each character in the original sequence,
2.a. sum of characters coming before that one in the map (including duplicates)
2.b. while looping for ^, also count number of duplicate characters
2.c.1. calculate (length - position)! * value from 2.a
2.c.2. IF result from 2.b !=0, divide 2.c.1 value by (duplicates*2)
2.d subtract one from the map value corresponding to that character in the original sequence
2.e add calculated value to running total

- Ben October 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int fact(int f)
{
	if (f == 0) return 1;
	if (f <= 2) return f;
	return (f * fact(f - 1));
}
void solve(string s,int n)
{
	int ans = 1;
	int arr[26] = {0};
	int len = n - 1;
	for (int i = 0; i < n; i++) {
	    s[i] = toupper(s[i]);
	    arr[s[i] - 'A']++;
	}
	for(int i = 0; i < n; i++) {
		int temp = 0;
		int x = 1;
		char c = s[i];
 
		for(int j = 0; j < c - 'A'; j++) temp += arr[j];
		for (int j = 0; j < 26; j++) x = (x * fact(arr[j]));
		arr[c - 'A']--;
		ans = ans + (temp * ((fact(len)) / x));
		len--;
	}
	cout << ans;
}
int main()
{
	int i,n;
	string s;
	cin>>s;
	n=s.size();
	solve(s,n);
	return 0;
}

- ducking_hipster May 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's the C++ implementation to above written question

#include<iostream>
using namespace std;
int fact(int f)
{
	if (f == 0) return 1;
	if (f <= 2) return f;
	return (f * fact(f - 1));
}
void solve(string s,int n)
{
	int ans = 1;
	int arr[26] = {0};
	int len = n - 1;
	for (int i = 0; i < n; i++) {
	    s[i] = toupper(s[i]);
	    arr[s[i] - 'A']++;
	}
	for(int i = 0; i < n; i++) {
		int temp = 0;
		int x = 1;
		char c = s[i];
 
		for(int j = 0; j < c - 'A'; j++) temp += arr[j];
		for (int j = 0; j < 26; j++) x = (x * fact(arr[j]));
		arr[c - 'A']--;
		ans = ans + (temp * ((fact(len)) / x));
		len--;
	}
	cout << ans;
}
int main()
{
	int i,n;
	string s;
	cin>>s;
	n=s.size();
	solve(s,n);
	return 0;
}

- ducking_hipster May 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

bbbbaaaa gives answer 65 while it should be 70

- Rudransh May 26, 2019 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

bwt alg

- sailorconan October 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This comment has been deleted.

- Administrator October 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Maybe, but for an easier problem.

The difficult part is dealing with repeated characters and that does not deal with it.

- Anonymous October 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@shondik:

1) Why are you peddling your blog?

2) Why not post the gist here? Why do you expect people to read through a bunch of crap to get to what you think is relevant?

Deserve the downvote.

- Anonymous October 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

So, you think the post is not relevant.
May i ask you where did you find the post is wrong.
Do not let other people think in your way. If they want, they will read.
If you have a better solution, why don't you post it and let other readers judge it.
And its not my blog. I read it there and found it a nice solution.
So, posted the link here.
CareerCup has not well defined indentation. If i would have posted the entire content, it would be messy to read. It is better to go through the link.
If you would have been interested in the solution, you would have been read it carefully. But, i guess you are only interested in downvoting and writing sarcastic comments.

- Aashish October 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@shondik:

People have the right to whatever, including downvotes, don't they? No one is forcing anyone to think differently. All that is happening is some discussion.

btw, a good reason to downvote is answer with just links without any explanation whatsoever. Even if it is the greatest explanation you saw, the answer deserves a downvote. For instance, what if the site disappeared?

How hard is it to post a self sufficient gist along with the link?

- Anonymous October 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As to being interested in a solution, I find Loler's answer much more useful than that site's answer.

- Anonymous October 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@shondik: Don't make me laugh :-)! Personal? Seems like you are taking it too personally.

All I am interested in is helping this site maintain some quality. Broken links are bad in that respect and really bad, if an answer contains just that. The link might work now, but what if it disappears two months later. How useful do you think this answer will be then?

You can always edit your answer to add an explanation and say, for more details go here etc. That would be an excellent answer.

- Anonymous October 12, 2012 | Flag


Add a Comment
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.

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