How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Validate word abbreviation and reconcile two abbreviations

Quick Overview

Validate word abbreviation and reconcile two abbreviations evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Validate word abbreviation and reconcile two abbreviations

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Implement a function isValidAbbreviation(word: string, abbr: string) that returns true if abbr is a valid abbreviation of word, where a positive integer in abbr represents the number of letters skipped and leading zeros are invalid. Follow-ups: (a) Given two abbreviations abbr1 and abbr2, determine whether there exists at least one original word (over lowercase letters) that both could represent; if so, return true and output one possible alignment of kept/skipped positions, otherwise return false. (b) Analyze time and space complexity, and discuss how you would handle very long inputs or streaming validation.

Quick Answer: Validate word abbreviation and reconcile two abbreviations evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Valid Word Abbreviation

Implement `isValidAbbreviation(word, abbr)` that returns `true` if `abbr` is a valid abbreviation of `word`. An abbreviation replaces any number of consecutive characters with the count of characters replaced. A positive integer in `abbr` represents how many letters are skipped; the remaining characters in `abbr` must match `word` exactly, in order. Numbers must not contain leading zeros (e.g. `"01"`, `"s010n"` are invalid abbreviations), and the abbreviation is valid only if the two strings are fully consumed at the same time. Example: `isValidAbbreviation("internationalization", "i12iz4n") = true` because `i` + skip 12 + `iz` + skip 4 + `n` reconstructs the word. `isValidAbbreviation("apple", "a2e") = false` because `a` + skip 2 lands on the 4th char (`l`), not `e`. Use two pointers: walk `word` with `i` and `abbr` with `j`. On a letter in `abbr`, it must equal `word[i]` (advance both). On a digit, reject a leading `0`, parse the full number, and advance `i` by that count. Return `true` iff both pointers finish exactly at the end.

Constraints

1 <= word.length, but word and abbr may also be empty in edge cases.
word consists of lowercase English letters.
abbr consists of lowercase English letters and digits.
Numbers in abbr have no leading zeros (a leading zero makes the abbreviation invalid).
Parsed skip counts fit in a 32-bit / 64-bit integer.

Examples

Input: ("internationalization", "i12iz4n")

Expected Output: True

Explanation: i + skip 12 + iz + skip 4 + n exactly rebuilds the 20-letter word.

Input: ("apple", "a2e")

Expected Output: False

Explanation: a + skip 2 lands on index 3 ('l'), which does not match the required 'e'.

Input: ("substitution", "s10n")

Expected Output: True

Explanation: s + skip 10 + n reconstructs 'substitution' (1 + 10 + 1 = 12 letters).

Input: ("substitution", "s55n")

Expected Output: False

Explanation: '55' = skip 55 overshoots the word, so the pointers never finish together.

Input: ("substitution", "s010n")

Expected Output: False

Explanation: The number '010' has a leading zero, which is an invalid abbreviation.

Input: ("word", "1ord")

Expected Output: True

Explanation: skip 1 + 'ord' matches 'word'.

Input: ("", "")

Expected Output: True

Explanation: Empty word and empty abbreviation both finish immediately at the end.

Input: ("a", "01")

Expected Output: False

Explanation: Leading zero is invalid, and the leftover '1' would overshoot anyway.

Input: ("hi", "3")

Expected Output: False

Explanation: skip 3 overshoots the 2-letter word, so j ends but i does not equal n.

Hints

Use two pointers, one over word and one over abbr, advancing them independently.
When you hit a digit, parse the entire consecutive run of digits as one number, then jump that many positions in word.
Reject the abbreviation immediately if a number starts with '0' (leading zeros are invalid).
The abbreviation is valid only if BOTH pointers reach the end together — a number that runs past the end of word, or leftover characters, means invalid.

Reconcile Two Word Abbreviations

Follow-up to Valid Word Abbreviation. Given two abbreviation strings `abbr1` and `abbr2`, determine whether there exists at least one original word over lowercase letters that BOTH abbreviations could represent. Return `true` if such a word exists, otherwise `false`. Each abbreviation uses the same rules as before: a positive integer (no leading zeros) means "skip that many letters" (a wildcard run that can stand for any letters), and a literal letter must appear at that exact position. Two abbreviations describe the same word iff they have the **same total length** and, at every position where BOTH pin down a concrete letter, those letters are equal. A skip in either abbreviation acts as a wildcard at that position. Example: `canBothRepresentSameWord("a2c", "ab1c") = true` — both have length 4, abbr1 = a,_,_,c and abbr2 = a,b,_,c; no conflicting fixed letters, so a word like `"abxc"` works. `canBothRepresentSameWord("a2c", "a3c") = false` — lengths 4 vs 5 can never describe the same word. Approach: expand each abbreviation into a per-position list where a literal contributes its character and a skip of k contributes k wildcard slots. If lengths differ, return `false`; otherwise return `false` only if some position has two differing fixed letters. Reject any abbreviation containing a leading-zero number.

Constraints

abbr1 and abbr2 each follow the abbreviation grammar: lowercase letters and positive integers with no leading zeros.
An abbreviation containing a leading-zero number is invalid and yields false.
The original word, if it exists, is over lowercase English letters.
Either abbreviation may be empty; two empty abbreviations both represent the empty word.

Examples

Input: ("a2c", "ab1c")

Expected Output: True

Explanation: Both length 4: a,_,_,c vs a,b,_,c. No conflicting fixed letters, so e.g. 'abxc' works.

