Validate abbreviations and brackets
Company: Meta
Role: Site Reliability Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
The coding round included two short implementation problems:
1. Abbreviation validation
Given a lowercase word `word` and a string `abbr`, determine whether `abbr` is a valid abbreviation of `word`.
- Letters in `abbr` must match the corresponding letters in `word`.
- A positive integer in `abbr` means skipping that many characters in `word`.
- Numbers cannot have leading zeros.
- The abbreviation is valid only if it consumes the entire word exactly.
Example:
- `word = "internationalization"`, `abbr = "i12iz4n"` -> `true`
- `word = "apple"`, `abbr = "a2e"` -> `false`
2. Balanced bracket validation
Given a string `s` containing only the characters `(`, `)`, `[`, `]`, `{`, and `}`, return whether the brackets are balanced.
- Every opening bracket must be closed by the same type of bracket.
- Brackets must be closed in the correct order.
- An empty string is considered valid.
Example:
- `s = "()[]{}"` -> `true`
- `s = "([)]"` -> `false`
Quick Answer: This question evaluates proficiency in string parsing, pattern validation, and algorithmic correctness, covering abbreviation interpretation and bracket balancing while requiring careful handling of edge cases and input constraints.
Part 1: Abbreviation Validation
Given a lowercase word `word` and a string `abbr`, determine whether `abbr` is a valid abbreviation of `word`.
Rules:
- Letters in `abbr` must match the corresponding letters in `word`.
- A positive integer in `abbr` means skipping that many characters in `word`.
- Numbers cannot have leading zeros.
- The abbreviation is valid only if it consumes the entire word exactly.
Constraints
- 0 <= len(word) <= 100000
- 0 <= len(abbr) <= 100000
- `word` contains only lowercase English letters
- `abbr` contains only lowercase English letters and digits
- Any numeric part of `abbr` must represent a positive integer with no leading zeros to be valid
Examples
Input: ("internationalization", "i12iz4n")
Expected Output: True
Explanation: `i` matches, `12` skips 12 letters, `i` and `z` match, `4` skips 4 letters, and `n` matches the final character.
Input: ("apple", "a2e")
Expected Output: False
Explanation: After matching `a` and skipping 2 characters, the next character in `word` is `l`, not `e`.
Input: ("", "")
Expected Output: True