← Google Interview Insights

Google·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate
May 2026

Summary

Google SWE coding problem involving string manipulation and greedy movement logic. Pretty niche problem type, not your typical graph or DP warmup.

Questions Asked (1)

Q1

Given a string of 'T' and 'C' characters, a 'T' can move up to three positions to the right but cannot jump over another 'T'. Any 'C' characters it passes through are collected. Find the maximum number of 'C's that can be collected.

Algorithms & Data Structures
Author's notes

Took me a bit to realize this isn't just a greedy scan.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then propose a greedy or dynamic programming approach. For each 'T', consider moving it right by 1 to 3 positions, ensuring it doesn't jump over another 'T', and collect any 'C's passed. Use DP to maximize total collected 'C's, or a greedy strategy if optimal.

Pro tip: Discuss the trade-offs between greedy and DP, and mention that a greedy approach might work if you always move the rightmost 'T' first, but verify with counterexamples. Also, consider that moving a 'T' may block others, so order matters.

1. Understand the problem

Restate the problem: Given a string of 'T' and 'C', each 'T' can move right up to 3 positions without jumping over another 'T', collecting 'C's it passes. Goal: maximize total 'C's collected.

2. Identify constraints and edge cases

Consider cases with no 'T's, no 'C's, adjacent 'T's, and 'T's at the end. Note that moving a 'T' changes the positions of 'C's and may affect other 'T's moves.

3. Choose an approach

Evaluate greedy vs. dynamic programming. Greedy: process 'T's from right to left, moving each as far right as possible without crossing another 'T', collecting 'C's. DP: define state based on positions of 'T's and 'C's, but may be complex due to interactions.

4. Validate with examples

Test the chosen approach on small examples, such as 'TCC', 'TCT', 'TTCC', to see if greedy works or if DP is needed. Look for counterexamples where greedy fails.

5. Analyze complexity and optimize

If greedy works, it can be O(n) by scanning from right to left. If DP, define states and transitions, aiming for O(n) or O(n^2) time. Discuss potential optimizations.

Key Points to Mention

  • Clarify that 'T' cannot jump over another 'T', so relative order of 'T's is preserved.
  • Moving a 'T' collects all 'C's it passes over, but those 'C's are then removed from the string.
  • Greedy strategy: process 'T's from right to left, moving each as far right as possible without crossing the next 'T', collecting 'C's.
  • Potential counterexample to greedy: 'TCT' where moving the first 'T' right collects a 'C' but blocks the second 'T' from collecting more.
  • Dynamic programming state could be the index of the current 'T' and the number of 'C's collected so far, but interactions make it tricky.
  • Time complexity: O(n) for greedy, O(n^2) for naive DP; space complexity O(n) for DP.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.