Caesar Cipher with Translation-Table Optimization
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a **Caesar cipher**. Given a string `text` and an integer `shift`, return a new string in which every alphabetic character is rotated forward by `shift` positions within its own case, wrapping around the alphabet; all non-alphabetic characters are left unchanged.
Rules:
- An **uppercase** letter stays uppercase: it rotates within `A`–`Z` and wraps (so `'Z'` shifted by `1` becomes `'A'`).
- A **lowercase** letter stays lowercase: it rotates within `a`–`z` and wraps (so `'z'` shifted by `1` becomes `'a'`).
- **Non-letters** (digits, spaces, punctuation, symbols) are copied through unchanged.
- Letter case is preserved.
### Constraints
- `0 <= text.length <= 10^6` (the input may be very long — up to thousands of characters or more).
- `shift` is an integer; it may be `0`, negative, or larger than `26`, so reduce it modulo `26` (handling negative values so the result stays in `[0, 26)`).
- The string contains only printable ASCII characters.
### Input / Output
- **Input:** a string `text` and an integer `shift`.
- **Output:** the ciphered string.
### Examples
**Example 1**
```
text = "Hello, World!"
shift = 3
Output: "Khoor, Zruog!"
```
**Example 2**
```
text = "abcXYZ"
shift = 2
Output: "cdeZAB"
```
**Example 3**
```
text = "Shift me 5!"
shift = 0
Output: "Shift me 5!"
```
---
### Follow-up — Avoid redundant per-character work
For a very long string (thousands of characters or more), computing a `% 26` for every single character is wasteful: a given letter `F` always maps to the same output letter, so re-deriving that mapping on every occurrence repeats work. The alphabet has only **26 letters**. Show how to optimize so the per-character cost is a cheap lookup rather than a modulo each time — e.g. **precompute a translation table** (a 26-entry map per case, or a 256-entry byte lookup table) once, then map each character through the table in a single pass.
Quick Answer: This question tests practical string manipulation and modular arithmetic by requiring implementation of a classic Caesar cipher with correct case-preserving wraparound logic. It also evaluates algorithmic optimization skills, specifically the ability to recognize repeated computation and replace per-character modulo operations with a precomputed translation table for large inputs.
Implement a **Caesar cipher**. Given a string `text` and an integer `shift`, return a new string in which every alphabetic character is rotated forward by `shift` positions within its own case, wrapping around the alphabet; all non-alphabetic characters are left unchanged.
**Rules**
- An **uppercase** letter stays uppercase: it rotates within `A`–`Z` and wraps (so `'Z'` shifted by `1` becomes `'A'`).
- A **lowercase** letter stays lowercase: it rotates within `a`–`z` and wraps (so `'z'` shifted by `1` becomes `'a'`).
- **Non-letters** (digits, spaces, punctuation, symbols) are copied through unchanged.
- Letter case is preserved.
`shift` may be `0`, negative, or larger than `26`, so reduce it modulo `26` (handling negative values so the effective shift stays in `[0, 26)`).
**Follow-up — avoid redundant per-character work.** For a very long string, computing `% 26` for every character repeats work: a given letter always maps to the same output letter, and the alphabet has only 26 letters. Precompute a translation table once (a 26-entry map per case, or a 256-entry byte lookup table), then map each character through the table in a single pass so the per-character cost is a cheap lookup instead of a modulo.
Constraints
- 0 <= text.length <= 10^6
- shift is an integer; it may be 0, negative, or larger than 26 — reduce it modulo 26 so the effective shift is in [0, 26).
- text contains only printable ASCII characters.
- Case is preserved; non-letters pass through unchanged.
Examples
Input: ("Hello, World!", 3)
Expected Output: "Khoor, Zruog!"
Explanation: Each letter shifts forward by 3 within its case; the comma, space, and '!' are unchanged. H->K, e->h, l->o, o->r; W->Z, o->r, r->u, l->o, d->g.
Input: ("abcXYZ", 2)
Expected Output: "cdeZAB"
Explanation: a->c, b->d, c->e in lowercase; X->Z stays in range, then Y->A and Z->B wrap around the uppercase alphabet.
Input: ("Shift me 5!", 0)
Expected Output: "Shift me 5!"
Explanation: A shift of 0 leaves every character unchanged.
Input: ("", 5)
Expected Output: ""
Explanation: Empty input yields empty output (boundary case).
Input: ("abc", -1)
Expected Output: "zab"
Explanation: A negative shift rotates backward: a->z (wraps), b->a, c->b. Equivalent to shift 25 after modulo.
Input: ("Zz", 1)
Expected Output: "Aa"
Explanation: Wrap at the end of each case: 'Z'->'A' and 'z'->'a'.
Input: ("Hello", 29)
Expected Output: "Khoor"
Explanation: shift 29 reduces to 29 % 26 = 3, so this matches a shift of 3.
Input: ("12345 !@#", 7)
Expected Output: "12345 !@#"
Explanation: No alphabetic characters, so nothing changes regardless of the shift.
Hints
- First normalize the shift with `shift % 26`. In Python the `%` operator already returns a non-negative result for a positive modulus, so `-1 % 26 == 25`. In other languages you may need `((shift % 26) + 26) % 26` to keep it in [0, 26).
- For a letter at 0-based index `i` within its alphabet (e.g. 'C' -> 2), the ciphered index is `(i + shift) % 26`; convert back to a character by adding the case's base ('A' or 'a').
- Follow-up optimization: build two 26-entry tables (one for uppercase, one for lowercase) once before the scan. Then each character is a single lookup — no modulo per character. A 256-entry byte lookup table over the whole ASCII range works too and is even faster.
- Non-letters aren't in either table, so just copy them through unchanged.