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 online assessment coding practice problem when the problem catalog has that company and stage context.

Problem

Palindrome Path Queries in a Tree

Learn this problem

UberFULLTIMEOA

See Uber hiring insights

Problem statement

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.

Function

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

Examples

Example 1

n = 5edges = [[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.

Example 2

n = 4edges = [[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