Microsoft | Onsite | Coloring Grid

Anonymous User

3743

I had this question during an onsite interview for a senior dev position. Its an interesting question also appears to be a hard one, I couldnt find similar question anywhere online so it might worth sharing.
Interviewer gave me half hour to finish the question including reading time. The question was quite long, I will do my best to remember/describe it.

Question:

Given a map (2D vector<vector> m) with K different colors in each position, represented by int 1~K.
Adjacent cells with same color are considered to be a single isle.
Each time we can print one isle to any color that we like
Return minimal times of printing the map that can make it same color.

int coloringMap(vector<vector<int>>& matrix, int K) {...}

Example 1:

Input:
111111
112211
111111

Output: 1
Explanation: either change 2s to 1 or change all 1s to 2.

Example 2:

Input:
1111111111
1122112211
1111111111

Output: 1
Explanation: change all 1s to 2 can make it same color

Example 3:

Input:
1111111111
1122332211
1111111111

Output: 2
Explanation:
1111111111 -> 1111111111 -> 1111111111
1122332211 -> 1122222211 -> 1111111111
1111111111 -> 1111111111 -> 1111111111
print 3s
print 2s
done

for above example we cannot print 2s because it would take 3 steps.
1111111111 -> 1111111111 -> 1111111111 -> 1111111111
1122332211 -> 1133332211 -> 1133333311 -> 1111111111
1111111111 -> 1111111111 -> 1111111111 -> 1111111111

Clarification

for following input, we can only print 1s to 2, so we will have matrix with all 2s
we cant print 2s to 1 because there are two isles with 2s but they are not adjacent, we can print only one isle each time.

Input:
1111111111
1122112211
1111111111

Output: 1

Ideas about how to solve this problem

I failed to finish the question on time, after I got home I came up with a greedy algorithm, not sure if this is the best solution.
I found int K is totally useless, not sure why did interviewer give me K in function prototype

Let's narrow down the question, think about a 1D vector, suppose we have following map
111222333222111

Adjacent cells with same color can be merged, so we have
12321

no matter how we print it, we can make 3 middle cells to be same color
12221 (or 13331)

then cells can be merged again, we have
121

so we only need to consider two situations
123 or 121

in another word, we only need to consider a cell with different adjacent colors, or with same adjacent color.
for case 123, it doesnt matter which color we print first, it always takes 2 steps to get the job done.
for case 121 we need to print middle cell 2 to 1 then its done.

Here we can draw our conclusion, apply greedy algorithm, find the isle with most same color adjacent isles, print it to that color. keep doing this process till map contains only one color.

Comments (8)