Adobe Interview Question
abcsCountry: United States
Define the solution recursively. Think about a base case, if N < 4, we can paint the N posts with the K colors with no restriction at all, that's K^N ways.
If N >= 4 it gets interesting, we can paint the first 3 posts in K^3 different ways, and for each triplet (c1, c2, c3) out of the K^3 possibilities, sum together g(N - 3, K, c1, c2, c3). Where g function is recursively defined as:
g(N, K, c1, c2, c3) = 1, if N = 0
sum of (g(N - 1, K, c2, c3, i) or 0 if c1 = c2 = c3 and i = c1) for every natural i between 1 and K. Otherwise
Then f becomes:
f(N, K) = N^K if N < 4.
Sum of g(N - 3, K, c1, c2, c3) for every triplet (c1, c2, c3) where c1, c2, c3 are natural numbers between 1 and K. Otherwise
Below is implementation in JavaScript.
function g(N, K, c1, c2, c3, expanded){
if (N === 0){
console.log(expanded.join());
return 1;
}
else {
let sum = 0;
for (let i = 1; i <= K; i++){
// Equivalent to !(c1 === c2 && c2 === c3 && i === c1)
// De-Morgan's theorem
if (c1 !== c2 || c2 !== c3 || i !== c1){
sum += g(N - 1, K, c2, c3, i, expanded.concat(i));
}
}
return sum;
}
}
function f(N, K){
if (N < 4){
return Math.pow(K, N);
}
else {
let sum = 0;
for (let c1 = 1; c1 <= K; c1++){
for (let c2 = 1; c2 <= K; c2++){
for (let c3 = 1; c3 <= K; c3++){
console.log(`Triplet (${c1}, ${c2}, ${c3})`);
sum += g(N - 3, K, c1, c2, c3, [c1, c2, c3]);
}
}
}
return sum;
}
}
// 16, that is K^N = 4^2
console.log(f(2, 4));
// 1944, and prints the solutions as well
console.log(f(7, 3));
Looking at the code it can be seen that we could speed things up thanks to Dynamic Programming.
function g(N, K, c1, c2, c3, DP){
const state = `${N}-${c1}-${c2}-${c3}`;
if (!DP.has(state)){
if (N === 0){
DP.set(state, 1);
}
else {
let sum = 0;
for (let i = 1; i <= K; i++){
// Equivalent to !(c1 === c2 && c2 === c3 && i === c1)
// De-Morgan's theorem
if (c1 !== c2 || c2 !== c3 || i !== c1){
sum += g(N - 1, K, c2, c3, i, DP);
}
}
DP.set(state, sum);
}
}
return DP.get(state);
}
function f(N, K){
if (N < 4){
return Math.pow(K, N);
}
else {
let sum = 0;
for (let c1 = 1; c1 <= K; c1++){
for (let c2 = 1; c2 <= K; c2++){
for (let c3 = 1; c3 <= K; c3++){
sum += g(N - 3, K, c1, c2, c3, new Map());
}
}
}
return sum;
}
}
// 16, that is K^N = 4^2
console.log(f(2, 4));
// 1944, and prints the solutions as well
console.log(f(7, 3));
Complexity of that last one is O(N * K^6) in time and O(N * K^3) additional space. However, there should be a better solution using combinatorics but I was lazy to try it out.
/*
Input : n = 2 k = 4
Output : 16
We have 4 colors and 2 posts.
Ways when both posts have same color : 4
Ways when both posts have diff color :
4*(choices for 1st post) * 3(choices for
2nd post) = 12
Input : n = 3 k = 2
Output : 6
*/
#include<bits/stdc++.h>
using namespace std;
// Returns count of ways to color k posts
// using k colors
long countWays(int n, int k)
{
// To store results for subproblems
long dp[n + 1];
memset(dp, 0, sizeof(dp));
// There are k ways to color first post
dp[1] = k;
// There are 0 ways for single post to
// violate (same color_ and k ways to
// not violate (different color)
int same = 0, diff = k;
// Fill for 2 posts onwards
for (int i = 2; i <= n; i++)
{
// Current same is same as previous diff
same = diff;
// We always have k-1 choices for next post
diff = dp[i-1] * (k-1);
// Total choices till i.
dp[i] = (same + diff);
}
return dp[n];
}
// Driver code
int main()
{
int n = 3, k = 2;
cout << countWays(n, k) << endl;
return 0;
}
Simple BruteForce using Backtracking.
+ This is not an optimal solution, but very intuitive to reach during interview.
+ Pick one color at a time ( loop over K value ) and recurse for next one.
+ If last 3 colors were the same as this color, dont pick this color and continue.
+ when we reach n colors, count that solution as 1 valid result.
int helper( int n, int k, vector<int>& result )
{
int size = result.size();
if( size == n )
{
return 1;
}
int count = 0;
for( int i=0; i<k; ++i )
{
if( size >=3 && result[size-1] == i
&& result[size-2] == i
&& result[size-3] == i )
{
continue;
}
result.push_back( i );
count += helper(n,k, result);
result.pop_back();
}
return count;
}
void getCount(int n, int k )
{
vector<int> result;
int count = helper(n,k, result);
cout << " Count is " << count;
}
As far as I understood it, we should paint N posts using K colors so, that after painting, looking at any group of 4 consecutive posts, we see 4 different colors. And we should count how many ways are there to satisfy the rule.
In this case, number of ways can be found using the following formula:
K * (K - 1) * (K - 2) * (K - 3)^(N - 3)
The code below proves the formula by comparing with brute force.
- Alex November 10, 2017