Quick Overview

This question evaluates graph-traversal and modular arithmetic skills by requiring modeling a circular array as a state graph and determining reachability and minimum-distance jumps under wrap-around constraints.

Find shortest jumps in circular array

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a circular array `arr` of length `n`. From index `i`, you may jump exactly `arr[i]` steps either to the left or to the right (wrapping around the array), i.e. you can move to: - `(i + arr[i]) mod n` - `(i - arr[i]) mod n` Given two indices `start` and `target` (0-based), return the minimum number of jumps needed to reach `target` starting from `start`. If it is impossible to reach `target`, return `-1`. Clarifications: - Each jump uses the value at your current index to determine the exact jump distance. - The array is circular, so indices wrap around using modulo `n`. Example: - `arr = [2, 1, 2, 3]`, `start = 0`, `target = 3` - From 0 you can go to 2 (right) or 2 (left) → 2 - From 2 you can go to 0 or 0 → cannot reach 3 → return `-1`. Implement a function to compute this minimum jump count.

Quick Answer: This question evaluates graph-traversal and modular arithmetic skills by requiring modeling a circular array as a state graph and determining reachability and minimum-distance jumps under wrap-around constraints.

You are given a circular array `arr` of length `n`. From index `i`, you must jump exactly `arr[i]` positions either to the left or to the right, wrapping around the array. From index `i`, the two possible next indices are: - `(i + arr[i]) mod n` - `(i - arr[i]) mod n` Given two 0-based indices `start` and `target`, return the minimum number of jumps needed to reach `target` starting from `start`. If it is impossible to reach `target`, return `-1`. Notes: - Each jump uses the value at your current index. - The array is circular, so indices always wrap using modulo `n`. - If `start` is already equal to `target`, the answer is `0`.

Constraints

  • 1 <= len(arr) <= 200000
  • 0 <= arr[i] <= 10^9
  • 0 <= start, target < len(arr)

Examples

Input: ([2, 1, 2, 3], 0, 3)

Expected Output: -1

Explanation: From index 0 you can only reach index 2, and from index 2 you can only return to index 0, so index 3 is unreachable.

Input: ([1, 1, 1, 1], 0, 2)

Expected Output: 2

Explanation: One shortest path is 0 -> 1 -> 2. Another is 0 -> 3 -> 2.

Hints

  1. Treat each index as a node in a graph, with up to two outgoing edges to the indices you can jump to.
  2. Since every jump has the same cost, a level-by-level traversal helps find the minimum number of jumps.

Loading coding console...