PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This set of three problems evaluates algorithm design, complexity analysis, and data-structure reasoning across matrix path traversal, interval coverage, and subarray optimization tasks.

  • medium
  • Google
  • Coding & Algorithms
  • Software Engineer

Solve Three Array and Matrix Path Problems

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given three independent coding tasks. For each task, design an algorithm, implement it, and analyze its time and space complexity. 1. **Find the longest two-step descending path in a matrix.** Given an `m x n` integer matrix, find the maximum number of cells in a valid path. A path may start at any cell. From a cell, you may move only up, down, left, or right. - For the first move with values `a -> b`, the move is valid if `b < a`. - For every later move with consecutive values `a -> b -> c`, the move to `c` is valid if `c < b` or `c < a`. Return only the maximum path length. Example of the rule: `10 -> 7 -> 9` is valid because `9 < 10`, even though `9` is not less than `7`. `10 -> 7 -> 11` is invalid. 2. **Minimize hand movements on a piano keyboard.** Keyboard positions are positive integers. One hand can cover any interval of five consecutive positions, such as `[3, 7]`. You are given an array `notes`, where `notes[i]` is the position of the `i`-th note to play. The initial hand placement is free and does not count as a movement. After that, moving the hand to a different five-position interval counts as one movement. Return the minimum number of hand movements needed to play all notes in order. Examples: - `notes = [1, 2, 3, 4, 5]` returns `0`. - `notes = [5, 9, 1]` returns `1`. Follow-up: every time the hand moves, print the previous hand interval. Also print the final hand interval after all notes have been played. 3. **Find the longest increasing subarray with one optional edit.** Given an integer array, return the length of the longest strictly increasing contiguous subarray. Follow-up: you may change at most one array element to any integer value. Return the maximum possible length of a strictly increasing contiguous subarray after the optional change.

Quick Answer: This set of three problems evaluates algorithm design, complexity analysis, and data-structure reasoning across matrix path traversal, interval coverage, and subarray optimization tasks.

Part 1: Longest Two-Step Descending Path in a Matrix

You are given an integer matrix. A path is a sequence of visited cells that starts anywhere and moves only up, down, left, or right. The first move must go from value a to a smaller value b. After that, if the last two visited values are a and b, the next value c is valid when c < b or c < a. Return the maximum number of visited cells in any valid path. For this problem, revisiting a cell is allowed if every move remains valid.

Constraints

  • 0 <= number of rows <= 100
  • If the matrix is non-empty, 1 <= number of columns <= 100 and all rows have the same length
  • The total number of cells is at most 10^4
  • Each matrix value is in the range [-10^9, 10^9]

Examples

Input: ([],)

Expected Output: 0

Explanation: No cells can be visited in an empty matrix.

Input: ([[42]],)

Expected Output: 1

Explanation: A single cell is a valid path of length 1.

Input: ([[7, 7], [7, 7]],)

Expected Output: 1

Explanation: No first move to a smaller adjacent value exists, so the best path is any single cell.

Input: ([[5, 3, 4]],)

Expected Output: 4

Explanation: One optimal path is 5 -> 3 -> 4 -> 3. Revisiting the cell with value 3 is allowed.

Input: ([[5, 4, 4]],)

Expected Output: 3

Explanation: An optimal path is 5 -> 4 -> 4. The third 4 is valid because it is smaller than the value two steps earlier, 5.

Input: ([[5, 1], [4, 3]],)

Expected Output: 4

Explanation: One optimal path is 5 -> 4 -> 3 -> 1.

Input: ([[2, -1, 1, -2]],)

Expected Output: 4

Explanation: An optimal path is 2 -> -1 -> 1 -> -2.

Input: ([[6, 2, 5], [1, 4, 3]],)

Expected Output: 6

Explanation: One optimal path is 6 -> 2 -> 5 -> 3 -> 4 -> 1.

