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

Intermediate

Jul 2026

Summary

Amazon OA for a SWE role, one coding problem about string scoring with an optional character swap. Pretty algorithmic, felt like a mid-level screen.

Questions Asked (1)

Given a string, compute a score where each character is worth 1 point and each substring where adjacent characters differ by at most 1 (alphabetically) earns a bonus point. You can change at most one character to maximize the total score. What's the highest score achievable?

Algorithms & Data Structures

Author's notes

The base scoring wasn't hard to wrap my head around but the 'change one character' part is where I fumbled for a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the scoring rules and constraints, then propose an efficient algorithm that computes the base score and evaluates the impact of changing each character. Use a sliding window or dynamic programming to count valid adjacent pairs, and for each position, consider all possible replacement characters to maximize the score.

Pro tip: Demonstrate awareness of edge cases such as single-character strings or when no change improves the score, and discuss time/space complexity trade-offs. Mention that you would test with small inputs and compare against a brute-force solution to validate correctness.

1. Clarify the problem

Restate the scoring: 1 point per character plus 1 bonus point for each adjacent pair where the absolute difference in alphabet positions is at most 1. Confirm that you can change at most one character to any lowercase letter.

2. Compute base score

Calculate the initial score by summing the length of the string and the number of valid adjacent pairs (where |c_i - c_{i+1}| <= 1).

3. Analyze impact of changing one character

For each position i, consider changing s[i] to any letter from 'a' to 'z'. The change affects only the pairs (i-1, i) and (i, i+1). Compute the new score by adjusting the base score: subtract the old contributions of these pairs and add the new contributions.

4. Find maximum score

Track the maximum score over all positions and all possible replacement characters. Also consider the option of not changing any character (i.e., the base score).

5. Optimize and discuss complexity

The naive approach is O(n * 26) which is O(n). Explain that this is optimal since you must consider each position. Discuss potential optimizations like precomputing prefix/suffix scores or using a sliding window, but note that O(n) is already efficient.

Key Points to Mention

Clarify the scoring rules and constraints (e.g., string length, character set).
Compute the base score efficiently by iterating through the string once.
For each position, only the adjacent pairs are affected, so you can update the score in O(1) per candidate character.
Consider all 26 possible replacement characters for each position, but note that only characters close to neighbors matter.
Handle edge cases: empty string, single character, no change needed, change that doesn't improve score.
Discuss time and space complexity: O(n) time and O(1) extra space.

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