How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Find smallest start index avoiding left exit

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

You are given an integer array `jump` of length `n` (0-indexed). If you are currently at index `i`, your next position becomes `i + jump[i]` (a positive value moves right, a negative value moves left). Starting from an index `s`, you repeatedly apply this move rule. - If you ever reach an index `< 0`, you have moved out of the **left boundary**. - If you reach an index `>= n`, you have moved out of the array on the right (you may treat this as stopping). - The process may also loop inside the array. Return the **smallest** starting index `s` such that, during the entire process starting from `s`, you **never** move out of the left boundary (i.e., the sequence of visited indices never becomes negative). If no such index exists, return `-1`. Implement an algorithm that runs in O(n) time if possible.

Quick Answer: This question evaluates a candidate's ability to analyze reachability and cycle behavior in array-based functional graphs, testing competency in array manipulation, traversal, loop detection, and runtime optimization within the Coding & Algorithms domain.

You are given an integer array `jump` of length `n` (0-indexed). From index `i`, your next position is `i + jump[i]`. A positive value moves right, a negative value moves left, and `0` keeps you on the same index.\n\nStarting from an index `s`, repeatedly apply this rule:\n- If the next index becomes `< 0`, you have exited through the left boundary.\n- If the next index becomes `>= n`, you have exited on the right and the process stops.\n- The process may also loop forever inside the array.\n\nReturn the smallest starting index `s` such that the process starting from `s` never exits through the left boundary. Exiting on the right or looping inside the array is allowed. If no such starting index exists, return `-1`.

Constraints

0 <= n <= 200000
-10^9 <= jump[i] <= 10^9
An O(n) solution is expected.

Examples

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

Expected Output: 4

Explanation: Indices 0 through 3 eventually move to -1. Starting at 4 jumps to 6, which exits on the right, so the answer is 4.

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

Expected Output: 0

Explanation: Index 0 jumps to itself forever, which is allowed. Therefore the smallest valid start is 0.

Input: ([-1, -1, -1],)

Expected Output: -1

Explanation: Every starting index eventually exits through the left boundary.

Input: ([1, 1, -1],)

Expected Output: 0

Explanation: Starting from 0 gives 0 -> 1 -> 2 -> 1, which loops inside the array and never exits left.

Input: ([],)

Expected Output: -1

Explanation: There is no valid starting index in an empty array.

Input: ([-1],)

Expected Output: -1

Explanation: The only starting index immediately exits to the left.

Input: ([0],)

Expected Output: 0

Explanation: The only index loops to itself, so it is valid.

Input: ([1, -2, 3, -4, 1],)

Expected Output: 2

Explanation: Starts 0 and 1 exit left, while 2 jumps to 5 and exits right. So the smallest valid start is 2.

Hints

Think of each index as a node with exactly one outgoing edge to `i + jump[i]`.
If a walk revisits a node already seen in the same exploration, you found an internal cycle, which is safe because it can never suddenly exit left.

Quick Overview

This question evaluates a candidate's ability to analyze reachability and cycle behavior in array-based functional graphs, testing competency in array manipulation, traversal, loop detection, and runtime optimization within the Coding & Algorithms domain.