How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Uber during technical interviews.

Solve DFS grid and keypad problems | Uber Coding Question

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.

Part 1: Count Connected Land Regions

You are given a 2D binary grid where 1 represents land and 0 represents water. Count how many connected land regions exist. Two land cells belong to the same region if they are connected horizontally or vertically. Diagonal cells are not connected.

Constraints

0 <= number of rows <= 200
0 <= number of columns <= 200
Each grid cell is either 0 or 1
All rows have the same length

Examples

Input: ([[1, 1, 0, 0], [0, 1, 0, 1], [0, 0, 0, 1], [1, 0, 0, 0]],)

Expected Output: 3

Explanation: There are three separate land regions: the top-left cluster, the right-side vertical cluster, and the single land cell at the bottom-left.

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

Expected Output: 0

Explanation: There is no land in the grid.

Input: ([[1]],)

Expected Output: 1

Explanation: A single land cell forms one region.

Input: ([],)

Expected Output: 0

Explanation: An empty grid has no regions.

Input: ([[1, 0, 1, 1, 0, 1]],)

Expected Output: 3

Explanation: In this single row, the land cells form three groups: [1], [1,1], and [1].

Hints

Whenever you find an unvisited land cell, start a DFS or BFS from it and mark every reachable land cell.
Increase the region count only when you begin exploring a brand-new land component.

Part 2: Generate Phone Keypad Letter 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 string of digits containing only characters from '2' to '9', return all possible letter combinations the number can represent. Return the combinations in the natural backtracking order: process digits from left to right, and for each digit, try its letters in listed order. If the input is empty, return an empty list.

Constraints

0 <= len(digits) <= 10
Each character in digits is between '2' and '9'
The returned order should follow keypad letter order from left to right

Examples

Input: ('23',)

Expected Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Explanation: Digit '2' gives abc and digit '3' gives def, so there are 3 x 3 = 9 combinations.

Input: ('',)

Expected Output: []

Explanation: An empty input has no combinations.

Input: ('7',)

Expected Output: ['p', 'q', 'r', 's']

Explanation: Digit '7' maps to four letters.

Input: ('92',)

Expected Output: ['wa', 'wb', 'wc', 'xa', 'xb', 'xc', 'ya', 'yb', 'yc', 'za', 'zb', 'zc']

Explanation: Digit '9' contributes wxyz and digit '2' contributes abc.

Hints

Think of each digit as a set of choices. Build the answer one position at a time.
A recursive backtracking function can append one letter, explore deeper, then remove it to try the next letter.

Part 3: Count Phone Keypad Output Possibilities

Using the same phone keypad mapping—2 -> abc, 3 -> def, 4 -> ghi, 5 -> jkl, 6 -> mno, 7 -> pqrs, 8 -> tuv, 9 -> wxyz—determine how many distinct letter strings a given digit string can represent. Do not generate the actual strings. If the input is empty, return 0.

Constraints

0 <= len(digits) <= 100000
Each character in digits is between '2' and '9'
The answer may be very large; in Python, normal integers can handle it

Examples

Input: ('2345',)

Expected Output: 81

Explanation: Each of these four digits maps to 3 letters, so the total is 3 x 3 x 3 x 3 = 81.

Input: ('',)

Expected Output: 0

Explanation: An empty input has no possible outputs.

Input: ('7',)

Expected Output: 4

Explanation: Digit '7' maps to pqrs, which gives four possibilities.

Input: ('79',)

Expected Output: 16

Explanation: Digit '7' has 4 choices and digit '9' has 4 choices, so 4 x 4 = 16.

Input: ('222222',)

Expected Output: 729

Explanation: There are six digits, each with 3 choices, so the total is 3^6 = 729.

Hints

Each digit contributes an independent number of choices: usually 3, but 7 and 9 contribute 4.
The total count is the product of the number of choices for each digit.

Quick Overview

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.