FastPrepLongest Alternating a/b Path in a Tree
Problems/Longest Alternating a/b Path in a Tree

Longest Alternating a/b Path in a Tree

Hudson River Trading logoHudson River Trading● MediumNEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Two candidates described this task from Hudson River Trading's 2021 online assessment for new grad Python roles. It was the second of two problems in a two-hour test. One of them said the problem photos in their post came from an earlier post, so the two reports may not be fully separate. Every node of a tree holds the letter a or b, and you want the longest path on which no two neighboring nodes have the same letter. One report says the letters come as a string and the answer is a count of nodes.

The reports do not say how the tree is given, whether the path has to start at the root, whether a single node counts, or how big the tree can be, and they give no examples. Here the tree comes as a parent array with node 0 as the root, the path can start and end at any node, a single node counts as a path of 1, and there are at most 10^4 nodes. The examples are new.

Our version is about 90% the same as the reported questions.

You are given a tree with n nodes numbered from 0 to n - 1. Node 0 is the root. The array parent describes the tree: parent[0] is -1, and for every other node i, parent[i] is the node directly above i. A parent can have a larger number than its child.

Each node holds one letter, 'a' or 'b'. The letter of node i is labels[i].

A path is a list of different nodes in which each node is joined to the next one by a tree edge. A path does not have to start at the root or end at a leaf. It can go up to some node and then down a different branch. A single node is also a path.

A path is alternating if no two neighboring nodes on it have the same letter. Return the number of nodes on the longest alternating path.

The tree can be a single chain of 10^4 nodes, so a recursive solution must be able to go that deep.

Function

longestAlternatingPath(parent: int[], labels: String) → int

Examples

Example 1

parent = [-1,0,0,1,1,3,4]labels = "abbaaba"return = 5

Edges 0-1, 0-2, 1-3, 1-4 and 3-5 join nodes with different letters. Edge 4-6 joins two 'a' nodes, so node 6 can never be next to node 4 on an alternating path.

The path 5 → 3 → 1 → 0 → 2 has the letters b, a, b, a, b. No two neighbors match, and it has 5 nodes. It goes up from node 5 to the root and then down to node 2.

No alternating path is longer, so the answer is 5.

Example 2

parent = [-1,0,0]labels = "aaa"return = 1

Every node is labeled 'a', so any path with two or more nodes has two neighbors with the same letter. A single node is still a path with no neighbors, so the answer is 1.

Example 3

parent = [-1,3,0,2,1,3]labels = "aaabba"return = 4

Here a parent can have a larger number than its child. For example, parent[1] = 3. The edges are 0-2, 2-3, 3-1, 1-4 and 3-5.

Nodes 0 and 2 are both 'a', so the root cannot be next to node 2. Node 0 has no other neighbor, so it is not on any longer path.

The path 4 → 1 → 3 → 2 has the letters b, a, b, a and 4 nodes. The path 4 → 1 → 3 → 5, which turns at node 3, also has 4 nodes. Without the blocked edge, the usable part has the five nodes 1 to 5, and three of them (2, 4 and 5) have only one usable neighbor. A path has only two ends, so it cannot hold all five nodes. The answer is 4.

Constraints

  • n == parent.length == labels.length
  • 1 <= n <= 10^4
  • parent[0] == -1
  • 0 <= parent[i] <= n - 1 for every i from 1 to n - 1
  • Following parent links from any node always reaches node 0, so parent describes one tree rooted at node 0.
  • labels contains only the letters 'a' and 'b'.

More Hudson River Trading Online Assessment questions

  • Count Palindrome Addition ChoicesOA · Seen Nov 2026
  • Count Multiples of Three with Two SevensOA · Seen Oct 2026
  • Recursively Expanded Shell Command CountsOA · Seen Oct 2026
  • Rotate Matrix Regions Around the DiagonalsOA · Seen Oct 2026
  • Maximum Diamond SumOA · Seen Oct 2026
  • Smallest Most-Lit Street PositionOA · Seen Oct 2026
  • Rearrange String by Alternating EndsOA · Seen Sep 2026
  • Most Items Within Budget from a Start IndexOA · Seen Sep 2026
  • Count Sawtooth SubarraysOA · Seen Aug 2026
  • Backtick Identifier ConverterOA · Seen Jun 2026

Similar questions at other companies

  • Maximum Data Transfer TimeMicrosoft · OAMicrosoft interview questions
  • Best Sum Downward Tree PathCitadel · OACitadel interview questions
  • Longest Transfer Time in a Server TreeRippling · OARippling interview questions
  • Binary Tree Level OrderMorgan Stanley · OAMorgan Stanley interview questions
  • Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions
  • Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
  • Part 2: Batch Access ReviewScale AI · OAScale AI interview questions
  • Binary Tree CamerasAmazon · OA · PHONE SCREEN
  • Maximum Sum Path Between Two Leaf NodesGoogle · OAGoogle interview questions
  • Special Diameter EndpointsAgoda · OAAgoda interview questions

Interview reports that mention this question

  • HRT New Grad Python Track Interviews: 9 Experiences

Hudson River Trading interview experiences

  • Hudson River Trading Quant Video Interview: 1 Experience
  • HRT SWE Intern and Onsites: 34 Experiences (Part 2 of 2)
  • HRT Python Track Interviews: 64 Experiences (Part 1 of 2)
All Hudson River Trading interview questionsSee Hudson River Trading hiring insights
Saved
class Solution {
    public int longestAlternatingPath(int[] parent, String labels) {
        // Write your code here.
    }
}
Checking account…