Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
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.
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));
}
}
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);
}
#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;
}
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
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).
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.
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
#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;
}
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;
}
Maybe, but for an easier problem.
The difficult part is dealing with repeated characters and that does not deal with it.
@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.
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.
@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?
As to being interested in a solution, I find Loler's answer much more useful than that site's answer.
@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.
If there are k distinct characters, the i^th character repeated n_i times, then the total number of permutations is given by
which is the multinomial coefficient.
- Loler October 11, 2012Now 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.