How should I practice Palindrome Path Queries in a Tree?

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

Is Palindrome Path Queries in a Tree associated with Uber?

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

FastPrep

Problem

Palindrome Path Queries in a Tree

UberFULLTIMEOA

See Uber hiring insights

You are given an undirected tree with n nodes numbered from 0 to n - 1. The tree is rooted at node 0, and each node i has a lowercase English character labels[i].

You are also given a list of queries. For each query [u, v], consider all node characters encountered on the simple path from u to v, including both endpoints.

Return an integer array where the answer for each query is 1 if the characters on that path can be rearranged to form a palindrome, and 0 otherwise.

Examples

01 · Example 1

n = 5
edges = [[0,1],[0,2],[1,3],[1,4]]
labels = "ababa"
queries = [[3,4],[2,3],[2,4]]
return = [1,1,0]

For [3,4], the path characters are b,b,a, which can form bab. For [2,3], the characters are a,a,b,b, which can form a palindrome. For [2,4], the characters are a,a,b,a, with two odd character counts, so they cannot form a palindrome.

02 · Example 2

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

The first two paths contain three different characters, so neither can be rearranged into a palindrome. A path from a node to itself always contains one character.

Constraints

n == labels.length
edges.length == n - 1
edges forms a valid tree rooted at node 0.
labels contains only lowercase English letters.
queries[i].length == 2