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 Onsite rounds at Google.

What role is this question designed for?

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

Maximize coins collected by 3-step pieces

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a 1D board of length **N**. Each cell is in one of three states: - **Empty** - **Piece** (a movable token) - **Coin** (collectible) In one move, you may choose **any one piece** and move it **exactly 3 cells to the right** (from index `i` to `i+3`). The move rules are: 1. If the destination cell is **empty**, the piece moves there. 2. If the destination cell contains a **coin**, the piece moves there and you **collect** that coin (the coin is removed). 3. Pieces **cannot overlap**: a move is **not allowed** if the destination cell already contains another piece. 4. The piece may “jump over” intervening cells; only the destination cell matters. 5. A move is not allowed if `i+3` is outside the board. You may perform moves in any order, for as many turns as you like, until **no piece can legally move**. Return the **maximum number of coins** you can collect. ### Input - A representation of the board (e.g., a string/array of length `N`) containing exactly one of `{empty, piece, coin}` per cell. ### Output - An integer: the maximum number of coins collectible. ### Notes / Clarifications - Multiple pieces may exist. - Coins are collected at most once (they disappear after collection). - The result depends on the order in which you choose moves.

Quick Answer: This question evaluates modeling and optimization of discrete state-space transitions under movement constraints, testing combinatorial reasoning, reachability, and resource-maximization competencies.

You are given a 1D board of length N, represented as a string where each character is one of: '.' (empty cell), 'P' (a movable piece), or 'C' (a collectible coin). In one move you may pick any one piece at index i and move it exactly 3 cells to the right (to i+3). The rules: 1. The move is only legal if i+3 < N (cannot move off the board). 2. If the destination cell is empty, the piece moves there. 3. If the destination cell holds a coin, the piece moves there and that coin is collected (removed from the board). 4. Pieces cannot overlap: a move is illegal if i+3 already holds another piece. 5. A piece jumps over intervening cells; only the destination cell matters. You may perform moves in any order, for as many turns as you like, until no piece can legally move. Return the maximum number of coins you can collect. Key observation: a move of +3 keeps every piece inside its own residue class mod 3, so the board splits into three independent sub-lines. Within each sub-line (where a move becomes one step right), pieces keep their relative order, so the j-th of k pieces can advance to at most position m-1-(k-1-j); a coin is collectible exactly when some piece can sweep over it.

Constraints

1 <= N <= 10^5 (board length)
Each board character is one of '.', 'P', or 'C'.
0 or more pieces and 0 or more coins may be present.
A piece moves only to the right, exactly 3 cells per move.
Each coin is collected at most once.

Examples

Input: ('P..C',)

Expected Output: 1

Explanation: Piece at 0 moves +3 onto the coin at 3 and collects it.

Input: ('P..C..C',)

Expected Output: 2

Explanation: Piece sweeps 0->3 (coin) then 3->6 (coin); both coins lie 3 apart so both are collected.

Input: ('PC..C',)

Expected Output: 0

Explanation: Coin at 1 is in a different residue class than the piece, and coin at 4 is unreachable from index 0 in steps of 3 (lands on 3, then 6 is out of bounds) -> 0.

Input: ('P.C',)

Expected Output: 0

Explanation: The only possible move 0->3 is out of bounds (N=3); the coin at 2 is never reachable -> 0.

Input: ('CCCC',)

Expected Output: 0

Explanation: No pieces on the board, so no coins can be collected -> 0.

Input: ('',)

Expected Output: 0

Explanation: Empty board -> 0 coins.

Input: ('PPP...CCC',)

Expected Output: 3

Explanation: Three pieces at 0,1,2 each move +3 onto the aligned coin at 6,7,8 (matching residue classes) -> 3.

Input: ('P..P..C..C',)

Expected Output: 2

Explanation: Two pieces share residue class 0; the front piece collects the near coin and the back piece the far coin -> 2.

Input: ('C..P..C',)

Expected Output: 1

Explanation: Coin at 0 sits behind the only piece (pieces move right only, so it is unreachable); the coin at 6 is collected -> 1.

Input: ('.P..C..C..P..C',)

Expected Output: 3

Explanation: Residue-1 line is P,C,C,P,C with two pieces: they can sweep three of these coins; the back piece is boxed in behind the front one, leaving one coin uncollected -> 3.

Hints

A move always changes an index by +3, so a piece can only ever visit cells sharing its index's value mod 3. The three residue classes never interact - solve each independently and sum the results.
Compress one residue class into consecutive slots; a move becomes a single step to the right. Pieces preserve their order because they only move right and cannot overlap.
In a compressed line of length m with k pieces, the j-th piece (0-indexed from the left) can be pushed as far as slot m-1-(k-1-j) once the pieces to its right vacate the end. A coin is collectible iff some piece's start <= coin <= that piece's max reach.

Quick Overview

This question evaluates modeling and optimization of discrete state-space transitions under movement constraints, testing combinatorial reasoning, reachability, and resource-maximization competencies.