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

Solve Wonderful Strings and Grid Queries

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Two algorithmic tasks were reported. ### Task 1: Minimum-cost wonderful string A string is considered **wonderful** if, among the letters `'a'` through `'j'`, at most one letter appears an odd number of times. You are given: - A string `s` of length `n` containing only letters from `'a'` to `'j'`. - A `10 x 10` non-negative integer matrix `cost`, where `cost[i][j]` is the cost of replacing one occurrence of the `i`-th letter with the `j`-th letter. Assume `cost[i][i] = 0`. You may replace any characters independently. Return the minimum total cost required to transform `s` into a wonderful string. ### Task 2: Count reachable grid cells for threshold queries You are given an `m x n` grid of positive integers and an array `queries` of positive integers. For each query value `q`, start from cell `(0, 0)`. You may move up, down, left, or right, but you may only enter cells whose value is strictly less than `q`. For each query, return the number of distinct cells reachable from `(0, 0)`. Return the answers in the original order of the queries. Design an efficient algorithm for large inputs, for example where `m * n` and `queries.length` can each be up to `100000`.

Quick Answer: This question evaluates algorithm design and data-structure competencies through two problems: a parity-constrained minimum-cost string transformation over a 10-letter alphabet and threshold-based grid reachability under many queries.

Part 1: Minimum-cost Wonderful String

A string is called wonderful if, among the letters 'a' through 'j', at most one letter appears an odd number of times. You are given a string s that contains only letters from 'a' to 'j', and a 10 x 10 non-negative integer matrix cost. If a character is currently the i-th letter, changing it into the j-th letter costs cost[i][j]. You may choose a final letter for each character independently. Return the minimum total cost required to transform s into a wonderful string.

Constraints

0 <= len(s) <= 200000
s contains only characters from 'a' to 'j'
cost is a 10 x 10 matrix
0 <= cost[i][j] <= 10^9
cost[i][i] = 0
The answer may be larger than 32-bit integer range

Examples

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

Expected Output: 0

Explanation: The empty string already satisfies the condition.

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

Expected Output: 1

Explanation: For length 2, all counts must be even. Change either character into the other for cost 1.

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

Expected Output: 2

Explanation: The string has four odd counts. Two replacements are enough to pair letters into even counts.

Input: ("aabccd", [[0, 9, 9, 9, 9, 9, 9, 9, 9, 9], [9, 0, 9, 5, 9, 9, 9, 9, 9, 9], [9, 9, 0, 9, 9, 9, 9, 9, 9, 9], [9, 2, 9, 0, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9, 0, 9, 9, 9, 9, 9], [9, 9, 9, 9, 9, 0, 9, 9, 9, 9], [9, 9, 9, 9, 9, 9, 0, 9, 9, 9], [9, 9, 9, 9, 9, 9, 9, 0, 9, 9], [9, 9, 9, 9, 9, 9, 9, 9, 0, 9], [9, 9, 9, 9, 9, 9, 9, 9, 9, 0]])

Expected Output: 2

Explanation: Only 'b' and 'd' have odd counts. Changing 'd' to 'b' costs 2 and makes all counts even.

Hints

Only the parity of each final letter count matters. A 10-bit mask is enough to represent the odd/even state of all letters.
Process equal source letters together. If you decide which target letters receive an odd number of copies, every remaining copy can be sent in pairs to the cheapest target for that source letter.

Part 2: Count Reachable Grid Cells for Threshold Queries

You are given an m x n grid of positive integers and an array queries. For each query value q, start from cell (0, 0). You may move up, down, left, or right, but you may only enter cells whose value is strictly less than q. For each query, return the number of distinct cells that are reachable from (0, 0). Return the answers in the original order of the queries. Your algorithm should be efficient for large inputs where m * n and len(queries) can each be as large as 100000.

Constraints

1 <= m * n <= 100000
1 <= len(queries) <= 100000
1 <= grid[r][c] <= 10^9
1 <= queries[i] <= 10^9

Examples

Input: ([[1, 2, 3], [2, 5, 7], [3, 5, 1]], [5, 6, 2])

Expected Output: [5, 8, 1]

Explanation: For q = 5, only cells with values 1, 2, or 3 are allowed and 5 cells are reachable. For q = 6, all except the 7 are reachable.

Input: ([[5]], [1, 5, 6])

Expected Output: [0, 0, 1]

Explanation: The start cell itself must also satisfy the strict inequality. It becomes reachable only when q > 5.

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

Expected Output: [2, 6, 2]

Explanation: Sorting queries internally is helpful, but answers must be returned in the original order.

Input: ([[1, 100, 1], [1, 100, 1], [1, 1, 1]], [50, 101])

Expected Output: [7, 9]

Explanation: At threshold 50 the two cells with value 100 are blocked, but the other 7 cells are still connected through the bottom row.

Hints

If you process queries from small to large, cells reached for a smaller query never need to be processed again for a larger one.
Use a min-heap frontier starting from (0, 0). Repeatedly expand the smallest-valued reachable boundary cell while its value is below the current query.

Quick Overview

This question evaluates algorithm design and data-structure competencies through two problems: a parity-constrained minimum-cost string transformation over a 10-letter alphabet and threshold-based grid reachability under many queries.