Google | Onsite | Longest Increasing Subsequence

Posted
21 May 2024
364 reads

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)

  1. 01

    Longest Increasing Subsequence (LIS)

    Data Structures & Algorithms · Medium

    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].

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!