Maximize coins with tokens moving by +3

Q: Maximize coins with tokens moving by +3

This question evaluates proficiency in discrete optimization and state-space reasoning, emphasizing movement constraints, collision avoidance, modular-position effects from fixed-step moves (+3), and maximizing reward collection.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Google.

Q: What role is this question designed for?

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

Question

You are given a 1D board represented by a string s of length n (1 <= n <= 100). Each character is one of:

'.' : empty cell
'C' : a cell containing one coin
'T' : a cell containing a token (there may be multiple tokens)

Movement rules:

Each token may be moved any number of times.
A move for a token is exactly 3 cells to the right: from index i to index i + 3 .
Moves to the left or by any other distance are not allowed.
A move is invalid if the destination cell is currently occupied by another token.
Coins:
- If a token lands on a cell containing a coin, the coin is collected.
- Each coin can be collected at most once total (after it is collected, it disappears).
- Coins that a token “jumps over” during a move are not collected (only the destination cell matters).

Task: Compute the maximum number of coins the player can collect by choosing an optimal sequence of token moves.

Output: an integer, the maximum collectible coins.

Notes/clarifications:

Tokens are considered distinct only in that they cannot occupy the same cell at the same time.
You may assume all input tokens/coins are initially placed according to s .
Tokens never leave the board; moves that would go past the end are not allowed.

Maximize coins with tokens moving by +3

Quick Overview

Comments (0)