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...

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.

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.