The internet is a great for people with streamofconsciousness thinking. Today that is me.
Over the last few days I have been playing a lot with Mongodb. Mongodb is one of those products that looks pretty amazing, and having played with it a bit I think it is pretty amazing if applied to the right problem.
One of the things I have been trying to do more when I find a cool project is learn about the people behind the technologies. In the case of Mongodb, one of the developers who wrote the book on Mongodb is Kristina Chodorow. I Googled her name and discovered her blog (cutely named “snail in a turtleneck“).
Turns out our Mongodb hero has just accepted a job with Google! Awesome for her. One of the posts she did that caught my eye was The Google Interviews post. Being on the hiring team for Schweitzer Engineering Laboratories I am often looking for good interview questions. Google, Microsoft, and the other “big companies” are know for having hard interview questions, so I was excited to see the questions they asked her.
The treelike thing wasn’t too hard. I could program up a recursive solution for that in 15 minutes I think. It would be harder for me to do it iteratively, just because I haven’t done that in a bit. The power series question is interesting, and the part I haven’t figured out yet is how to avoid continual calls to next() in the second series as I foil out that expressions, but I will figure it out. Reversing the bytes in an int isn’t too bad nor is the subsets one. atoi is also straightforward (and maybe I will do another post on my solution to it). The longest substring of two distinct characters seemed easy though I completely messed it up when I tried to write it because my solution didn’t handle skipping intermediate letters correctly (yet another post?).
The problem that definitely caught my eye was:
Suppose you are on a Cartesian coordinate system. Find all paths from (0,0) to (m,n) that only go through each point once. For example, if you were given m=2, n=2, you’d have the following:
This would be one possible path:
Return the number of possible paths. Then extend for negative coordinates.
All credit goes to http://www.kchodorow.com/blog/2013/03/04/thegoogleinterviews/ for this, as I am copying it, and the images, verbatim from her.
This problem seemed really hard. I figured out in my head that for a 1 by 1 there were 2 solutions, and for a 1 x 2 I figured there were 4 solutions. I couldn’t figure out what the solution for a 2 x 2 was. I was guessing around 10. Turns out it is 12.
I kept thinking about this issue and how hard the problem seemed, but most likely I was just missing something. I decided to try to code up a solution to the problem, and it was an adventure. I published my script at my github account. Its pretty cool if I do say so myself as it actual finds the number of solutions and shows you them. Here is an example:
python path_finder.py s 2 2
0 1 2

3 4 5

6__7__8
0 1 2

3 4__5
  
6__7 8
0 1__2
  
3 4 5
  
6__7 8
0 1 2

3__4 5

6 7__8
0 1 2

3__4__5

6 7 8
0 1__2
  
3__4 5

6 7 8
0__1 2

3 4 5

6 7__8
0__1 2

3 4__5

6 7 8
0__1 2

3__4 5

6__7__8
0__1__2

3 4 5

6 7 8
0__1__2

3 4__5

6 7__8
0__1__2

3__4__5

6__7__8
Found: 12 solutions
This is cool, but I can’t really see a pattern as to how to do this correctly yet in a closeform solution. I ran the script with various inputs and recorded the outputs:
For a 2×2 version, there are 12 solutions.
For a 2×3 version, there are 38 solutions.
For a 2×4 version, there are 125 solutions.
For a 2×5 version, there are 414 solutions.
For a 2×6 version, there are 1369 solutions.
This, while highly interesting, wasn’t helping me find the close form solution I was looking for. I turned to Google and search for those numbers. I found a few interesting pages including http://mathworld.wolfram.com/SelfAvoidingWalk.html and http://www.iwriteiam.nl/Crook_path.html that talked about what they refer to as “The rook path problem”.
Unfortunate that I had to write a script to generate the numbers to give me a search criteria that actually returned something related to this problem, but life is always interesting.
Wolfram does have some interesting generating functions and recurrence relations for this family of problem.
In summary, I still don’t know what Kristina said in response to the Cartesian Coordinate problem, and I don’t know what I would have said, but I am pretty sure I wouldn’t have gotten it right since I still don’t know an easy way I can find the number of possible paths knowing m and n :(.