Solve peak element and unique word abbreviation
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given two independent coding problems to solve.
1) Peak element in an array (binary search)
- Input: an integer array `nums` of length `n >= 1`.
- A peak is an index `i` such that `nums[i] > nums[i-1]` and `nums[i] > nums[i+1]`.
- Treat out-of-bounds neighbors as negative infinity: `nums[-1] = nums[n] = -∞`.
- Task: return the index of any peak element.
- Requirement: design an algorithm with `O(log n)` time.
2) Minimal unique abbreviations for a dictionary
- Input: an array of distinct strings `words`.
- A word can be abbreviated as: `prefix + <number of omitted middle characters> + last_char` (e.g., `"international" -> "i11l"`).
- Abbreviations must be unique across the list.
- If an abbreviation is not shorter than the original word, keep the original word.
- Task: return an array `abbr` where `abbr[i]` is the minimal-length abbreviation for `words[i]` that is unique among all words.
Clarify any assumptions you need (e.g., lowercase letters only) and implement the solutions.
Quick Answer: This question evaluates algorithmic design and data-structure skills by combining a binary-search peak-finding problem with a string-abbreviation uniqueness problem, testing competence in time-complexity reasoning and creation of minimal unique representations.