TikTok·Machine Learning Engineer·Technical Phone Screen
- Given an integer array, find the length of the longest strictly increasing subsequence and output one valid subsequence. They wanted an O(n log n) solution using binary search, and asked you to walk through the patience sorting idea and explain how reconstruction works.
- How would you adapt the solution to handle non-decreasing subsequences instead of strictly increasing ones, and what changes are needed when duplicates are present?
- How would you count the total number of distinct longest increasing subsequences in the array?
- Walk through the time and space complexity of your O(n log n) LIS approach.
“I knew LIS and had done the O(n^2) version before, but the O(n log n) path with patience sorting was something I'd only half-remembered.”