Input: ("a2c", "a3c")

Expected Output: False

Explanation: Lengths 4 vs 5 differ, so no single word fits both.

Input: ("3", "1a1")

Expected Output: True

Explanation: Both length 3; abbr1 is all wildcards, so any word matching abbr2 (e.g. 'xay') works.

Input: ("ab", "ba")

Expected Output: False

Explanation: Position 0 fixes 'a' vs 'b' (conflict) — no common word.

Input: ("2", "abc")

Expected Output: False

Explanation: Length 2 vs 3 differ.

Input: ("a1b", "a1b")

Expected Output: True

Explanation: Identical abbreviations trivially share a word like 'axb'.

Input: ("01", "1")

Expected Output: False

Explanation: '01' has a leading zero and is an invalid abbreviation.

Input: ("", "")

Expected Output: True

Explanation: Two empty abbreviations both represent the empty word.

Input: ("1a1", "a1b")

Expected Output: True

Explanation: Both length 3: _,a,_ vs a,_,b. No position fixes two different letters, so e.g. 'aab' works.

Hints

Think of each digit-run as a sequence of wildcard slots and each letter as a fixed slot, then line the two sequences up position by position.
If the two abbreviations expand to different total lengths, no single word can satisfy both — return false.
A conflict only happens when both abbreviations fix a concrete (and different) letter at the same position; a skip on either side is a wildcard that matches anything.
Don't forget to reject abbreviations with leading zeros before comparing.

Quick Overview

Validate word abbreviation and reconcile two abbreviations

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Valid Word Abbreviation

Constraints

1 <= word.length, but word and abbr may also be empty in edge cases.
word consists of lowercase English letters.
abbr consists of lowercase English letters and digits.
Numbers in abbr have no leading zeros (a leading zero makes the abbreviation invalid).
Parsed skip counts fit in a 32-bit / 64-bit integer.

Examples

Input: ("internationalization", "i12iz4n")

Expected Output: True

Explanation: i + skip 12 + iz + skip 4 + n exactly rebuilds the 20-letter word.

Input: ("apple", "a2e")

Expected Output: False

Explanation: a + skip 2 lands on index 3 ('l'), which does not match the required 'e'.

Input: ("substitution", "s10n")

Expected Output: True

Explanation: s + skip 10 + n reconstructs 'substitution' (1 + 10 + 1 = 12 letters).

Input: ("substitution", "s55n")

Expected Output: False

Explanation: '55' = skip 55 overshoots the word, so the pointers never finish together.

Input: ("substitution", "s010n")

Expected Output: False

Explanation: The number '010' has a leading zero, which is an invalid abbreviation.

Input: ("word", "1ord")

Expected Output: True

Explanation: skip 1 + 'ord' matches 'word'.

Input: ("", "")

Expected Output: True

Explanation: Empty word and empty abbreviation both finish immediately at the end.

Input: ("a", "01")

Expected Output: False

Explanation: Leading zero is invalid, and the leftover '1' would overshoot anyway.

Input: ("hi", "3")

Expected Output: False

Explanation: skip 3 overshoots the 2-letter word, so j ends but i does not equal n.

Hints

Use two pointers, one over word and one over abbr, advancing them independently.
When you hit a digit, parse the entire consecutive run of digits as one number, then jump that many positions in word.
Reject the abbreviation immediately if a number starts with '0' (leading zeros are invalid).
The abbreviation is valid only if BOTH pointers reach the end together — a number that runs past the end of word, or leftover characters, means invalid.

Reconcile Two Word Abbreviations

Constraints

abbr1 and abbr2 each follow the abbreviation grammar: lowercase letters and positive integers with no leading zeros.
An abbreviation containing a leading-zero number is invalid and yields false.
The original word, if it exists, is over lowercase English letters.
Either abbreviation may be empty; two empty abbreviations both represent the empty word.

Examples

Input: ("a2c", "ab1c")

Expected Output: True

Explanation: Both length 4: a,_,_,c vs a,b,_,c. No conflicting fixed letters, so e.g. 'abxc' works.

Input: ("a2c", "a3c")

Expected Output: False

Explanation: Lengths 4 vs 5 differ, so no single word fits both.

Input: ("3", "1a1")

Expected Output: True

Explanation: Both length 3; abbr1 is all wildcards, so any word matching abbr2 (e.g. 'xay') works.

Input: ("ab", "ba")

Expected Output: False

Explanation: Position 0 fixes 'a' vs 'b' (conflict) — no common word.

Input: ("2", "abc")

Expected Output: False

Explanation: Length 2 vs 3 differ.

Input: ("a1b", "a1b")

Expected Output: True

Explanation: Identical abbreviations trivially share a word like 'axb'.

Input: ("01", "1")

Expected Output: False

Explanation: '01' has a leading zero and is an invalid abbreviation.

Input: ("", "")

Expected Output: True

Explanation: Two empty abbreviations both represent the empty word.

Input: ("1a1", "a1b")

Expected Output: True

Explanation: Both length 3: _,a,_ vs a,_,b. No position fixes two different letters, so e.g. 'aab' works.

Hints

Think of each digit-run as a sequence of wildcard slots and each letter as a fixed slot, then line the two sequences up position by position.
If the two abbreviations expand to different total lengths, no single word can satisfy both — return false.
A conflict only happens when both abbreviations fix a concrete (and different) letter at the same position; a skip on either side is a wildcard that matches anything.
Don't forget to reject abbreviations with leading zeros before comparing.