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 Backend Engineer candidates at Uber during technical interviews.

Replace Dashes With Nearest Letters

Company: Uber

Role: Backend Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an `m x n` grid containing only dash characters `'-'` and alphabetic letters. For every dash cell, replace it with the nearest letter in the grid. Distance is Manhattan distance using 4-directional movement: up, down, left, and right. Letter cells remain unchanged. If a dash cell has multiple nearest letters at the same minimum distance, any one of those letters may be used. **Follow-up:** Change the tie-breaking rule so that if a dash cell has multiple nearest letters at the same minimum distance, it must be replaced by the lexicographically smallest of those letters. Return the modified grid.

Quick Answer: This question evaluates a candidate's competence in grid traversal, distance computation using Manhattan metrics, and handling tie-breaking rules including lexicographic ordering.

Part 1: Replace Dashes with Any Nearest Letter

You are given a rectangular grid of lowercase English letters and '-' characters. For every dash cell, replace it with a nearest letter from the grid. Distance is Manhattan distance using 4-directional movement: up, down, left, and right. Existing letter cells must remain unchanged. If a dash cell has multiple nearest letters at the same minimum distance, any one of them is acceptable. Return the completed grid. For the sample tests below, tie cases are avoided so the expected output is unique.

Constraints

0 <= m <= 200, where m is the number of rows
If m > 0, then 1 <= n <= 200, where n is the number of columns
All rows have the same length
Each cell is either '-' or a lowercase English letter
If the grid is non-empty, it contains at least one letter

Examples

Input: []

Expected Output: []

Explanation: Edge case: an empty grid stays empty.

Input: ['q']

Expected Output: ['q']

Explanation: Edge case: a single letter cell is unchanged.

Input: ['ab-', '---']

Expected Output: ['abb', 'abb']

Explanation: Each dash is uniquely closer to either 'a' or 'b'.

Input: ['m---', '----']

Expected Output: ['mmmm', 'mmmm']

Explanation: With only one letter in the grid, every dash becomes that letter.

Input: ['abc', 'def']

Expected Output: ['abc', 'def']

Explanation: There are no dashes to replace.

Hints

Instead of running a search from every dash, start from all letter cells at once.
A multi-source BFS spreads outward in increasing Manhattan distance, so the first time a dash is reached, it has found a nearest letter.

Part 2: Replace Dashes with the Lexicographically Smallest Nearest Letter

You are given a rectangular grid of lowercase English letters and '-' characters. For every dash cell, replace it with the nearest letter in the grid. Distance is Manhattan distance using 4-directional movement: up, down, left, and right. Existing letter cells must remain unchanged. If a dash cell has multiple nearest letters at the same minimum distance, you must choose the lexicographically smallest of those letters. Return the completed grid.

Constraints

0 <= m <= 200, where m is the number of rows
If m > 0, then 1 <= n <= 200, where n is the number of columns
All rows have the same length
Each cell is either '-' or a lowercase English letter
If the grid is non-empty, it contains at least one letter

Examples

Input: []

Expected Output: []

Explanation: Edge case: an empty grid stays empty.

Input: ['z-a']

Expected Output: ['zaa']

Explanation: The middle cell is distance 1 from both 'z' and 'a', so it becomes 'a'.

Input: ['a--', '---', '--b']

Expected Output: ['aaa', 'aab', 'abb']

Explanation: Cells tied between 'a' and 'b' must choose 'a', the smaller letter.

Input: ['-', 'c']

Expected Output: ['c', 'c']

Explanation: Edge case: a single-column grid with one dash above a letter.

Input: ['abc', 'def']

Expected Output: ['abc', 'def']

Explanation: There are no dashes, so the grid is unchanged.

Hints

You still want a multi-source BFS, because all edges have equal weight.
To enforce lexicographic tie-breaking, initialize the BFS frontier so smaller letters expand first among cells at the same distance.

Quick Overview

This question evaluates a candidate's competence in grid traversal, distance computation using Manhattan metrics, and handling tie-breaking rules including lexicographic ordering.