Google | Onsite | Longest Increasing Subsequence
Summary
This post describes the 'Longest Increasing Subsequence' problem that I encountered during my Google onsite interview, complete with problem statement, examples, and a detailed solution approach.
Full Experience
During my onsite interview with Google, I was presented with the classic 'Longest Increasing Subsequence' problem. I focused on explaining the problem thoroughly, illustrating it with examples, and then detailing a dynamic programming approach, including its recursive formulation and a Python code example. I also discussed how memoization could optimize the solution, acknowledging the time complexity of the initial recursive approach.
Interview Questions (1)
Longest Increasing Subsequence (LIS)
Problem Description:
Given an array arr[] of size N, the task is to find the length of the Longest Increasing Subsequence (LIS). An LIS is the longest possible subsequence in which the elements are sorted in increasing order.
Examples:
1. Input: arr[] = [3, 10, 2, 1, 20]
- Output: 3
- Explanation: The longest increasing subsequence is
[3, 10, 20].
2. Input: arr[] = [3, 2]
- Output: 1
- Explanation: The longest increasing subsequences are
[3]and[2].
3. Input: arr[] = [50, 3, 10, 7, 40, 80]
- Output: 4
- Explanation: The longest increasing subsequence is
[3, 7, 40, 80].