Determine minimal substitutions and removals
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
Given a list of words, determine the minimum number of character substitutions required so that, in every word, no two adjacent characters are identical.
Given an array of n unique integers, determine the minimum number of elements that must be removed so the array becomes "almost sorted"—meaning that after the removals, deleting at most one additional element would make the remaining array strictly ascending.
Quick Answer: This question evaluates string manipulation and adjacency-constraint handling in the first task and sequence analysis with minimal-removal and subsequence reasoning in the second, targeting competencies such as local transformation logic, subsequence recognition, and optimization under input constraints.
Given an array of n unique integers, return the minimum number of elements to remove so that the remaining array is almost sorted. An array is almost sorted if deleting at most one additional element from it would make it strictly increasing. Removals must preserve the original relative order (i.e., the remaining elements form a subsequence of the original).
Constraints
- 0 <= n <= 200000
- All nums[i] are pairwise distinct
- -10^9 <= nums[i] <= 10^9
- Aim for O(n log n) time and O(n) extra space
Hints
- Let L be the length of the longest strictly increasing subsequence (LIS).
- Any almost-sorted subsequence can become strictly increasing by removing one element, so its strictly increasing remainder cannot exceed length L.
- You can achieve length L+1 by taking any LIS and adding one extra element; compute L with patience sorting (binary search) in O(n log n).