HackerRank·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Apr 2026

Summary

Coding round for a software engineer position at HackerRank. One algorithmic problem, graph traversal flavored, with a big constraint on k that rules out any brute force approach pretty quickly.

Questions Asked (1)

You have n friends labeled 1 to n. Each friend i always passes a ball to a fixed receiver[i]. Starting from friend 1, who holds the ball after exactly k passes? k can be up to around 10^9 so you can't just simulate it.

Algorithms & Data Structures

Author's notes

The naive loop fails immediately once you see the constraint on k, which I did notice pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the friends and their fixed receivers as a functional graph where each node has exactly one outgoing edge. Since k can be up to 10^9, use cycle detection (e.g., Floyd's tortoise and hare) to find the cycle length and the entry point, then compute the final position using modular arithmetic.

Pro tip: Clarify with the interviewer whether the ball is passed exactly k times or if you start at friend 1 and then perform k passes; also mention edge cases like k=0 and self-loops to show thoroughness.

1. Understand the problem and constraints

Restate the problem: starting at node 1, follow the 'receiver' pointers for k steps. Note that k can be up to 10^9, so simulation is infeasible.

2. Model as a functional graph

Recognize that each node has exactly one outgoing edge, so the graph consists of cycles with trees feeding into them. The path from node 1 will eventually enter a cycle.

3. Detect cycle and find entry point

Use Floyd's cycle-finding algorithm (tortoise and hare) to find the cycle length and the first node of the cycle (the entry point). Alternatively, use a visited array to record the step at which each node is first seen.

4. Compute the final position

Let mu be the number of steps before entering the cycle, and lambda be the cycle length. If k < mu, the answer is the node reached after k steps. Otherwise, the answer is the node at position mu + ((k - mu) mod lambda) along the path.

5. Handle edge cases and verify

Consider k=0 (return 1), self-loops (cycle length 1), and ensure the algorithm works when the cycle includes node 1. Test with small examples.

Key Points to Mention

Functional graph representation: each node has exactly one outgoing edge.
Cycle detection using Floyd's algorithm or visited array.
Time complexity O(n) and space complexity O(1) with Floyd's, or O(n) with visited array.
Modular arithmetic to skip full cycles: (k - mu) % lambda.
Edge cases: k=0, self-loops, cycle starting at node 1.
Alternative approach: binary lifting for O(n log k) time, but cycle detection is more efficient.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.