Katkat
Back

Compute max coins with 3-step token moves

GoogleSoftware Engineer · Online Assessment
EasySoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This question evaluates combinatorial optimization, state-space reasoning, and algorithmic design for constrained token movements on a linear board, and falls under the Coding & Algorithms domain.

You are given a one-dimensional board with n positions represented by a string s of length n:

  • . = empty cell
  • T = token
  • C = coin

You may move tokens any number of times under these rules:

  1. A move selects one token and moves it exactly 3 positions to the right (from index i to i+3).
  2. A token cannot move if i+3 is outside the board.
  3. A token cannot land on a cell currently occupied by another token (T).
  4. If a token lands on a coin (C), that coin is collected (removed) and cannot be collected again.

Your task is to compute the maximum number of coins that can be collected by choosing an optimal sequence of moves.

Input: s (string of length n, consisting only of ., T, C)

Output: An integer = maximum coins collectible.

Notes / clarifications:

  • Tokens can be moved in any order.
  • A token may move multiple times.
  • Coins are only collected when a token lands on them (not when jumping over them).