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

Solve two interview coding problems

Quick Overview

These two problems evaluate algorithmic problem-solving skills: the first focuses on spatial reasoning and grid-based distance computation relative to obstacles, while the second targets tree traversal and character-frequency reasoning for ancestor-path palindrome checks.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

The interview included two coding problems. **Problem 1: Find valid robot locations in a grid** You are given a 2D grid containing empty cells and obstacles. A robot may be placed on any empty cell. For a candidate robot position, define a 4-element signature `[left, up, right, down]`, where each value is the number of steps from the robot's cell to the nearest obstacle in that direction. Only obstacles in the same row or column count. If there is no obstacle before the grid boundary in any direction, that candidate does not match. Given the grid and a target signature such as `[1, 1, 2, 2]`, return all robot locations `(row, col)` whose directional distances exactly match the target. **Problem 2: Count ancestor path segments that can form a palindrome** You are given a rooted tree with `treeNodes` nodes labeled `0..treeNodes-1`, where node `0` is the root. Each node stores a lowercase letter: - `char[] nodes`, where `nodes[i]` is the character at node `i` - `int[] nodeFrom` and `int[] nodeTo`, where each pair describes an edge in the tree - `int[] queries`, where each query is a start node For a query node `q`, consider every path segment that starts at `q` and ends at an ancestor of `q`, including `q` itself and the root. For each such segment, collect the characters along the path. Count how many of those path segments can be rearranged into a palindrome. A string can be rearranged into a palindrome if at most one character has an odd frequency. Return one answer per query. Example: - `treeNodes = 4` - `nodes = ['z', 'a', 'a', 'a']` - `nodeFrom = [0, 0, 1]` - `nodeTo = [1, 2, 3]` - `queries = [3]` For query `3`, the ancestor path segments are: - `3 -> 3`, characters `"a"` -> valid - `3 -> 1`, characters `"aa"` -> valid - `3 -> 1 -> 0`, characters `"aaz"` -> can be rearranged into `"aza"` -> valid So the result is `[3]`.

Quick Answer: These two problems evaluate algorithmic problem-solving skills: the first focuses on spatial reasoning and grid-based distance computation relative to obstacles, while the second targets tree traversal and character-frequency reasoning for ancestor-path palindrome checks.

Part 1: Find valid robot locations in a grid

You are given a rectangular grid made of empty cells . and obstacle cells #. A robot may be placed only on an empty cell. For a robot placed at position (row, col), define its signature as [left, up, right, down], where each value is the number of steps needed to reach the nearest obstacle cell in that direction. Only obstacles in the same row or column count, and the obstacle cell itself is included in the distance. If moving in any direction reaches the grid boundary before hitting an obstacle, that position is not a match. Return all empty cells whose signature exactly equals the target signature, in row-major order.

Constraints

0 <= number of rows <= 500
0 <= number of columns <= 500
All rows in grid have the same length
Each grid cell is either . or #
target has exactly 4 integers
1 <= target[i] <= max(1, rows, cols)

Examples

Input: (['#####', '#...#', '#.#.#', '#...#', '#####'], [2, 1, 2, 1])

Expected Output: [(1, 2), (3, 2)]

Explanation: Cells (1, 2) and (3, 2) both have obstacles 2 steps to the left and right, and 1 step up and down.

Input: (['####', '#..#', '#..#', '####'], [1, 1, 2, 2])

Expected Output: [(1, 1)]

Explanation: Only the top-left interior cell has the exact distances left=1, up=1, right=2, down=2.

Input: (['.#.', '...', '.#.'], [1, 1, 1, 1])

Expected Output: []

Explanation: Every empty cell is missing an obstacle in at least one direction before the boundary.

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

Expected Output: []

Explanation: An empty grid has no valid robot positions.

Input: (['.'], [1, 1, 1, 1])

Expected Output: []

Explanation: A single empty cell has no obstacle in any direction, so it cannot match.

Hints

For every empty cell, you need the nearest obstacle in four directions. Try sweeping left-to-right, right-to-left, top-to-bottom, and bottom-to-top to precompute these distances.
A cell cannot match if any one of the four directions has no obstacle before the boundary.

Part 2: Count ancestor path segments that can form a palindrome

You are given a tree with treeNodes nodes labeled 0 to treeNodes - 1, rooted at node 0. Each node stores one lowercase English letter. For each query node q, consider every path segment that starts at q and ends at an ancestor of q, including q itself and the root. For each such segment, collect the characters along that path and count how many of those segments can be rearranged into a palindrome. A multiset of characters can form a palindrome if at most one character has an odd frequency. Return one answer for each query in the same order.

Constraints

1 <= treeNodes <= 200000
len(nodes) == treeNodes
len(nodeFrom) == len(nodeTo) == treeNodes - 1
0 <= len(queries) <= 200000
nodes[i] is a lowercase English letter
0 <= queries[i] < treeNodes
The given edges form a tree rooted at node 0

Examples

Input: (4, ['z', 'a', 'a', 'a'], [0, 0, 1], [1, 2, 3], [3])

Expected Output: [3]

Explanation: The path segments from node 3 are a, aa, and aaz. All three can be rearranged into palindromes.

Input: (5, ['a', 'b', 'a', 'c', 'b'], [0, 1, 1, 0], [1, 2, 3, 4], [2, 3, 4, 0])

Expected Output: [2, 1, 1, 1]

Explanation: For node 2, segments a and aba are valid. For node 3 only c is valid. For node 4 only b is valid. The root contributes one valid segment by itself.

Input: (4, ['a', 'a', 'b', 'b'], [0, 1, 2], [1, 2, 3], [3, 2])

Expected Output: [4, 2]

Explanation: For node 3, all four upward segments are valid. For node 2, only b and baa are valid.

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

Expected Output: [1]

Explanation: A single node always forms one valid segment consisting of itself.

Input: (2, ['a', 'b'], [0], [1], [1, 1, 0])

Expected Output: [1, 1, 1]

Explanation: Repeated queries should produce repeated answers. Node 1 has only one valid upward segment, and node 0 also has one.

Hints

A path can be rearranged into a palindrome if its character-parity mask has at most one bit set. Think in terms of xor masks instead of full frequency tables.
During a DFS, maintain counts of prefix masks seen on the current root-to-parent path. For a node q, you only need masks equal to prefix[q] or differing from it by exactly one bit.

Quick Overview