How should I practice Palindromic Paths to the Root?

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

Is Palindromic Paths to the Root associated with Rippling?

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

Palindromic Paths to the Root

Rippling● HardFULLTIMEOA

Problem statement

You are given a tree with n nodes numbered from 0 to n - 1, rooted at node 0. Each edges[j] = [a, b] is an undirected edge between nodes a and b. Node i holds the letter labels[i], and n is the length of labels.

For a query node u, walk from u up to the root. Call the nodes on this walk u = p0, p1, ..., pk = 0. For each node v on the walk, including u itself and the root, look at the letters on the nodes from u to v. Count how many choices of v give letters that can be rearranged to form a palindrome.

A group of letters can be rearranged into a palindrome exactly when at most one letter appears an odd number of times.

Return an array answer where answer[i] is the count for queries[i].

Function

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

Examples

Example 1

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

Node 3 walks up through 3, 1, 0 with letters a, b, a. The groups a, ab, and aba are checked. a and aba can form palindromes, but ab cannot, so the count is 2.

Node 4 walks through 4, 1, 0 with letters b, b, a. The groups b, bb, and bba all work, since bba can become bab. The count is 3.

Node 5 walks through 5, 2, 0 with letters c, a, a. The groups c and caa work, since caa can become aca, but ca does not. The count is 2.

Example 2

edges = []labels = "z"queries = [0,0]return = [1,1]

The tree is a single node. The only walk is the node itself, and one letter is always a palindrome, so each query answers 1.

Example 3

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

From node 3 the letters are d, c, b, a. Only the group d works, because every longer group has at least two letters that appear once. The count is 1.

From node 1 the letters are b, a, and again only b works. The count is 1.

Constraints

1 <= n <= 2 * 10^4, where n = labels.length
labels contains only lowercase English letters.
edges.length == n - 1, and each edges[j] has two different nodes from 0 to n - 1.
The edges connect all n nodes into one tree.
1 <= queries.length <= 2 * 10^3
0 <= queries[i] < n, and the same node may appear in more than one query.