## Amazon Interview Question for Software Engineer / Developers

• 0

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.

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

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.

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

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.

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) {

System.out.println(input);

}

}

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

Character c = chars[i];

ArrayList newCharArray = new ArrayList();
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));

}

}

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

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

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

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

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

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

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

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

floating point exception.

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

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).

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

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.

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

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

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

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

bbbbaaaa gives answer 65 while it should be 70

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

bwt alg

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

This comment has been deleted.

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

Maybe, but for an easier problem.

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

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

@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.

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

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

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

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

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

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

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

@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.

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.