Google Interview Question Software Engineer / Developers
@crabmilk: could you please explain when the n'th student is not equal in rank to any one else why r we multiplying f(n-1,k-1) with k
the correct should be:
f(N, k) = f(N-1, k-1) + f(N-1, k) * k
f(N-1, k-1) ==>we create a new rank
f(N-1, k) * k ==> we put this student to one of the current k ranks
bg2d I think you are wrong. You have several options to save the number into the slot, it doesn't need to be last. Maybe you look at the problem differently
The problem with the solution above is that f(0,k) must be defined as 0, otherwise you will count even solutions in which you didn't use all of the ranks..
Otherwise I think solution is quite good, it took me a while to understand why it works. The key idea here is it changes the question to "distribute k numbers into n slots, where every single number needs to be used." So thinking about Nth slot, you can give there one of k numbers and call it on smaller array.
The answer to the whole question is then sum of f(N, 1<=k<=N), complexity O(n^2)
N=3 we can count
3! cases when no ties
if one person is first and the other two are tied - 3 cases just choose the first
if two people are tied for first and one is second u have again 3 cases - choose the second
finally all tied for first - 1 case
so total of 6+3+3+1=13
sum i=1 to 3 i!(i^(n-i))=1x1+2x2+6x1=11 does not work according to me
also n! is the best not the worst case - 3!<13
I am not sure; I dont know much about circular dependency
I realize that this formula calls back the function more and more times each round but isn't it possible to store each P(N) staring with P(0) in a list and then add up a node each time and for the next one just go thru the list using the formula
this way you will calculate all the P's
seems ugly but It looks like doable for small N's
unfortunately the answer for N=1000 is bigger then 1000! but that's the nature of it
N! +
C(N,2) * (N-1)! +
C(N,3) * (N-2)! +
...
C(N,N) * (N-(N-1))!
For N=2, this gives
2! +
C(2,2) * (2-(2-1))!
=2+ 1*1=3
For N=3, this gives
3! +
C(3,2) * 2! +
C(3,3) * 1
=6+6+1=13
S1, S2 , S3 ... are students
case 1) if n == 1, then number of possibilities
1
case 2) if n==2 ( two students S1 and S2 ), then number of possibilities
3
---------
S1 S2
1 1
1 2
2 1
---------
case 3) Three students S1, S2, S3
number of possibilities 13.
S1 S2 S3
1 1 1
1 1 2
1 2 1
2 1 1
1 2 2
2 1 2
2 2 1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
-----------
Code for this problem
// 'n' is number of students.
long int NumWays(int n)
{
if( n < 0 )
{
return -1; //error
}
else if( n <= 1)
{
return 1;
}
else
{
int i =1;
long sum = 0;
while ( i <= n )
{
sum + = Combinations( n, i ) * NumWays( n - i );
i++ ;
}
return sum;
}
}
// combinations function
long int Combinations( int n, int k )
{
// here this API returns nCk i.e ( n! /((n-k)! * k! );
return nCk;
}
#include <stdio.h>
#include <stdlib.h>
long long rank(long long n)
{
long long *f = calloc((n + 1) * (n + 1), sizeof(long long));
long long i, j;
long long *tmp = malloc((n + 1) * sizeof(long long));
long long fac = 1;
for(i = 2; i < n + 1; ++i){
fac *= i;
tmp[i] = i * (i - 1)/2 * fac;
}
for(i = 1; i < n + 1; ++i){
for(j = 1; j <= i; ++j){
if(j == 1){
f[i * (n + 1) + j] = 1;
continue;
}
if(j == i){
f[i * (n + 1) + j] = f[(i - 1) * (n + 1) + (i - 1)] * i;
continue;
}
f[i * (n + 1) + j] = j * f[(i - 1) * (n + 1) + j] + tmp[j];
}
}
long long ret = 0;
for(j = 1; j < n+1; ++j)
ret += f[n * (n + 1) + j];
return ret;
}
int main(int argc, char *argv[])
{
int n = atoi(argv[1]);
long long num = rank((long long )n);
printf("%lld\n", num);
return 0;
}
This problem can be thought like this:
1) Any two students, s1 and s2, their relation could be expressed as s1 < s2 (one ranks higher than the other) or s1 = s2 (both ranks the same)
2) So a way of ranking is a permutation that s1 r1 s2 r2 s3 ... rn-1 sn, where si denotes a student and rj denotes the relationship between two adjacent students, and rj could be either '<' or '='.
3) Define f(n) as the number of ways to rank n students. Assume position k is the last position of '<' appears in the permutation above, so k could be 0 to n - 1 (0 means there is no '<' appeared).
4) From the permutation in 2) , you will find there will be k students before relation in position k, and there will be (n - k) students after relation k. define i = n - k, so f(n) = sigma[c(n, i) * f(n - i)] where i in 1...n. c(n, i) means i students are picked from n students and arranged as the students after relation k. f(n - i) means the number of ways to arrange the (n - i) students before relation k.
i dont agree at all Prakash
you have to define more carefully ranking
think of N=2 (people a and b)
either a is first b second or vice versa or they are ranked the same
they cannot be both ranked second so the answer when N=2 is 3 and not 2^2 as you suggested
think about the following recursive formula
let P(n) be the number of possible rankings (the answer in question)
and C(n,k) be the standard combination "n chooses k"
P(n)=sum(k=1 to k=n) C(n,k)P(n-k) with setting up P(0)=1 and obviously P(1)=1 check it out
i say this because it is ranking; you have to set your mind on the way you do it
if N=3 you cant have both 112 and 113 rankings otherwise it would be a really easy question with N^N answer
i define ranking in the following way - which is reasonable
there should be at least one person ranked 1st
if not everyone is ranked first then there should be at least one ranked 2nd
if not everyone is ranked 1st or 2nd there should be at least one ranked 3rd and so on - you get the picture
otherwise think about 5 people and 3 of them ranked 3rd, 2 of them ranked 5th - does not look like a valid ranking to me
how many total possible rankings are for N = 3. I got these lists:
[# rank = 3]
1, 2, 3
1, 3, 2
2, 3, 1
2, 1, 3
3, 1, 2
3, 2, 1
[# rank = 2]
12, 3
13, 2
23, 1
3, 12
2, 13
1, 23
[# rank = 1]
123
So, total # of ranking = 1 + 6 + 6 = 13
I used this formula:
R(n) = Sum ( 1 <= k <=n ) [C(n, k) * (n-k+1)! ]
Using this formula, I get 69 for N = 4 (your recurrence gave me 75, pls correct if I'm wrong). Here's a brief listing of 69 possible rankings. Any feedback is welcomed. Thanks.
[# rank = 4]
1, 2, 3, 4
so on, total rankings = C(4,1) * 4! = 24
[# rank = 3]
1, 2, 34
1, 34, 2
34, 1, 2
2, 1, 34
2, 34, 1
2, 1, 34
so on, total rankings = C(4, 2) * 3! = 6 * 6 = 36
[# rank = 2]
123, 4
124, 3
134, 2
234, 1
1, 234
2, 134
3, 124
4, 123
total rankings = C(4,3)* 2! = 4 * 2 = 8
[# rank = 1]
1234
So, # of rankings = 24 + 36 + 8 + 1 = 69
my bad! I was inclined to avoiding a recurrence, and thought it'd be solvable (wrongly) with direct solution.
Your recurrence gives correct solution. Awesome!
i am a math person not a developer
i myself like closed or direct solutions far better
also i don't say there isn't one - might be complicated
just remember this is from a software interview and they like recurrence a lot
another interesting thing is what happen when N--->oo
I called the answer P(n)
more precisely with the the quotions
P(N)/N^N and N!/P(N) - on first glaze it looks like both tend to zero but it might be deeper
i am too tired to think of it now
i am a math person not a developer
i myself like closed or direct solutions far better
also i don't say there isn't one - might be complicated
just remember this is from a software interview and they like recurrence a lot
another interesting thing is what happen when N--->oo
I called the answer P(n)
more precisely with the the quotions
P(N)/N^N and N!/P(N) - on first glaze it looks like both tend to zero but it might be deeper
i am too tired to think of it now
Let f(N, k) be the number of ways to rank N students where there are k different ranks.
For example, f(3, 2) = 6 as there are 6 ways: 113, 131, 311, 122, 212, 221
We have the trivial cases
Otherwise we consider two cases: when the Nth student is not equal in rank with anyone else and when the Nth student is equal with other students. We get
- crabmilk February 27, 2011