Katkat
Back

Solve peak element and unique word abbreviation

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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