## Adobe Interview Question for abcs

Country: United States

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

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.

``````#include <iostream>
#include <vector>

using namespace std;

bool Valid(vector<int> const &comb)
{
for (int i = 0; i < comb.size(); ++i) {
for (int j = 1; j <= 3; ++j) {
if (i >= j &&
comb[i - j] == comb[i])
{
return false;
}
}
}
return true;
}

uint64_t BruteForce(int n, int k)
{
vector<int> comb;
comb.resize(n, 1);
uint64_t count = 0;
do {
if (Valid(comb)) {
++count;
}
for (int i = comb.size() - 1; i >= 0; --i) {
if (++comb[i] <= k) {
break;
}
if (i != 0) {
comb[i] = 1;
}
}
} while (comb <= k);

return count;
}

uint64_t Formula(int n, int k)
{
uint64_t count = k;
if (n > 1) {
count *= (k - 1);
if (n > 2) {
count *= (k - 2);
}
}
for (int i = 0; i < n - 3; ++i) {
count *= k - 3;
}
return count;
}

int main()
{
for (int n = 1; n <= 9; ++n) {
for (int k = 1; k <= 9; ++k) {
uint64_t count1 = BruteForce(n, k);
uint64_t count2 = Formula(n, k);
cout << n << ", " << k << ", " << count1 << ", " << count2 << "\n";
if (count1 != count2) {
cerr << "error\n";
exit(-1);
}
}
}
return 0;
}``````

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

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.

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

k^n - (n-3) * k

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

``````/*
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 = 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;
}``````

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

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;
}``````

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

@Alex: thanks for the proof, I came to the same closed formula...

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