Amazon Interview Question
Developer Program EngineersCountry: United States
Interview Type: In-Person
That is just one of the combinations, not all. We need the total number of such combinations possible.
Once you know the optimal solution you know the no of advertisement boards in the optimal solution. Assume there are 'p' advertisements totally in the optimal solution then the problem comes down to finding 'p' slots out of 'n' and checking if that combination is valid. Complexity is O(nCp)
a simple solution is assign 0/1 to every solution and check if all the constraints are satisfied for a given assignment.
backtrack during the assignment process if any condition is violated.
First i proposed brute force method of checking all the combinations (Time Complexity: 2^N) but he asked for a better solution, then i proposed the below solution.
Please note from here on wherever i mean N / M, i actually mean floor value of N / M.
To get the minimum number of boards required we can calculate in greedy method, where we will have to select K boards (all the remaining boards if there are no K boards) after every M - K boards, which gives us as below.
min_boards = (N / M) * K if N % M <= M - K
= (N / M) * K + (N % M - (M - K)) otherwise
There are 4 different cases possible as listed below.
Case 1: N % M = M - K
Here the only arrangement possible is ----XXX----XXX----XXX---- for 25, 7, 3
Since the first M elements should have K selections, you can only arrange K selections among those M elements, the same applies for all successive M elements.
If you have to get a different combination for the last group (15 - 21 elements in the above example) you will have to remove at least one of the selection from the K selections, in which case the last M elements (19 - 25 elements in the above example) will lose a selection in which case minimum K criteria is not satisfied.
The same is the case for all the previous groups as well, therefore no other combination is possible.
Case 2: N % M = 0
We have an algorithm explained further down to analyze this case. Here since we have N / M groups, this is equivalent to T(G, M, K) where G = N / M.
Case 3: N % M > M - K
For example we consider ----XXX----XXX----XXX----X for 26, 7, 3
Since the first M elements should have K selections, you can only arrange K selections among those M elements, the same applies for all successive M elements.
The last M elements have K selections (XX----X in above example), but the first M - N % M (2 in above example) selections actually belong to the N / M group (3rd in above example), but it is not affordable for us to lose these selections as it will not let us satisfy the criteria of minimum K selection for the last M elements.
Similarly the same applies to all the previous groups. Therefore M - N % M selections in every group do not change and therefore there is no point calculating combinations for the same.
We can actually remove these elements and then try for the combinations.
Removing M - N % M elements in every group will make you remain with N % M elements in every group. If you notice carefully now the number of groups has increased by 1. So the new number of groups would be N / M + 1. As we removed M - N % M selections in every group K will now be K - (M - N % M), which is also same as N % M - (M - K).
Therefore this boils down to T(N / M + 1, N % M, N % M - (M - K))
Case 4: N % M < M - K
Let's consider ----XXX----XXX----XXX-- for 23, 7, 3
Since the first M elements should have K selections, you can only arrange K selections among those M elements, the same applies for all successive M elements.
For the last M elements (17 to 23 --XXX-- in above example) we cannot afford to lose these K selections out of these M elements. Therefore the combinations in the last group (15 - 21 elements in the above example) cannot have selections in the first N % M elements.
The same applies to all the earlier groups.
Therefore we could as well get rid of so many elements in every group and also the last N % M elements as we don't get to any selection in these.
Therefore we will end up with M = M - N % M, number of goups G = N / M and K will remain the same.
Therefore this boils down to T(G, M - N % M, K).
Assuming S(N, M, K) is the total number of combinations for N, M, K, based on the above analysis for different N, M, K we get the below relation between S and T.
S(N, M, K) = 1 if N % M = M - K
= T(N / M, M, K) if N % M = 0
= T(N / M + 1, N % M, N % M - (M - K)) if N % M > M - K
= T(N / M, M - N % M, K) if N % M < M - K
Based on the above relation between S and T you will end up needing to calculate T(G, M, K) where G is number of groups, each group containing M elements and N = G * M. This can be calculated as below.
Since N % M = 0, N can be divided into groups of size M each.
Since each group has to have K selected we cannot move the selection to other groups.
Now we get the different combinations for each group separately, selecting K boards out of M. Suppose we generate all the combinations and store in array l[MCK] identifying each combination by its index in the array. We can go for list and use iterator to navigate if M is large as MCK does not fit in the array for M > 33. Time complexity involved here is M * MCK and space complexity is MCK as you can use BitSet for each combination.
But for the contiguous sake we can have only some combinations in group 1 against every combination in group 2, so we can calculate all combinations that can preceed each combination, say we get m[][] where m[i][j] is set if combination j can preceed combination i. We can go for maps if M is large as MCK does not fit in the array for M > 33. This can be achieved in M * MCK * MCK time complexity and MCK space complexity as BitSet can be used for second dimension array.
This applies not just for group 1 and group 2 but for any group x and group x + 1.
Let's say V(G, i) is the total number of combinations where group G can have combination i.
T(G, M, K) = sum of V(G, i) for i from 0 to MCK - 1.
V(G, i) = sum of V(G - 1, j) for all j for which m[i][j] is set.
= 1 if G = 1.
This can be calculated by having an array v[g][i] where g is group index and i is combination index.
Calculate the values from g = 0 for all combinations based on recursive relation.
To save space we could as well have two arrays c[i] and p[i] where c holds values for current group combinations and p holds values for previous group combinations. We can go for maps if M is large as MCK does not fit in the array for M > 33.
This can be achieved in (N / M) * MCK * MCK time complexity and MCK space complexity.
So the total time complexity all three put together is M * MCK + M * MCK * MCK + (N / M) * MCK * MCK and space complexity is MCK.
But i was asked for even more better solution.
Any suggestions are most welcome.
Here is solution in java. Just find the minimum number of boards required first and check for all the combinations. In this case, we check for many combinations (sub problems) again and again. If there is a way to store this result in some DS, we can improve the performance through dynamic programming.
public static int possibleWays(int n, int m, int k) {
/* c -> minimum board required */
int c = n / m * k;
int total = 0;
if (n % m > m - k) c += n % m - (m - k);
int array[] = new int[n];
for (int i = 0; i < n; i++) {
if (i >= n - c) array[i] = 1;
else array[i] = 0;
}
do {
if (validateCombination(array, m, k)) total++;
} while(nextCombination(array));
return total;
}
private static boolean nextCombination(int[] array) {
boolean swapFound = false;
int i, j;
int n = array.length;
for (i = n - 1; i > 0; i--)
if (array[i] == 1 && array[i - 1] == 0) break;
if (i == 0) return false;
for (j = i - 1; j >= 0; j--)
if (array[j] == 0) {
swapFound = true;
break;
}
if (swapFound) {
swap(array, i, j);
/* Sort bit array after swapping */
int k = i;
for (int i1 = i; i1 < n; i1++) {
if (array[i1] < array[k]) {
swap(array, i1, k);
k++;
}
else if (array[i1] > array[k]) {
k++;
}
}
}
return swapFound;
}
private static boolean validateCombination(int[] array, int m, int k) {
int n = array.length;
for (int i = 0; i <= n - m; i++) {
int tempK = k;
for (int j = i; j < i + m; j++)
if (array[j] == 1) tempK--;
if (tempK > 0) return false;
}
return true;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
Here is the DP approach to solve the problem.
First, we need to calculate the minimum number of boards of advertisement needed.
numBoards = (N/M) * K + Math.max(0,(K-(M - N % M)))
Next step is to find recursive solution for sub-problems.
If there are n boards that need t advertisements and m consecutive boards have been skipped,
then
numWays (n,t,m) = numWays(n-1,t-1,0) if m == M-1
= numWays(n-1,t-1,0) + numWays(n-1,t,m+1) if m < M-1
= 1 if k == 0 && n+m < M
= 0 if k == 0 && n+m >= M
Our final result will be numWays (N, numBoards, 0).
There are two ways to subdivide the problem. One to put an advertisement at nth billboard and other is not to put an advertisement on the billboard. If m = M-1 billboards have been skipped, then we cannot skip the current billboard and we have to place an advertisement on current billboard (condition 1). If m < M-1 billboards have been skipped, it is our option whether to put an advertisement on current billboard or not (condition 2).
The terminating condition of 1 means that the current placement is valid. A condition of 0 means the current placement is invalid.
Because of the recursive subproblems, the actual solution is exponential run time, however, if we use DP approach of creating solution bottom-up, our solution will be O(N*numBoards*M).
Here is the java code for a working implementation.
static int numWays (int N, int M, int K) {
int numBoards = (N/M) * K + Math.max(0,(K-(M - N % M)));
int[][][] matrix = new int[N+1][numBoards+1][M];
for(int t = 1; t < numBoards+1; t++) {
for(int m = 0; m < M; m++) {
matrix[0][t][m] = 0;
}
}
for (int n = 0; n < N+1; n++) {
for(int m = 0; m < M; m++) {
if(n+m >= M)
matrix[n][0][m] = 0;
else {
matrix[n][0][m] = 1;
}
}
}
for (int n = 1; n < N+1; n++) {
for(int t = 1; t < numBoards+1; t++) {
for(int m = 0; m < M; m++) {
if(m == M-1) {
matrix[n][t][m] = matrix[n-1][t-1][0];
}
else {
matrix[n][t][m] = matrix[n-1][t-1][0] + matrix[n-1][t][m+1];
}
}
}
}
return matrix[N][numBoards][0];
}
one solution is by doing permutations twice , like doing permutations of length M zeros with K ones and performing outward permutation by considering the whole string and permutating it by considering M length string as single entity.
after observing examples i am thinking that answer should be sum of c(m,k+i)
where i=0,1,2.....until m<=k+i
let me know if i am wrong.
What do you mean until m<=k+i?
That means i>=m-k? Then why did you start i from 0?
I think you actually mean until m = k + i.
Even then it gives 26 for N=15, M=5, K=2 but the answer is 175.
@Naveen, how did you know the answer is 175 for N=15, M=5 and K=2?
For K >1, I think there is only possible way of painting the boards with minimum cost. My reasoning goes as below. Suppose N=8, M=5 and K=2
The only configuration with the minimum number of boards painted and at the same time satisfying the criteria that every M consecutive boards should have at least K boards painted is:
000CC000
In the above configuration, the first M(=5) boards [1..5] have 2 boards painted, the next M boards, [2..6] have 2 boards painted and so on. Any other configuration leads to the number of painted boards to be >2 which is not optimal. The above configuration holds for 5<=N<=8
In general, I think the optimal solution should be such that for the first M boards, K boards need to be painted from M-K+1 to M. These K painted boards should be shared across all M-size window frames till the one that ends at 2M-K and the pattern needs to be repeated.
For N=15, M=5 and K=2, the optimal pattern is: 000CC000CC000CC
Can you find any counterexample to it? Can you find any other optimal pattern with the same or lesser number of boards but with a different permutation?
For K=1, however, there can be several combinations as depicted in your example.
Here is a rough outline for a solution that I *think* should work.I might try to code it out later.
As an example, I'll use a total length of 8, a sequence length of 4 and a required number of boards in each sequence of 2.
Take the length of the sequence of boards and calculate all the permutations that make for the required number. E.g. for the given, we have:
x x 0 0
x 0 x 0
x 0 0 x
0 x x 0
0 x 0 x
0 0 x x
An optimal solution will continuously repeat one of these subsequences. Why? Because they are the minimum subsequences that fit the requirements they are optimal, and each solution when chained together maximizes the space between the x'es to the maximum possible, thus minimizing the number of x'es that need to be placed.
So the number of possible sequences is the number of permutations of the sequence length (2^sequence_length).
However, this isn't quite good enough because we might have a remainder, so then we just need to calculate the number of combinations for the remainder (in conjunction with each pattern) that are acceptable solutions and add those together, then multiply the whole thing by two since we could take the remainder from the front or from the back.
you see the problem ......you are considering only number of boards equal to k.but it can be greater than k as well.so number of case will be greater for your given case of n=8,m=4,k=2
think about my solution which i have given above.if i am wrong correct me.
What is sequence_length by the way? Is it N/M? How did you come to the conclusion of 2^sequence_length? Not every 2 combinations can be beside each other, consider for example xx00 and 00xx, if we take them both together we are left with 4 zeros in between without any x which is violating the requirement of minimum K. Similarly it is not necessary that you take the same combination beside each other, consider for example 0xx0 and x0x0, if we take them both together it is a valid solution, also you notice that 2nd position to 5th position there are 3 x.
Total=N
M banners should have atleast K consecutive banners.
We can solve this in 2 steps:
1. First assigning K blocks consecutively from end in a M window size.
2.Then running a loop which assigns an ad as we move on from index N-M to N.
The pseudo code is like:
for(j=0;j<k;j++)
{
arr[N-M+j]='C'
}
for (j=M;j<N;j++)
{
a[j]='C'
}
1st loop puts K banners from last in a M size banner block and second for loop keep on putting one banner each from Mth position to N.
int factorial(int num)
{ int fact=1;
for( int i=1;i<=num;i++){fact = fact*i;}
return fact;
}
int findpossibleadvertisements(int n,int m,int k)
{
int start = m;
int end = m+k;
int adcount =0;
while(end!=n)
{
adcount = acdount + (factorial(m)/(factorial(k)*factorial(m-k));
start++;end++;
}
return adcount;
}
What is start variable doing in your program by the way?
Your program tells that you are adding mCk n-m-k times, even then your program is not efficient, you could have multiplied mCk with (n-m-k) to get the answer instead of having loop.
Most importantly how do you prove this is right?
Your program runs into infinite loop for 5, 5, 1, even if you correct your infinite loop by changing end != n to end < n it would return 0, but the answer is 5.
int factorial(int num)
{ int fact=1;
for( int i=1;i<=num;i++){fact = fact*i;}
return fact;
}
int findpossibleadvertisements(int n,int m,int k)
{
int start = m;
int end = m+k;
int adcount =0;
while(end!=n)
{
adcount = acdount + (factorial(m)/(factorial(k)*factorial(m-k));
start++;end++;
}
retuen adcount;
}
What is start variable doing in your program by the way?
Your program tells that you are adding mCk n-m-k times, even then your program is not efficient, you could have multiplied mCk with (n-m-k) to get the answer instead of having loop.
Most importantly how do you prove this is right?
Your program runs into infinite loop for 5, 5, 1, even if you correct your infinite loop by changing end != n to end < n it would return 0, but the answer is 5.
You can also use greedy approach. Try to assign k consecutive ad boards to the rightmost position of the current window of size M. This should give the optimal result.
- Anonymous May 25, 2013