Katkat
Back

Caesar Cipher with Translation-Table Optimization

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests string manipulation, modular arithmetic, and the ability to optimize performance by trading space for time using a precomputed lookup table.

Caesar Cipher with Translation-Table Optimization

Implement a function caesar_cipher(text, shift) that shifts each alphabetical character in a given string by a specified integer shift. Non-alphabetical characters (e.g., spaces, numbers, punctuation) should remain unchanged. The cipher must preserve the case of the letters (e.g., 'A' shifted by 1 becomes 'B', 'a' shifted by 1 becomes 'b').

Crucially, you must optimize the performance for large strings by using a precomputed translation table rather than calculating the modulo operation for every character individually.

Function Signature

def caesar_cipher(text: str, shift: int) -> str:

Requirements

  • Handle shifts greater than 26 or negative shifts (e.g., a shift of 27 is equivalent to 1, -1 is equivalent to 25).
  • Ensure case consistency.
  • Use a lookup structure to map the original character to its shifted counterpart.

Examples

# Example 1
caesar_cipher("Hello, World!", 3)
# Output: "Khoor, Zruog!"
# Explanation: H->K, e->h, l->o, l->o, o->r, W->Z, o->r, r->u, l->o, d->g

# Example 2
caesar_cipher("abc", 27)
# Output: "bcd"
# Explanation: 27 % 26 = 1, so every letter moves forward by one.

Constraints

  • text length can be up to 10^6 characters.
  • shift can be any integer.
  • Time complexity should be O(N), where N is the length of the string, with minimal operations per character.

Hints

Hint 1

Normalize the shift value using the modulo operator `shift % 26` to handle cases where the shift is larger than the alphabet size.

Hint 2

Create a mapping (dictionary or array) that stores the shifted character for every possible input character (A-Z and a-z) before iterating through the string.

Hint 3

Accessing a dictionary or array index is a constant time operation, which is faster than performing conditional logic and arithmetic for every single character.

Follow-up questions

  • How would your approach change if the input was a massive stream of data rather than a fixed string?
  • What are the space complexity implications of your translation table if you were to expand the character set to include all Unicode characters?
  • Could you implement a decryption function that reverses the shift without needing to know the original shift value, perhaps using frequency analysis?