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 Technical Screen rounds at Meta.

What role is this question designed for?

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

Solve Two String Problems | Meta Coding Question

Solve Two String Problems

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

The interview included two coding questions: 1. **Exactly one edit apart** Given two strings `s` and `t`, determine whether they are **exactly one edit apart**. An edit is one of the following operations applied once: - Insert a single character - Delete a single character - Replace a single character Return `true` if you can transform one string into the other using exactly one edit, and `false` otherwise. Example cases: - `s = "ab", t = "acb"` -> `true` - `s = "cab", t = "ad"` -> `false` - `s = "1203", t = "1213"` -> `true` - `s = "abc", t = "abc"` -> `false` 2. **Validate a word abbreviation** Given a 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 contain leading zeros. - The abbreviation is valid only if it consumes the entire word exactly. Example cases: - `word = "internationalization", abbr = "i12iz4n"` -> `true` - `word = "apple", abbr = "a2e"` -> `false` - `word = "substitution", abbr = "s10n"` -> `true` - `word = "word", abbr = "w02d"` -> `false` Implement efficient solutions for both problems.

Quick Answer: This question evaluates string manipulation, pattern parsing, and algorithmic problem-solving skills, focusing on edit operations, index and boundary handling, and numeric-token parsing for abbreviations.

Part 1: Exactly One Edit Apart

Given two strings `s` and `t`, determine whether they are exactly one edit apart. One edit means performing exactly one of these operations once: insert a single character, delete a single character, or replace a single character. Return `True` only if one string can be transformed into the other using exactly one edit. If they are already equal, or if they need two or more edits, return `False`.

Constraints

0 <= len(s), len(t) <= 100000
Strings may contain any characters.
An efficient linear-time solution is expected.

Examples

Input: ('ab', 'acb')

Expected Output: True

Explanation: Insert 'c' into 'ab' to get 'acb'.

Input: ('cab', 'ad')

Expected Output: False

Explanation: More than one edit is required.

Input: ('1203', '1213')

Expected Output: True

Explanation: Replace '0' with '1'.

Input: ('abc', 'abc')

Expected Output: False

Explanation: They are zero edits apart, not exactly one.

Input: ('', 'a')

Expected Output: True

Explanation: Insert one character into the empty string.

Hints

If the string lengths differ by more than 1, they cannot be exactly one edit apart.
Use two pointers to scan both strings. At the first mismatch, decide whether it represents a replacement or skipping one character in the longer string.

Part 2: Validate a Word Abbreviation

Given a word `word` and an abbreviation `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 in the abbreviation cannot have leading zeros, and the abbreviation is valid only if it consumes the entire word exactly.

Constraints

0 <= len(word), len(abbr) <= 100000
`abbr` contains only letters and digits.
Numbers in `abbr` represent positive skip lengths and cannot contain leading zeros.

Examples

Input: ('internationalization', 'i12iz4n')

Expected Output: True

Explanation: The abbreviation matches the word by skipping the correct number of characters.

Input: ('apple', 'a2e')

Expected Output: False

Explanation: After matching 'a' and skipping 2 characters, the next letter should be 'l', not 'e'.

Input: ('substitution', 's10n')

Expected Output: True

Explanation: Match 's', skip 10 characters, then match 'n'.

Input: ('word', 'w02d')

Expected Output: False

Explanation: The number '02' has a leading zero, which is not allowed.

Input: ('', '')

Expected Output: True

Explanation: An empty abbreviation is valid for an empty word.

Hints

Walk through both strings with two pointers. When you see digits in `abbr`, parse the whole number before moving on.
A digit '0' cannot start a number in the abbreviation.

Quick Overview

This question evaluates string manipulation, pattern parsing, and algorithmic problem-solving skills, focusing on edit operations, index and boundary handling, and numeric-token parsing for abbreviations.