Solve string match and DashMart BFS
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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()
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.
Input: ("hello", "ll")
Expected Output: 2
Explanation: "ll" first appears starting at index 2.
Input: ("aaaaa", "bba")
Expected Output: -1
Explanation: No substring of "aaaaa" equals "bba".
Input: ("abc", "")
Expected Output: 0
Explanation: Empty needle returns 0 by convention.
Input: ("a", "a")
Expected Output: 0
Explanation: Single-character exact match at index 0.
Input: ("", "a")
Expected Output: -1
Explanation: Edge case: a non-empty needle cannot be found in an empty haystack.
Input: ("mississippi", "issip")
Expected Output: 4
Explanation: "issip" first matches starting at index 4 (the second 'iss' run), not the earlier 'iss' at index 1 which is followed by 'is' not 'ip'.
Hints
- Slide a window of length len(needle) across haystack and compare substrings.
- Short-circuit: if len(needle) > len(haystack), the answer is immediately -1.
- 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)
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.
Input: ([[2, 0, 0], [0, 1, 0], [3, 0, 3]],)
Expected Output: 4
Explanation: Start (0,0), items (2,0) and (2,2). Go down-down to (2,0) collecting the first item (2 steps), then right-right to (2,2) for the second (2 more) = 4.
Input: ([[2, 0], [0, 0]],)
Expected Output: 0
Explanation: No item cells, so nothing to collect: 0 steps.
Input: ([[3, 0, 2, 0, 3]],)
Expected Output: 6
Explanation: Start at index 2 with items at the two ends. You must visit one end then the other: 2 steps to one end + 4 steps to the far end = 6.
Input: ([[2]],)
Expected Output: 0
Explanation: Single start cell, no items: 0 steps.
Input: ([[3], [0], [2], [0], [3]],)
Expected Output: 6
Explanation: Vertical mirror of the five-cell case: 2 steps to the nearer item end, then 4 to the far one = 6.
Input: ([[2, 3]],)
Expected Output: 1
Explanation: Item is immediately adjacent to the start: 1 step.
Input: ([[2, 1], [1, 3]],)
Expected Output: -1
Explanation: Obstacles at (0,1) and (1,0) fully isolate the item at (1,1) from the start; impossible, so -1.
Hints
- Encode progress as a bitmask: bit i is set once item i has been visited. The goal state is the all-ones mask.
- 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.
- The first time you reach the full mask, the BFS distance is optimal (all edges cost 1).
- 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.