Katkat
Back

Solve cache, grid path, and substring problems

MicrosoftSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to implement an LRU cache, solve a dynamic programming problem on a grid with constraints, and optimize string searching using the sliding window technique.

Part 1: LRU Cache

Design and implement a data structure for a Least Recently Used (LRU) cache. It should support the following operations:

  • get(key): Get the value of the key if it exists, otherwise return -1.
  • put(key, value): Update or insert the value if the key is not present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item. Both operations should run in O(1) average time complexity.

Part 2: Grid Path Optimization

You are given a m x n grid of non-negative integers. Find a path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) such that the sum of the numbers along the path is minimized. You can only move either down or right at any point in time.

# Example
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
# Path: 1 -> 3 -> 1 -> 1 -> 1, Sum = 7

Part 3: Longest Unique Substring

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

# Example
s = "abcabcbb"
# Longest substring: "abc", Length = 3

Constraints

  • For Part 1: capacity >= 1.
  • For Part 2: Grid size up to 200x200.
  • For Part 3: String length up to 5 * 10^4.

Hints

Hint 1

For the LRU cache, combine a doubly linked list with a hash map to achieve O(1) access and updates.

Hint 2

For the grid path, use a 2D array or modify the grid in-place to store the minimum cost to reach each cell based on the values from the top or left.

Hint 3

For the unique substring, use the sliding window pattern with a set or a hash map to track the indices of characters seen so far to jump the 'start' pointer efficiently.

Follow-up questions

  • How would you modify your LRU cache implementation to be thread-safe in a multi-threaded environment?
  • If the grid had obstacles (represented by -1) that cannot be passed through, how would your pathfinding algorithm change?
  • Can you solve the longest unique substring problem using only O(1) extra space if the character set is restricted to ASCII?