← HackerRank Interview Insights

HackerRank·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate
May 2026

Summary

Online assessment for a Software Engineer role at HackerRank. One algorithmic problem that looks deceptively simple until k gets huge and you realize brute force is going to time out badly.

Questions Asked (1)

Q1

There are n friends numbered 1 to n. Each friend i passes the ball to receiver[i] every second, starting from friend 1. Given a potentially very large integer k, which friend holds the ball after exactly k seconds?

Algorithms & Data Structures
Author's notes

My first instinct was just simulate it, which works fine until you see k can be something like a billion.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the ball passing as a functional graph where each node has exactly one outgoing edge. Since k can be very large, use cycle detection (e.g., Floyd's algorithm) to find the cycle length and reduce k modulo the cycle length after accounting for the tail. Then simulate the remaining steps to find the final holder.

Pro tip: Always clarify constraints first: if n is small (e.g., ≤ 10^5) and k is huge, cycle detection is optimal; if n is also huge, you might need a different approach. Mentioning this shows you consider scalability.

1. Understand the problem

Restate the problem: starting from friend 1, after each second the ball moves to receiver[i]. We need the friend after exactly k seconds. Note that k can be very large, so simulation is infeasible.

2. Model as a functional graph

Each friend has exactly one outgoing edge to receiver[i]. This forms a directed graph where each component has exactly one cycle with trees feeding into it. The ball's path will eventually enter a cycle.

3. Detect cycle and compute parameters

Use Floyd's cycle-finding algorithm (tortoise and hare) to find the cycle start (tail length) and cycle length. Alternatively, use a visited array to record the first time each node is seen.

4. Reduce k and find final position

If k < tail length, simulate k steps from start. Otherwise, reduce k to (k - tail_length) % cycle_length and then simulate that many steps from the cycle start. Return the resulting friend.

5. Analyze complexity and edge cases

Time O(n) and space O(1) with Floyd's, or O(n) space with visited array. Handle edge cases: k=0 (friend 1), self-loops, and multiple components (though start is always 1).

Key Points to Mention

  • Functional graph: each node has out-degree 1, so every path eventually enters a cycle.
  • Cycle detection using Floyd's tortoise and hare (O(1) space) or visited array (O(n) space).
  • Computing tail length (μ) and cycle length (λ) to reduce k modulo λ.
  • Handling k=0 and ensuring 1-indexed friends.
  • Time complexity O(n) and space complexity O(1) or O(n).
  • Edge cases: self-loop (receiver[i]=i), k smaller than tail length.

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