How should I practice Graph Palindrome Queries?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Uber online assessment problems in FastPrep.

Is Graph Palindrome Queries associated with Uber?

FastPrep tags this as a Uber online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Graph Palindrome Queries

Learn this problem

● Hard

UberFULLTIMEOA

See Uber hiring insights

Problem statement

You are given an undirected graph rooted at node 0 with n nodes (numbered 0 to n-1). Each node i is labelled with a lowercase English letter given by labels[i].

You are also given m queries. For each query [node_from, node_to], collect all characters encountered while travelling from node_from to node_to along the unique path in the tree. Determine whether those characters can be rearranged to form a palindrome.

Return a boolean array of length m where result[i] is true if the characters for query i can form a palindrome, and false otherwise.

Function

palindromeQueries(n: int, labels: String, edges: int[][], queries: int[][]) → boolean[]

Examples

Example 1

n = 3labels = "aba"edges = [[0, 1], [1, 2]]queries = [[0, 2], [0, 1]]return = [true, false]

Query [0,2]: path is 0→1→2, chars = {a, b, a} → {a:2, b:1} → one odd-count char → can form palindrome → true.
Query [0,1]: path is 0→1, chars = {a, b} → {a:1, b:1} → two odd-count chars → cannot form palindrome → false.

Example 2

n = 2labels = "aa"edges = [[0, 1]]queries = [[0, 1]]return = [true]

Path 0→1 yields {a, a} → {a:2} → zero odd-count chars → true.

Example 3

n = 4labels = "abcd"edges = [[0, 1], [0, 2], [0, 3]]queries = [[1, 2]]return = [false]

Path 1→2 goes through node 0: chars = {b, a, c} → {a:1, b:1, c:1} → three odd-count chars → cannot form palindrome → false.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ m ≤ 10⁵
labels contains only lowercase English letters
Edges form a valid tree rooted at node 0