Hints

  1. The next move depends on the previous cell and the current cell, so the state is not just the current position.
  2. Memoize the best answer for each ordered adjacent pair of cells. Along transitions, the pair (max(previous, current), current) decreases, so the state graph is acyclic.

Part 2: Minimum Piano Hand Movements

Piano key positions are positive integers. One hand placement covers exactly five consecutive positions [L, L + 4]. You are given notes in the order they must be played. The initial hand placement is free and does not count as a movement. Moving the hand to a different valid interval counts as one movement. Return the minimum number of hand movements needed to play all notes in order.

Constraints

  • 0 <= len(notes) <= 2 * 10^5
  • 1 <= notes[i] <= 10^9

Examples

Input: ([],)

Expected Output: 0

Explanation: There are no notes to play, so no movement is needed.

Input: ([12],)

Expected Output: 0

Explanation: A single note can always be covered by the free initial placement.

Input: ([4, 6, 8, 5],)

Expected Output: 0

Explanation: All notes fit in one interval [4, 8], so the initial placement is enough.

Input: ([1, 5, 6],)

Expected Output: 1

Explanation: Notes 1 and 5 fit in [1, 5], but adding 6 makes the range 5, so a new placement is required for 6.

Input: ([8, 4, 6, 7, 9],)

Expected Output: 1

Explanation: Notes 8, 4, 6, 7 fit in [4, 8]. The note 9 cannot be added to that same interval, so one movement is needed.

Input: ([1, 2, 10, 11, 12, 3, 4],)

Expected Output: 2

Explanation: One optimal split is [1, 2], [10, 11, 12], [3, 4]. That uses 3 placements total, so 2 movements after the free initial placement.

Input: ([5, 5, 9, 9, 5],)

Expected Output: 0

Explanation: All notes stay within the interval [5, 9], so no movement is needed.

Input: ([2, 7, 3, 8, 4, 9],)

Expected Output: 3

Explanation: A minimum partition is [2], [7, 3], [8, 4], [9]. That is 4 placements total, so 3 movements.

Hints

  1. For one note x, the hand's left endpoint L can be any integer in [max(1, x - 4), x].
  2. While scanning the notes, keep the intersection of all left-endpoint ranges for the current block. Move only when that intersection becomes empty.

Part 3: Piano Hand Movement Trace

This is the follow-up to the piano movement problem. A hand placement covers exactly five consecutive positions [L, L + 4]. The initial placement is free. Every time the hand must move to a new interval, output the previous interval. After all notes are played, also output the final interval. Instead of printing, return the intervals in order as a list of [left, right] pairs. If several intervals are valid for the same block of notes, use the one with the smallest possible left endpoint so the output is deterministic.

Constraints

  • 0 <= len(notes) <= 2 * 10^5
  • 1 <= notes[i] <= 10^9

Examples

Input: ([],)

Expected Output: []

Explanation: No notes are played, so no intervals are used.

Input: ([1],)

Expected Output: [[1, 5]]

Explanation: A single note at position 1 can be covered by [1, 5]. Because positions are 1-indexed, this is the smallest valid interval.

Input: ([2, 4, 5],)

Expected Output: [[1, 5]]

Explanation: All three notes fit inside one 5-position interval. The valid choices are intervals with left endpoint 1 or 2, so choose the smallest: [1, 5].

Input: ([1, 5, 6, 2, 3, 8],)

Expected Output: [[1, 5], [2, 6], [4, 8]]

Explanation: Notes [1, 5] fit in [1, 5], but adding 6 would break that block. Then [6, 2, 3] fit in [2, 6], but adding 8 breaks it. The last note 8 uses [4, 8].

Input: ([4, 4, 8, 8, 12],)

Expected Output: [[4, 8], [8, 12]]

Explanation: The notes [4, 4, 8, 8] all fit exactly in [4, 8]. Adding 12 forces a move, so the final block is [8, 12].

