-1
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Why nest functions like that? \$\endgroup\$ – AMC Feb 8 at 22:09
1
\$\begingroup\$

Unfortunately for your interview hopes, the code you wrote doesn't solve the problem. Try this input:

findWinner([2,0,2], 0)

The way I would solve this problem is indeed to use a "graph algorithm" — something like flood-fill. Start with an array of bools, of the same size as your input array. Color the starting cell True. Then look at the neighbors of that cell. For each neighbor which is currently False, color it True and recurse on it. Eventually you'll run out of False neighbors and the recursion will end. Then check (or during the coloring, check) to see if any of the True (reachable) cells in your array have value 0.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Yup, I already said it does not work :). Thanks for the answer though. Would it be possible to share a source code to understand it better? \$\endgroup\$ – Ugur Yilmaz Feb 8 at 21:54
  • \$\begingroup\$ I added an answer based on your suggestion, it seems like it's working. can you check if I can make any optimization on it? I feel like the way I use recursion function definitely could be improved @Quuxplusone \$\endgroup\$ – Ugur Yilmaz Feb 8 at 23:01
1
\$\begingroup\$

Here is the answer based on @Quuxplusone's suggestion- thanks. Also, I don't understand why my question got downvoted without any comments, I'd appreciate if you add some comments why you did not like the question or what can be improved if you want to make a better community for all. So, I could improve my way of asking questions and wouldn't ask in the same style again. Thanks!

def findWinner(arr, pos):

    visited = [0, 0, 0, 0, 0, 0, 0, 0, 0]

    num = arr[pos]
    visited[pos] = 1
    if arr[pos] == 0:
        return True
    return dfs(arr, pos+num, visited) or dfs(arr, pos-num, visited)


def dfs(arr, pos, visited):
    if pos < 0 or pos >= len(arr):
        return False

    if visited[pos] == 1:
        return False
    visited[pos] = 1

    num = arr[pos]
    if arr[pos] == 0:
        return True
    return dfs(arr, pos+num, visited) or dfs(arr, pos-num, visited)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ The downvotes were probably because you said it's non-working code; one of the codereview rules is that the code has to already be in a working state. \$\endgroup\$ – Samwise Feb 9 at 0:28
  • \$\begingroup\$ I mean the code is working but it just doesn't work for some of the test cases and it just needed a little bit of a fix as it can be seen above. I just wanted to put my own solution as well, so people wouldn't think I am looking for an answer even without trying it, but apparently it backfired. I'll never understand the negativity here. Thanks for your comment anyway \$\endgroup\$ – Ugur Yilmaz Feb 9 at 0:32
  • \$\begingroup\$ Some people on this site are VERY particular. I don't understand that mindset myself, but just be aware that if you even hint that you're looking to fix rather than polish a piece of code, it's gonna get a lot of automatic downvotes before anyone's even read your post. :P \$\endgroup\$ – Samwise Feb 9 at 0:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.