Jump Game As Interview Problem, Domain Solutions

Over on LeetCode, there's a problem known as the Jump Game.

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.

Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

A couple years ago some teams at work used to use this, and I tried it a few times, but I eventually retired it because despite being rated "medium" only one person I tested it on could solve it, and it took a while.

Whenever I consider a problem to ask for a technical interview (given that I have to ask one, I don't think the normal tech interview is a good process), I make sure I can do it myself first, and within a shorter time frame than I would give people I'm interviewing. If I can't do it, or can't do it fast enough, I'm not going to bother asking.

So I think the Jump Game was a bit unfortunate to look at, because I came up with the way to implement the solution about 5-20 seconds after reading the description and the two examples, and then spent around 10-15 minutes actually implementing it in Python and testing with various edge cases. I gave this to people with never less than 30 mins, and usually 45-60, to come up with a solution. Shouldn't be too bad right? There are some potential extensions to the problem too if they get the solution quickly.

Is it obvious to you too? Would you get the solution quickly?

I had the fortune to recognize that this is a special case of a general search question. I've implemented breadth-first and depth-first search algorithms a lot of times, and had done one again very recently prior to first seeing this problem. So the relationship hit me immediately. The problem is asking you to search down a path and see if you can reach the end. Rephrasing the problem:

You begin in the First room, there are N rooms. Can you reach the Last room N?
You are given an array of N non-negative integers. Each index corresponds to the room number, and the value at each index determines which rooms (if any) are reachable from that room. From any room, you can visit neighboring rooms by "jumping" forward up to the maximum jump length specified by the element of the array.

Phrased this way, you just have to find a path of "jumps" to the final room, or if there is no path, then you are unable to reach the end. A greedy depth first search works here, though breadth first works too and is the solution that the 1 candidate I gave this to who solved it ended up with. Here's a version in Lisp I did for fun (original was in Python):

(defun jumpgame (input)

  (let ((frontier (list 0))

        (visited (list)))

    (loop

      :until (zerop (length frontier))

      :do

      (let* ((location (pop frontier))

             (max-jump (elt input location)))

        (if (eql location (1- (length input)))

            (return t)) ; reached the end

        (push location visited) ; mark as visited

        (dotimes (jump max-jump) ; add neighbors if unvisited

          (let ((neighbor-loc (+ location (1+ jump))))

            (unless (or (find neighbor-loc visited)

                        (>= neighbor-loc (length input)))

              (push neighbor-loc frontier))))))))



(jumpgame #(2 3 1 1 4)) ; should be true

(jumpgame #(3 2 1 0 4)) ; should be false

(jumpgame #(2 4 0 0 0 1)) ; true

Even if you don't know Lisp, it ought to be fairly clear if you know iterative DFS: create a frontier list (initializing it with the root node, in this case the start of the input list with the first room) and a visited set to keep track of what we've expanded to look at. Now loop until there's nothing left on the frontier. Take the next item off the frontier, check if it's what we're looking for. If so, we can return successful find. If not, then add that location to the visited set, then get all the neighbors and add them if they haven't been visited already. If we exit the loop due to nothing left to visit, we didn't find it.

Perhaps it would look a bit prettier if refactored into a recursive form with the frontier list being implicit in the call stack, but that leads to issues for larger problem sizes, and I might want to benchmark this against larger problem sizes in the future. Besides, in Lisp (as opposed to Scheme or Clojure) looping like you do in other programming languages is straightforward.

Stepping back, we solved the jump game, but how good is our solution? To measure that, we can introduce a new requirement, and see how easy it is to modify our solution to meet it. Enter the Jump Game 2.

Now we get to assume that all inputs are reachable if we need to, and we are to return the shortest number of jumps necessary to reach the end.

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Recall our solution was a greedy depth-first-search. Even if we now know we'll find a path, we aren't guaranteed the direct route is the shortest. A look at how the frontier list is added to will explain.

If we use that input vector for our current algorithm, we can see how our frontier list gets constructed for each loop iteration (just add a print to the top of the loop):

Frontier: (0)
Frontier: (2 1)
Frontier: (3 1)
Frontier: (4 1)

We reached the end, and it took 3 jumps: we started at index 0 which has neighbors at index 2 and 1. We jumped to index 2 first, which has a neighbor at 3. We jumped to index 3, which has a neighbor at index 4. We jumped to index 4, and we have reached the end in three jumps.

What to do? If we had considered index 1 before index 2, we would have seen that the reachable neighbors from there were 2, 3, and 4. We have to be smart again and consider 2 is already on the frontier list (though we haven't visited it yet), and to consider 4 (the end) before 3 (which would result in an extra jump). But if we were smart, we could realize that within two passes in our loop, we found the exit.

Fortunately there's an easy solution: just change from a depth-first search, to a breadth-first search. The way to do that is to change how the frontier list works, and then move the search operations from outside and before the innermost loop to inside.

Currently, the frontier list is a stack. We just need to turn it into a queue. In Python, if we were appending to the end and using pop(), we'd just have to change that to pop(0) and be done. Alas in Common Lisp it seems there's a bit more work to do. It's not hard to make one yourself, but in this case I'm just going to load up a library that did it already. So (list 0) becomes (queue 0), length becomes qlen, push becomes enq, pop becomes deq, we're good for the changes to frontier. At least for the searching.

Then we move the logic, and do our checks against neighbor-loc instead of location.

Now we'll find a path if it exists, or not if it doesn't, just using BFS instead of DFS. But we need to find the shortest path, which means we need to change the frontier list one last time and store some additional state there -- specifically, the number of jumps taken to get there. From the root node, there are 0 jumps, so (queue 0) becomes (queue '(0 0)) (adding the jump count to the end as a pair), and the logic is updated to deal with the new pair.

Finally the code now looks like this:

(ql:quickload :serapeum)

(shadowing-import '(serapeum:queue serapeum:enq serapeum:deq serapeum:qlen))



(defun jumpgame-bfs (input)

  (let ((frontier (queue '(0 0))) ; each node is an index and a jump-count

        (visited (list 0)))

    (loop 

      :until (zerop (qlen frontier))

      :do

      (let* ((location-cell (deq frontier))

             (location (first location-cell))

             (location-jump-count (second location-cell))

             (max-jump (elt input location)))

        (dotimes (jump max-jump) ; add neighbors if unvisited

          (let ((neighbor-loc (+ location (1+ jump))))

            (unless (or (find neighbor-loc visited)

                        (>= neighbor-loc (length input)))

              (if (eql neighbor-loc (1- (length input)))

                  (return-from jumpgame-bfs (1+ location-jump-count))) ; reached the end

              (push neighbor-loc visited) ; mark as visited

              (enq (list neighbor-loc (1+ location-jump-count)) frontier))))))))

The diff is not very much.

There is another solution to the Jump Game that doesn't explicitly use either one of these two search algorithms. I didn't come up with it, but found it over at this blog after I had solved it my way.

His solution is simpler, and maybe more clever. I had inklings of an alternative being possible but hadn't bothered trying to find it; I hoped that one of the candidates I gave the problem to would figure it out maybe because most of them immediately started with the idea of doing a single pass linear scan of the array, rather than recognizing the graph search abstraction that generally speaking could involve backtracking (just not in this problem, worst case for DFS is visiting each element of the input array once, just like this other solution, but more memory and processing is needed).

The solution if you didn't click through is to keep track of a separate piece of information "max-reachable-index" and have the insight that for each step in the array you can update it to i + A[i]. In Lisp:

(defun jumpgame-fast (input)

  (let ((max-reachable-index (elt input 0)))

    (loop 

      :for i :from 0

      :for el :across input

      :do

      (if (and (<= max-reachable-index i) (zerop el))

          (return))

      (if (> (+ i el) max-reachable-index)

          (setf max-reachable-index (+ i el)))

      (if (>= max-reachable-index (1- (length input)))

          (return t)))))

However, how does it handle Jumpgame 2? The same author has a solution.

To be honest, though the author says "the solution is similar", I don't see how. The total code is small, but the code diff itself seems huge -- pretty much nothing remains. I'm not even sure his solution actually works since I haven't tested some edge cases. I trust it does but it would require figuring out through careful thinking. The benefit of my BFS change is that it's obviously correct to return the number of plies done in the search tree once you find the end. (Implementation-wise it also ends up being faster than DFS, perhaps due to inefficiencies with how push/pop are implemented?)

Here is the code in Lisp for completion sake, it seems to work, don't ask me to explain why without thought.

(defun jumpgame2-eh? (input)

  (let ((last-reach 0)

        (reach 0)

        (step 0))

    (loop

      :for i :from 0 :below (length input)

      :while (<= i reach)

      :do

      (when (> i last-reach)

        (incf step)

        (setf last-reach reach))

      (setf reach (max reach (+ i (elt input i)))))

    (if (< reach (1- (length input)))

        0

        step)))

On the bright side, it should be slightly faster than the -bfs version some of the time. BFS can return as soon as it detects it can reach the end, though.

---

What brought this post about? I finally got around to finishing reading all of Programming as if the domain (and performance) mattered. It's worth your time too.

One of the lessons I took away from it is to be suspicious of the usual way we solve problems with programming, which is to take a problem statement, transform it to a different problem, and solve that one. That author's approach is more direct to the domain: take a problem statement, and solve things in terms of that problem's domain, rather than trying to map it to another problem right away.

The Jump Game is like that a bit I think. And yet, my observation last year when I retired the problem was that by mapping the problem to a well-known problem solving technique (searching algorithms) it becomes easier to make adjustments later on, not harder.

So in final reflection of that paper, with this jump game problem... I think some caveats might be in order. I do think that while the program creek blog author solves the problem more "directly", his solution actually isn't very domain specific. Instead of solving the question of "can I jump to the end?" that author solves the problem of "scanning each element in the input, can I continue, calculating the maximum reachable index? Oh and if the max reachable index is the end or more, then I can exit early and therefore jump to the end".

This is a useful technique to writing clean code (I can't remember where I found it, I'll edit this post if I do -- I think it may have been something Norvig wrote?). You write what you want to do in English. Then you write the code that does it. Then you write a new English rephrasing of your code, and compare with the original.

If you look at my solution, it turns "can I jump to the end?" into something like "doing a depth-first search using the rules of the game, can I reach the end?" It seems a lot closer, even if perhaps it loses a lot of the domain in the workings of the search implementation.

And most importantly, I still claim that my approach of using a general searching method is easier to extend (as shown in jump game 2).

The caveat I would have for favoring the domain solution over not is that if there is a well-trodden class of algorithm that has been successful in the past to solve problems like the one you're currently trying to solve, go ahead and use it. The difference between "computery" or "mathy" solutions that are domain-agnostic, like the one that the paper author shows off in the Haskell versions of his problem or like the blog author's jump game solutions (the first has an insight that the problem can be solved with some folding and mins or whatever, the second has an insight that the problem can be solved by keeping a running-maximum and updating that), and the "computery" solutions that are fairly domain-agnostic like my search algorithm ones, is that my search algorithm ones have a rich history as a general algorithm ("mapping a function over data" isn't a general algorithm) of useful generalization with flexibility towards change in mind. The whole field of AI is a great case study in this.

On a practical level, knowing your CS will help you get past interview whiteboard hazing more easily since with the famous algorithms you'll be able to solve a wide variety of problems so long as you can phrase them in terms of the algorithms. That's better than relying on a spur of the moment insight that your particular problem has an underlying math fact in some cases of min(x+1, i+a[i]) or whatever that you can exploit.

---

Jan 18, 2019 update, added another jumpgame implementation for fun.

(defclass union-find ()

  ((parent-lookup-table

     :accessor uf-parent-lookup-table

     :initform (make-hash-table :test #'equal)

     :documentation "Table that associates a set element (key) to its parent element (val)).")

   (subtree-size-table

     :accessor uf-subtree-size-table

     :initform (make-hash-table :test #'equal)

     :documentation "Table that associates a subtree with root element (key) to its subtree count of elements (val).")))



(defmethod uf-parent-lookup ((uf union-find) key)

  "Looks up key in uf's parent-lookup table.

   If key hasn't been added yet, sets the key's value

   to key itself and returns it."

  (multiple-value-bind (parent present?) (gethash key (uf-parent-lookup-table uf))

    (unless present?

      (setf (gethash key (uf-parent-lookup-table uf)) key)

      (setf parent key))

    parent))



(defmethod uf-subtree-size ((uf union-find) subtree)

  "Gets the size of the specified subtree. If it's not part of the

   lookup map yet, creates an entry and sets it to 1."

  (multiple-value-bind (size present?) (gethash subtree (uf-subtree-size-table uf))

    (unless present?

      (setf (gethash subtree (uf-subtree-size-table uf)) 1)

      (setf size 1))

    size))



(defmethod uf-find ((uf union-find) element)

  "Finds the root parent of the uf structure."

  (let ((parent (uf-parent-lookup uf element)))

    (if (equal parent element)

        element

        (uf-find uf parent))))



(defmethod uf-union ((uf union-find) set1 set2)

  "Makes set1 and set2 subsets of each other (if not already) by parenting the root

   of the smallest set to the other's root."

  (let ((root1 (uf-find uf set1))

        (root2 (uf-find uf set2))

        (parent-table (uf-parent-lookup-table uf))

        (size-table (uf-subtree-size-table uf)))

    (unless (equal root1 root2)

      ; make sure that root2's size is always greatest, swapping if needed,

      ; then parent root1 -> root2

      (if (> (uf-subtree-size uf root1)

             (uf-subtree-size uf root2))

          (rotatef root1 root2))

      (setf (gethash root1 parent-table)

            root2)

      ; update root2's size to be num elements unioned from root1

      (incf (gethash root2 size-table)

            (gethash root1 size-table))))

  nil)



(defmethod uf-connected ((uf union-find) cmp1 cmp2)

  "If cmp1 and cmp2 have the same root in the uf,

   then they are connected in the same subtree."

  (equal (uf-find uf cmp1)

          (uf-find uf cmp2)))



(defun jumpgame-w/-union-find (input)

  (let ((jump-uf (make-instance 'union-find)))

    (flet ((generate-neighbors (idx max-jump-len)

             (loop :for i :from idx :to (+ idx max-jump-len)

                   :collect i)))

      (loop

        :for i :from 0

        :for el :across input

        :do

        (let ((neighbors (generate-neighbors i el)))

          (dolist (neighbor neighbors)

            (uf-union jump-uf i neighbor)))))

    (uf-connected jump-uf 0 (1- (length input)))))



(jumpgame-w/-union-find #(2 3 1 1 4)) ; T

(jumpgame-w/-union-find #(3 2 1 0 4)) ; nil

---

Posted on 2018-09-14 by Jach

Tags: hiring, lisp, programming

Permalink: https://www.thejach.com/view/id/356

Trackback URL: https://www.thejach.com/view/2018/9/jump_game_as_interview_problem_domain_solutions

Back to the top