Determine reachability and minimum jumps
Company: SoFi
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given an array of non-negative integers nums of length n, where nums[i] is the maximum number of steps you can move forward from index i:
(
1) Determine whether you can reach index n-1 starting from index 0.
(
2) If reachable, compute the minimum number of jumps required to reach index n-1. Aim for an O(n) time, O(
1) extra space solution if possible. Explain the algorithm, prove its correctness, analyze time/space complexity, and discuss edge cases (e.g., zeros that block progress, n=1, very large jump values, and cases where the last index is unreachable).
Quick Answer: This question evaluates algorithmic problem-solving skills including array traversal, reachability analysis, greedy optimization and complexity reasoning within the Coding & Algorithms domain.