Decode the Message
What is this problem about?
The Decode the Message interview question involves a simple substitution cipher. You are given a key string and a message string. The first appearance of each unique English letter in the key is mapped to the standard alphabet in order (first unique letter -> 'a', second -> 'b', and so on). Spaces are kept as spaces. You need to return the decoded message. This Decode the Message coding problem is a test of character mapping and frequency tracking.
Why is this asked in interviews?
Amazon and Meta use this "Easy" level question to check for basic data structure usage. It specifically tests your ability to use a Hash Map or a frequency array to store a mapping and then use that map to transform a string. It’s a test of clean code and efficient string traversal.
Algorithmic pattern used
This follows the Hash Table, String interview pattern.
- Build Map: Iterate through the key. Skip spaces and letters already in the map. Assign the next available alphabet character to each new letter found.
- Translate: Iterate through the message. For each character, look up its replacement in the map. If it's a space, append a space.
- Efficiency: Use a string builder to collect the results.
Example explanation
Key: "the quick brown fox jumps over the lazy dog", Message: "vkbs"
- First unique letter in key is 't' -> 'a'.
- 'h' -> 'b', 'e' -> 'c', 'q' -> 'd', etc.
- Looking at "vkbs":
- 'v' is the 22nd unique letter -> 'v'? (Wait, let's look at the mapping).
- If 'v' mapped to 'h', 'k' to 'e', 'b' to 'l', 's' to 'p', the message would be "help".
Common mistakes candidates make
- Redundant entries: Adding the same letter from the key multiple times to the mapping logic.
- Ignoring spaces: Trying to map spaces to letters instead of preserving them.
- Alphabet management: Not correctly incrementing the target character (the 'a', 'b', 'c'...) after each new mapping.
Interview preparation tip
When building a mapping from a string, always use a Set or check map.containsKey() to ensure you only process the first occurrence of each character.
