Solve DFS grid and keypad problems
Company: Uber
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You may be asked to solve one or more DFS/backtracking problems:
1. **Grid connectivity problem**: Given an `m x n` grid where `1` represents land and `0` represents water, count how many connected land regions exist. Cells are connected horizontally and vertically.
2. **Phone keypad combinations**: On a classic phone keypad, digits map to letters as follows: `2 -> abc`, `3 -> def`, `4 -> ghi`, `5 -> jkl`, `6 -> mno`, `7 -> pqrs`, `8 -> tuv`, `9 -> wxyz`.
- Given a digit string such as `2345`, generate all possible letter strings it can represent.
- Also determine how many possible outputs exist for the input.
Explain your approach, edge cases, and time/space complexity.
Quick Answer: This question evaluates understanding of DFS and backtracking for grid traversal and combinatorial generation, assessing skills in graph traversal, recursion, connected-component counting, and mapping digit sequences to letter combinations.