Quick Overview

This question evaluates proficiency with string algorithms and pattern matching, assessing understanding of substring search complexity and algorithm selection within the algorithms and data structures domain, and is commonly asked to verify efficient low-level text-search implementation and time/space trade-off reasoning at a practical implementation level. The "Dash Mart" grid BFS evaluates graph traversal, state-space modeling, and shortest-path reasoning for multi-target collection tasks within graph algorithms and path-finding, and is commonly asked to measure competence in BFS-based search, state encoding and optimization strategies with a focus on practical algorithmic application and performance considerations.

Solve string match and DashMart BFS

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Implement a string-matching function that returns the first index of a pattern in a text (akin to LeetCode 28 Implement strStr()). 2) “Dash Mart” grid path-finding: given a 2-D map with a start cell, obstacles, and target pickup cells, code a BFS to find the minimum steps to collect all required items and explain follow-up optimizations. https://leetcode.com/problems/implement-strstr/description/

Quick Answer: This question evaluates proficiency with string algorithms and pattern matching, assessing understanding of substring search complexity and algorithm selection within the algorithms and data structures domain, and is commonly asked to verify efficient low-level text-search implementation and time/space trade-off reasoning at a practical implementation level. The "Dash Mart" grid BFS evaluates graph traversal, state-space modeling, and shortest-path reasoning for multi-target collection tasks within graph algorithms and path-finding, and is commonly asked to measure competence in BFS-based search, state encoding and optimization strategies with a focus on practical algorithmic application and performance considerations.

Implement strStr()

Implement a string-matching function `strStr(haystack, needle)` that returns the index of the first occurrence of `needle` in `haystack`, or `-1` if `needle` is not part of `haystack`. This is the classic LeetCode 28 problem. By convention, when `needle` is the empty string, return `0` (the empty string is found at the start of any string). Examples: - `strStr("sadbutsad", "sad") = 0` ("sad" occurs at index 0 and 6; first is 0) - `strStr("leetcode", "leeto") = -1` ("leeto" does not occur) - `strStr("hello", "ll") = 2` A brute-force O(n*m) scan is acceptable for the interview; mention KMP / Rabin-Karp as the O(n+m) follow-up.

Constraints

  • 1 <= haystack.length, needle.length <= 10^4 (and needle may be empty by the convention above)
  • haystack and needle consist of only lowercase English characters
  • Return 0 when needle is the empty string

Examples

Input: ("sadbutsad", "sad")

Expected Output: 0

Explanation: "sad" occurs at indices 0 and 6; the first occurrence is index 0.

Input: ("leetcode", "leeto")

Expected Output: -1

Explanation: "leeto" never appears in "leetcode", so return -1.

Hints

  1. Slide a window of length len(needle) across haystack and compare substrings.
  2. Short-circuit: if len(needle) > len(haystack), the answer is immediately -1.
  3. For the optimal O(n+m) follow-up, precompute the KMP failure (longest-proper-prefix-suffix) table so you never re-examine matched characters.

DashMart Grid: Minimum Steps to Collect All Items (BFS)

You are given a 2-D `grid` representing a DashMart store floor. Each cell holds one of: - `0` = open walkable cell - `1` = obstacle (a shelf you cannot enter) - `2` = the start cell (exactly one) - `3` = a pickup cell holding a required item Starting from the `2` cell, you may move one step up, down, left, or right into any non-obstacle cell (steps cost 1 each). Return the **minimum number of steps** needed to visit every `3` cell (collect every required item), in any order. Return `-1` if it is impossible to collect them all, and `0` if there are no items to collect (or all items coincide with the start). Because you must collect *all* items and may need to backtrack, this is a multi-target shortest-path problem. The standard approach is a BFS over the state `(row, col, collected_bitmask)`: the position plus a bitmask of which items have been picked up so far. The first time the bitmask becomes full, the current distance is the answer. Follow-up optimizations to discuss: precompute pairwise shortest distances between start and all items with per-source BFS, then solve a Traveling-Salesman-style DP over the item set (Held-Karp, O(k^2 * 2^k)) — far cheaper than state-BFS when the grid is huge but the number of items k is small.

Constraints

  • 1 <= rows, cols <= 50
  • Exactly one start cell (value 2); 0 or more item cells (value 3)
  • k (number of items) is small (e.g. <= 10) so 2^k stays tractable
  • Movement is 4-directional into non-obstacle cells only

Examples

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

Expected Output: 2

Explanation: Start at (0,0), one item at (0,2). Walk right twice: 2 steps.

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

Expected Output: -1

Explanation: The obstacle at (0,1) walls off the item at (0,2); it can never be reached, so -1.

Hints

  1. Encode progress as a bitmask: bit i is set once item i has been visited. The goal state is the all-ones mask.
  2. BFS over states (row, col, mask) — not just (row, col) — because you may legitimately revisit a cell with a different set of items already collected.
  3. The first time you reach the full mask, the BFS distance is optimal (all edges cost 1).
  4. Follow-up: if the grid is huge but items are few, run one BFS from start and from each item to get pairwise distances, then solve a small Held-Karp TSP DP over the items instead of a grid-sized state space.

Loading coding console...