Google | Onsite | Longest Increasing Subsequence
- Posted
- 21 May 2024
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.
How it went
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.
Questions asked (1)
- 01
Longest Increasing Subsequence (LIS)
Data Structures & Algorithms · Medium
Longest Increasing Subsequence (LIS)
Problem Description:
Given an arrayarr[]of sizeN, 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].