Compute longest increasing subsequence

Q: Compute longest increasing subsequence

This is a Coding & Algorithms interview question from TikTok for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given an integer array nums, compute the length of a longest strictly increasing subsequence and also output one valid subsequence. Aim for an O(n log n) approach; explain the binary-search (patience sorting) technique, how to reconstruct the subsequence, and analyze time/space complexity. Follow-ups: adapt to non-decreasing subsequences, handle duplicates carefully, and discuss how to count how many LIS exist.

Compute longest increasing subsequence

Comments (0)