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[0] <= 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;
}

- Alex November 10, 2017 | Flag Reply
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.

- Anonymous November 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

k^n - (n-3) * k

- rajr November 09, 2017 | Flag Reply
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[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;
}

- harrypotter0 November 09, 2017 | Flag Reply
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;
}

- mr.robot.fun.society November 09, 2017 | Flag Reply
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...

- Chris November 13, 2017 | Flag Reply


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