FastPrepCount Nodes in a Chain

Count Nodes in a Chain

Apple logoApple● EasyFULLTIMEPHONE SCREEN
Learn

Problem statement

You are given a starting node in a finite doubly linked chain. Each node exposes only its left and right neighbor. Count the nodes in that chain.

For this exercise, arrays left and right serialize a read-only node pool: node i has neighbors left[i] and right[i]. A neighbor of -1 means that side ends. Start at start and follow neighbor links; do not infer chain length from node identifiers or the size of the storage pool.

The pool may contain other disconnected chains. Return the size of the chain containing start, excluding every other component. If the pool is empty, start = -1 and the answer is 0. Links are consistent and acyclic. Do not modify them.

Function

countChainNodes(left: int[], right: int[], start: int) → int

Examples

Example 1

left = [2,3,-1,0]right = [3,-1,0,1]start = 3return = 4

Starting inside a four-node chain requires both directions.

Example 2

left = []right = []start = -1return = 0

The empty node pool has no chain.

Example 3

left = [-1,-1,0,1,3]right = [2,3,-1,4,-1]start = 3return = 3

Count the selected chain and exclude other stored chains.

Constraints

  • 0 <= left.length = right.length <= 1024.
  • Nonempty input has 0 <= start < left.length.
  • Every neighbor is -1 or a valid node index.
  • If right[i] = j, then left[j] = i, and conversely.
  • Every component is a simple finite chain, including a possible isolated node.

More Apple problems

See Apple hiring insights
public int countChainNodes(int[] left, int[] right, int start) {
    // write your code here
}
left[2,3,-1,0]
right[3,-1,0,1]
start3
expected4
Checking account…