Quick Overview

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.

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`

Overview: 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.

Read the full Meta Site Reliability Engineer interview experience this question came from

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`.

Hints

  1. Use two pointers: one for `word` and one for `abbr`.
  2. When you see a digit, parse the full number first, then advance the word pointer by that amount.

Part 2: Balanced Bracket Validation

Given a string `s` containing only the characters `(`, `)`, `[`, `]`, `{`, and `}`, return whether the brackets are balanced. A string is balanced if: - Every opening bracket is closed by the same type of bracket. - Brackets are closed in the correct order. - An empty string is considered valid.

Constraints

  • 0 <= len(s) <= 100000
  • `s` contains only the characters `(`, `)`, `[`, `]`, `{`, and `}`

Examples

Input: "()[]{}"

Expected Output: True

Explanation: Each bracket is correctly opened and closed.

Input: "([)]"

Expected Output: False

Explanation: The order is wrong: `(` opens first, but `]` tries to close `[` before `)` closes `(`.

Hints

  1. Use a stack to keep track of the opening brackets you have not matched yet.
  2. When you see a closing bracket, it must match the most recent unmatched opening bracket.

Loading coding console...