Graph Palindrome Queries
Updated
Problem statement
You are given a tree with n nodes, numbered 0 to n - 1. Node 0 is the root. The input lists the n - 1 edges in edges; each edge works in both directions. Node i has a lowercase English letter labels[i].
You are also given m queries. Each query is a pair [node_from, node_to]. Walk from node_from to node_to along the one path between them in the tree, and write down the letter of every node you pass, including both ends. Can you rearrange those letters to make a palindrome?
For example, if the path has the letters a, b, a, you can rearrange them as aba, so the answer is true. For the letters a, b, the answer is false.
Return a boolean array of length m. Entry i is true if the letters on the path of query i can be rearranged into a palindrome, and false otherwise.
If node_from and node_to are the same node, the path is that one node and the answer is true.
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]The tree is the chain 0 - 1 - 2 with letters a, b, a.
Query [0, 2]: the path is 0, 1, 2 with letters a, b, a. The counts are a: 2 and b: 1. Only one letter has an odd count, so this can be a palindrome (aba): true.
Query [0, 1]: the path is 0, 1 with letters a, b. Two letters have an odd count, so it cannot be a palindrome: false.
The answer is [true, false].
Example 2
n = 2labels = "aa"edges = [[0, 1]]queries = [[0, 1]]return = [true]The path 0, 1 has the letters a, a. The count is a: 2, so no letter has an odd count and aa is a palindrome. The answer is [true].
Example 3
n = 4labels = "abcd"edges = [[0, 1], [0, 2], [0, 3]]queries = [[1, 2]]return = [false]Nodes 1, 2 and 3 all connect to node 0. The path from node 1 to node 2 goes through node 0: 1, 0, 2 with letters b, a, c. Three letters have an odd count, so it cannot be a palindrome. The answer is [false].
Constraints
1 ≤ n ≤ 1051 ≤ m ≤ 105, wheremisqueries.lengthlabels.length = n, andlabelscontains only lowercase English lettersedges.length = n - 1, andedgesform a tree on nodes0ton - 1- Every query is
[node_from, node_to]with0 ≤ node_from, node_to ≤ n - 1
More Uber Online Assessment questions
- Count Palindromic Ancestor PathsOA · Seen Aug 2026
- Jump Game with Prime-3 StepsOA · Seen Aug 2026
- Last Truck to Leave the LaneOA · Seen Jul 2026
- Chain of CommandOA · Seen Jul 2026
- Total Palindrome Substring CostOA · Seen Jun 2026
- Jump Game with Prime-Step RuleOA · Seen May 2026
- Pipeline Throughput Maximization Under BudgetOA · Seen May 2026
- Balanced Prefix Sets in a PermutationOA · Seen Apr 2026
- Minimum Edge Reversals to Root a TreeOA · Seen Apr 2026
- Maximum Riders in CarOA · Seen Apr 2026
Similar questions at other companies
- Palindromic Paths to the RootRippling · OARippling interview questions
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Part 2: Batch Access ReviewScale AI · OAScale AI interview questions
- Sum Dynamic Weighted Tree DistancesJuspay · OA
- Binary Tree CamerasAmazon · OA · PHONE SCREEN
- K-th Ancestor Subtree Preorder QueryAdobe · OAAdobe interview questions
- Maximum Sum Path Between Two Leaf NodesGoogle · OAGoogle interview questions
- Maximum Strength of Every NeuronMicrosoft · OAMicrosoft interview questions
- Delivery ServiceInMobi · OAInMobi interview questions
- Collect Opportunity Data in a TreeSalesforce · OASalesforce interview questions