How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Google during technical interviews.

Minimize Fence Painting Operations | Google Coding Question

Minimize Fence Painting Operations

Company: Google

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a fence made of `n` adjacent vertical boards. Each board has width `1`, and the height of the `i`-th board is `a[i]`. You have a brush of width `1`. In one operation, you may do exactly one of the following: 1. **Vertical stroke:** Paint one entire board from bottom to top. 2. **Horizontal stroke:** Paint one unit-height horizontal segment across a contiguous interval of boards. The stroke must stay on boards that exist at that height. Repainting an already painted area is allowed but unnecessary. Return the minimum number of operations required to paint the entire fence. **Input:** - An integer `n` - An array `a[1..n]` of non-negative integers representing board heights **Output:** - The minimum number of painting operations **Example:** Input: ```text a = [2, 2, 1, 2, 1] ``` Output: ```text 3 ``` Explanation: One optimal strategy is to paint height level `1` horizontally across all five boards, then paint height level `2` horizontally across boards `1..2`, and finally paint height level `2` on board `4`. Total: `3` operations.

Quick Answer: This question evaluates algorithmic problem-solving and optimization skills, focusing on minimizing painting operations on an array-modeled fence and reasoning about intervals, heights, and operation counts.

You are given a fence made of adjacent vertical boards. The i-th board has width 1 and non-negative height a[i]. A brush of width 1 can be used in one operation in exactly one of two ways: paint one entire board vertically from bottom to top, or paint one unit-height horizontal segment across a contiguous interval of boards where all boards exist at that height. Repainting is allowed but never helpful. Return the minimum number of operations needed to paint the entire fence.

Constraints

0 <= len(a) <= 5000
0 <= a[i] <= 10^9
Each board has width exactly 1

Examples

Input: ([2, 2, 1, 2, 1],)

Expected Output: 3

Explanation: Paint height 1 across all boards, then height 2 across boards 0..1, then height 2 on board 3.

Input: ([],)

Expected Output: 0

Explanation: There are no boards, so no operations are needed.

Input: ([0, 0, 0],)

Expected Output: 0

Explanation: All boards have height 0, so the fence is already fully painted.

Input: ([5],)

Expected Output: 1

Explanation: A single vertical stroke paints the entire board, which is better than 5 horizontal strokes.

Input: ([1, 2, 3, 2, 1],)

Expected Output: 3

Explanation: Use one horizontal stroke at height 1 across all boards, one at height 2 across the middle three boards, and one at height 3 on the center board.

Input: ([5, 5, 5],)

Expected Output: 3

Explanation: Painting the three boards vertically takes 3 operations, which is better than 5 horizontal strokes.

Input: ([1, 0, 1],)

Expected Output: 2

Explanation: The middle board has height 0, so the two height-1 boards cannot be covered by one horizontal stroke. Paint each positive board separately.

Input: ([3, 1, 2, 3, 1],)

Expected Output: 4

Explanation: One horizontal stroke covers height 1 across all boards. Then paint board 0 vertically and solve boards 2..3 in 2 more operations, for a total of 4.

Hints

For any contiguous interval, compare two choices: paint every board in that interval vertically, or paint horizontally up to the minimum height in the interval and then solve the remaining taller sub-intervals.
After painting horizontal layers up to the interval's minimum height, boards equal to that minimum split the problem into independent smaller intervals.

Quick Overview

This question evaluates algorithmic problem-solving and optimization skills, focusing on minimizing painting operations on an array-modeled fence and reasoning about intervals, heights, and operation counts.