## Interview Question

Country: United States
Interview Type: Written Test

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

Just compute the coefficient by doing 1* (N/1) * (N-1)/2 * (N-2)/3 *...

At each step, the answer will be an integer and no rounding etc will happen.

``````long capped_binomial(uint n, uint k) {

long answer = 1;
long r = 0;
while (r < k) {
// there might be overflow issues here. Consider those too.
// Just the check against 1 billion might not be sufficient.
answer = answer*(N-r)/(r+1);
if (answer > 1000000000) return -1;
r++;
}

}``````

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

return answer is missing!

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

Calling comment out explicitly:

You need to check for overflow issues.

Just the check against 1 billion might not be sufficient.

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

For "n = 1000000000" and "r = 2" you get
r = 0 => answer = 1000000000 (no over flow)
r = 1 = > answer = -743309312 which is an overflow but undetected.
Overall this is a very good approach since you are doing one product and one division in each iteration and naturally, it covers almost all supported pairs of values.

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

``````#include <iostream>
using namespace std;

int memoarr[50][50];

int binomial(int n, int k)
{
if (k == 0) {
memoarr[n][0] = 1;
return 1;
} else if (n == k) {
memoarr[n][k] = 1;
return 1;
} else if (memoarr[n][k] > 0) {
return memoarr[n][k];
} else {
int lhs = binomial(n-1, k-1), rhs = binomial(n-1, k);
if (lhs == -1 || rhs == -1)
return -1;
memoarr[n][k] = lhs + rhs;
if (memoarr[n][k] > 1000000000) {
return -1;
}
}
return memoarr[n][k];
}

int main(int args, char **argv)
{
cout << binomial(10,6) << endl;
}``````

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

This is very inefficient and uses a lot of memory.

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

Alternate way is to just compute multiplication of n * (n-1) * (n-2).... (n - max(n-k, k) +1), and factorial of (min(n-k, k))! and do the division of numerator and denimonator. I was not sure which one was expected to be the solution.
Since they allow some space complexity which was in terms of N*K, I assume that what I have posted is right.
Additionally since their constraint is that if "n choose k" is > 1 billion, return -1, they anyways don't expect memoization array to be greater than 40 x 40.

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

Computing factorials is inefficient too, and has potential overflow issues.

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

In O(k) space and O(k^2) time (k^2 = O(n * min(k, n - k)).
Assume k < n /.2, i.e., min(k, n - k) == k is true

The goal is to do the integer division first to make sure we can have the largest possible numbers without throwing an overflow.

``````public int nChoosek(int n, k) {
// Do division first
// We are evaluating N * (N - 1) * ... * (N - k + 1) / (k * (k - 1) * .... * 1).
// Numerator values (N, N - 1, ...)
int[] C = new int[k];
for (int i = 0; i < k; i++)
C[i] = N - i;
for (int i = 0; i < k; i++) {
// i + 1 is a denumerator value, i.e., i + 1 = 1, 2, ..., k
for (int j = 0; j < k; j++) {
// Find an element from numerator which divides (i + 1)
if (C[j] % (i + 1) == 0) {
C[j] = C[j] / (i + 1);
break;
}
}
}

// Now do product
int result = 1;
for (int i = 0; i < k; i++) {
if (i < (k - 1)) {
if (result > (1000000 / C[i + 1]))
return -1;  // This would be an overflow anyway
}
result *= C[i];
}
return result;
}``````

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

Best way is to use recursion and memo calls

``````f(n,k) = f(n-1, k) + f(n-1, k-1)
f(0, x) = 0``````

CV: spoj.com/SPOJ/users/mogers/

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

Good formula, but this takes exponential time unless you store values on a table, i.e., dynamic programming. And more boundary conditions are needed, like : f(n, 0) = 1.

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

@Anonymous, Miguel said memo the calls so it is linear not exponential.

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