Uber·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

May 2026

Summary

Uber coding round for a software engineer position. The problem was a tree-based palindrome path counting question that looked manageable at first but has some real bite to it once you think about the query complexity.

Questions Asked (1)

You're given an undirected tree where each node stores a single character. For each query node, count how many nodes on the path from that node up to the root produce a substring (from the query node to that ancestor, inclusive) whose characters can be rearranged into a palindrome. Design an efficient solution that handles multiple queries.

Algorithms & Data Structures

Author's notes

The palindrome condition is the part that trips you up first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a parity bitmask (26 bits) to represent character counts modulo 2 along root-to-node paths. A substring from node u to ancestor v is palindrome-permutable iff the XOR of masks from root to u and root to v (exclusive) has at most one set bit. For each query node, count ancestors v (including u) where the XOR mask has popcount ≤ 1, using a DFS with a hash map of mask frequencies along the current path.

Pro tip: Mention that the parity mask approach reduces the palindrome condition to a bitwise XOR and popcount check, which is O(1) per ancestor. Also note that using a hash map during DFS avoids O(N) per query, achieving O(N + Q) total time.

1. Preprocess tree and masks

Root the tree at node 0. Compute a 26-bit parity mask for each node representing character counts modulo 2 from root to that node.

2. Derive palindrome condition

For a query node u and ancestor v, the substring from v to u is palindrome-permutable iff mask[u] XOR mask[parent(v)] has at most one set bit (popcount ≤ 1).

3. DFS with frequency map

During DFS, maintain a hash map counting occurrences of each mask along the current root-to-node path. For each node u, count ancestors v where mask[u] XOR mask[parent(v)] has popcount ≤ 1.

4. Answer queries efficiently

For each query node u, the answer is the count computed during DFS. Store answers in an array indexed by node.

5. Analyze complexity

Time O(N + Q) with O(N) space for masks and hash map. Each node processed once, each query answered in O(1).

Key Points to Mention

Parity bitmask representation of character counts (26 bits).
Palindrome-permutable condition: at most one character has odd count.
XOR operation to get parity of substring between ancestor and node.
Popcount check (≤ 1) on the XOR mask.
DFS with backtracking and hash map to track mask frequencies along path.
Time complexity O(N + Q) and space O(N).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.