Hints

  1. Build maximal consecutive blocks of notes that can be covered by one interval by intersecting feasible left-endpoint ranges.
  2. When a block ends, any left endpoint inside the current intersection works. The required tie-break says to choose the smallest one.

Part 4: Longest Strictly Increasing Contiguous Subarray

Given an integer array nums, return the length of the longest strictly increasing contiguous subarray. A contiguous subarray uses consecutive indices.

Constraints

  • 0 <= len(nums) <= 2 * 10^5
  • Each nums[i] is in the range [-10^9, 10^9]

Examples

Input: ([],)

Expected Output: 0

Explanation: An empty array has no subarrays, so the longest length is 0.

Input: ([7],)

Expected Output: 1

Explanation: A single element forms a contiguous subarray of length 1.

Input: ([1, 2, 3, 2, 3, 4, 5, 1],)

Expected Output: 4

Explanation: The longest strictly increasing contiguous subarray is [2, 3, 4, 5], which has length 4.

Input: ([5, 4, 3, 2],)

Expected Output: 1

Explanation: No adjacent pair is increasing, so the best possible length is 1.

Input: ([1, 1, 2, 3],)

Expected Output: 3

Explanation: Because the sequence must be strictly increasing, [1, 1] does not count. The longest valid subarray is [1, 2, 3].

Input: ([-3, -2, -1, 0, -1, 0, 1, 2],)

Expected Output: 4

Explanation: There are two longest increasing contiguous runs, [-3, -2, -1, 0] and [-1, 0, 1, 2], both of length 4.

Hints

  1. Scan from left to right and keep the current length of the increasing streak ending at the current index.
  2. If nums[i] <= nums[i - 1], the current increasing streak must restart at length 1.

Part 5: Longest Increasing Contiguous Subarray With One Edit

Given an integer array nums, you may change at most one element to any integer value. Return the maximum possible length of a strictly increasing contiguous subarray after this optional edit.

Constraints

  • 0 <= len(nums) <= 2 * 10^5
  • Each nums[i] is in the range [-10^9, 10^9]
  • The edited value may be any integer

Examples

Input: ([],)

Expected Output: 0

Explanation: The array is empty, so there is no subarray.

Input: ([42],)

Expected Output: 1

Explanation: A single element is already a strictly increasing contiguous subarray of length 1.

Input: ([1, 2, 3, 4],)

Expected Output: 4

Explanation: The whole array is already strictly increasing, so the answer is 4.

Input: ([1, 5, 3, 4],)

Expected Output: 4

Explanation: Change 5 to 2 to get [1, 2, 3, 4]. The whole array becomes strictly increasing.

Input: ([1, 2, 10, 3, 4],)

Expected Output: 4

Explanation: A length-5 increasing array is impossible with one edit because there is no integer strictly between 2 and 3. But changing 3 to 11 gives [1, 2, 10, 11, 4], which has an increasing contiguous subarray of length 4.

Input: ([1, 2, 2, 3],)

Expected Output: 3

Explanation: With one edit, you can make either [1, 2, 3] or [0, 2, 2, 3] style runs of length 3, but not length 4.

Input: ([-5, -3, -4, -2, -1],)

Expected Output: 4

Explanation: Change -3 to -6 to get [-5, -6, -4, -2, -1]. Then the subarray [-6, -4, -2, -1] is strictly increasing with length 4.

Hints

  1. Precompute the length of the increasing run ending at each index and the length of the increasing run starting at each index.
  2. If you change nums[i] and want to connect both sides, you need an integer x with nums[i - 1] < x < nums[i + 1]. That is possible exactly when nums[i + 1] > nums[i - 1] + 1.
Last updated: Jun 4, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Solve Flower Placement and Directory Deletion - Google (medium)
  • Simulate In-Place Cellular State Updates - Google (hard)
  • Compute Turnstile Crossing Times - Google (hard)
  • Determine Whether a Word Exists in a Graph - Google (medium)
  • Implement Checksums and Feature Rollout Evaluation - Google (medium)