DRW·Data Scientist·Technical Phone Screen
- Given an array of movie ratings, implement a solution that returns both the length of the longest strictly increasing subsequence and one valid subsequence as a list of 1-based indices. Must run in O(n log n) time.
- Implement a data structure supporting two operations on an integer array: point updates (add a value to a single element) and range sum queries. Must handle up to 200,000 elements and operations efficiently.
- You have a list of release timestamps and a list of deployment windows. For each window, assign the most recent available release that hasn't been used yet and is no later than the window's timestamp. If none exists, return -1. Aim for O((n+m) log(n+m)) time.
“This is the classic LIS problem but they wanted the actual indices too, not just the length, which tripped me up.”