I got asked this question in an interview and I came up with a solution which I shared in the below but apparently it was not enough to pass. I'm looking forward to hearing how this problem could be solved.
The question is : You are given an array of numbers e.g arr= [1, 3, 2, 0, 1, 2, 8, 4, 1] that represents a board and a position that represents an index in the array, and your goal is to find whether you can reach to 0 in the array or not. If you can find the zero, you win the game. If you can't, you lose.
So you can only move to the right or to the left in the array. The rule for moving your index is as the value of the index in that array.
Example: arr[1,3,2,0,1,2,8,4,1] and you are given a position 0.
Position 0 is 1. So you can only move 1 to the left or 1 to the right. You can't move to the left because the index is out of bounds, but you can move to right. Then, you are at second index whose value is 3, then you can again move three to the left and right, (assuming you move right 3 times, you are at the 5th index whose value is 1. Then, you can move 1 to the left to get 0. Thus, you can win from a given position. I hope it's clear enough.
This is my solution that I've used dfs. It works for the above case but it does not work when there is 1,1 next to each other. Then, it loops to the infinity. I'm looking forward to hearing other solutions in terms of how to solve it or how to optimize this solution. I feel like graph algorithms could be used for this problem but I was not sure how to start or initiate a matrix to represent a graph from this list. Thank you so much
def findWinner(arr, pos): def dfs(arr, pos): if pos < 0 or pos >= len(arr): return False num = arr[pos] if arr[pos] == 0: return True return dfs(arr, pos+num) or dfs(arr, pos-num) num = arr[pos] if arr[pos] == 0: return True return dfs(arr, pos+num) or dfs(arr, pos-num)