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 role is this question designed for?

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

Maximize coins collected by tokens jumping +3

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Interview Round: Take-home Project

You are given a single-player board game represented by a string `board` of length `N` (1 ≤ N ≤ 100). Each character is one of: - `'.'`: empty cell - `'T'`: a player token (there may be multiple tokens) - `'C'`: a coin A move consists of selecting one token and moving it **exactly 3 positions to the right** (from index `i` to `i+3`). The token does not interact with intermediate cells. Rules: - A move is only allowed if `i+3 < N`. - A move is **not** allowed if the destination cell currently contains another token (`'T'`). - If a token lands on a cell containing a coin (`'C'`), that coin is collected and removed (each coin can be collected at most once). - Tokens can be moved multiple times. Task: Return the **maximum number of coins** that can be collected. Function signature: ```python def solution(board: str) -> int: ... ``` Examples: - `board = "TT.T.CCCCC"` → `3` - `board = "T...CCCC"` → `1` - `board = "C..TT.CT.C"` → `2`

Quick Answer: Evaluates algorithmic reasoning about constrained discrete moves and optimization, focusing on state-space modeling, reachability under move constraints, and resource-maximization techniques.

You are given a single-player board game represented by a string `board` of length `N`. Each character is one of: - `'.'`: empty cell - `'T'`: a player token - `'C'`: a coin A move consists of selecting one token at index `i` and moving it exactly 3 positions to the right, from `i` to `i + 3`. Rules: - A move is only allowed if `i + 3 < N`. - A move is not allowed if the destination cell currently contains another token (`'T'`). - The token does not interact with the two intermediate cells. - If a token lands on a cell containing a coin (`'C'`), that coin is collected and removed. - Tokens may be moved multiple times. Return the maximum number of coins that can be collected.

Constraints

1 <= len(board) <= 100
Each character of `board` is one of '.', 'T', or 'C'

Examples

Input: "TT.T.CCCCC"

Expected Output: 3

Explanation: Split by indices modulo 3. Coins at indices 6, 7, and 9 each have a token earlier in the same lane, so they can be collected. Coins at 5 and 8 cannot.

Input: "T...CCCC"

Expected Output: 1

Explanation: Only the coin at index 6 is in the same modulo-3 lane as the token at index 0. The other coins are unreachable.

Input: "C..TT.CT.C"

Expected Output: 2

Explanation: The collectable coins are at indices 6 and 9. They share a lane with the token at index 3. No other coin has a token before it in the same lane.

Input: "CCCC"

Expected Output: 0

Explanation: There are no tokens, so no coin can be collected.

Input: "T"

Expected Output: 0

Explanation: A single token with no space to move and no coins to collect.

Input: "TCTCTC"

Expected Output: 2

Explanation: The coins at indices 3 and 5 are in lanes that already have tokens before them. The coin at index 1 is not collectable because there is no earlier token in its lane.

Input: "CCTCCTTCCC"

Expected Output: 2

Explanation: Only the coins at indices 8 and 9 have a token earlier in the same modulo-3 lane. All other coins are before the first token in their lane or in a lane with no token.

Hints

A token that starts at index `i` can only ever visit positions with the same value of `index % 3`.
For each modulo-3 lane, think about which coins are impossible to reach and which ones will definitely be visited once there is at least one token before them.

Quick Overview

Evaluates algorithmic reasoning about constrained discrete moves and optimization, focusing on state-space modeling, reachability under move constraints, and resource-maximization techniques.