Interview questions · Meta
Solve peak element and unique word abbreviation
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.
You are given two independent coding problems to solve.
- Peak element in an array (binary search)
- Input: an integer array
numsof lengthn >= 1. - A peak is an index
isuch thatnums[i] > nums[i-1]andnums[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.
- 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
abbrwhereabbr[i]is the minimal-length abbreviation forwords[i]that is unique among all words.
Clarify any assumptions you need (e.g., lowercase letters only) and implement the solutions.
Community answers
Nothing here yet.
Join in on CSWork →