Katkat
Back

Solve Grid Path and Unique Substring

BloombergSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests grid traversal via dynamic programming or recursion, combined with the sliding window technique to identify unique character patterns within string segments.

Part 1: Grid Path

Given a 2D grid of size m x n filled with non-negative integers, find the path from the top-left (0, 0) to the bottom-right (m-1, n-1) that minimizes the sum of all numbers along the path. You can only move either down or right at any point in time.

Function Signature

def minPathSum(grid: List[List[int]]) -> int:

Example

Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]] Output: 7 Explanation: The path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.

Part 2: Longest Unique Substring

Given a string s, find the length of the longest substring without repeating characters.

Function Signature

def lengthOfLongestSubstring(s: str) -> int:

Example

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Constraints

  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100
  • 0 <= s.length <= 5 * 10^4

Edge Cases

  • Grid with single row or single column.
  • Empty string or string with all identical characters.

Hints

Hint 1

For the grid path, consider that the minimum cost to reach `(i, j)` is the value at `(i, j)` plus the minimum of reaching `(i-1, j)` or `(i, j-1)`.

Hint 2

For the longest unique substring, use a sliding window approach with a hash map to store the last seen index of each character.

Hint 3

Ensure your sliding window left boundary only moves forward to the index after the previous occurrence of the current repeating character.

Follow-up questions

  • How would the grid path algorithm change if you could move in all four directions (up, down, left, right) with non-negative weights?
  • Can you optimize the space complexity of the grid path solution to O(n) instead of O(m*n)?
  • How would you modify the unique substring problem to handle a sliding window of a fixed maximum length?