# Monthly Archives: February 2013

I decided yesterday to put in some practice by tackling the Tower of Hanoi problem. The problem is a very common one that I’ve seen all over the web but until now I hadn’t taken the time to work it out.

The problem begins as three pegs on which discs can be placed. The discs are placed in decreasing order of size to create a pyramid of n height on peg 1 and the task is to move the discs from peg 1 to peg 3. The constraint of the problem is that a larger sized disc cannot be placed on top of a smaller disc.

Creating an array for each of the three pegs and notating each disc as an integer from 1 – n depending on size gave me a representation of the problem. The beginning of the problem looked like so:

tower1 = [n,n-1,…,4,3,2,1]
tower2 = []
tower3 = []

I then began to map out the base cases for the problem:

N = 1, 1n move from tower 1 to tower 3:
1 disc from tower 1 to tower 3

N = 2, 2n move from tower 1 to tower 3:
1n move from tower 1 to tower 2
1 disc from tower 1 to tower 3
1n move from tower 2 to tower 3

N = 3, 3n move from tower 1 to tower 3:
2n move from tower 1 to tower 2
1 disc from tower 1 to tower 3
2n move from tower 2 to tower 3

If we notate the towers as origin, destination, and buffer, we begin to see the pattern:

origin to buffer
origin to destination
buffer to destination

Also we see that the problem lends itself to recursion easily because for a 3 height tower there are just two 2 height tower sub-problems, for a 4 there are two 3 height tower sub-problems, etc.

Given this fact, we can work together a recursive solution using normal arrays:

``` ```
``````# Define a move
def move(origin, dest)
if dest.empty? || origin[-1] < dest[-1]
dest.push(origin.pop)
end
end

# The recursive solution
def move_tower(n, origin, dest, buffer)
if n == 1
move(origin, dest)
else
move_tower(n-1, origin, buffer, dest)
move_tower(1, origin, dest, buffer)
move_tower(n-1, buffer, dest, origin)
end
end

tower1 = [6,5,4,3,2,1]
tower2 = []
tower3 = []

move_tower(6, tower1, tower3, tower2)
# Result is tower3 = [6,5,4,3,2,1]
``````

The move ensures we don't make an illegal move by making sure the target stack is either empty or has a larger disc than what we are moving. The solution takes in the height, and the three towers that we create and solves the problem recursively.

The solution is was quite fun to puzzle through by finding the pattern in the cases and modeling a solution to reflect that pattern. There is also an iterative solution that takes into account the fact that odd and even numbered towers have different solutions with set repeating moves. I will try to tackle that one in the future!

The River Problem:

You are a person trying to cross a river and reach the land on the other side, however you cannot swim.

There are rocks in the water which you can step on to allow you to cross the river, however you start at speed 0 and can only increase your speed by 1, decrease it by 1, or maintain the same speed for each step that you take. You cannot have a negative speed (go backwards).

Given a string representing rocks (“*”) and water (“~”) write a method to return True or False depending on whether any path exists across the river.

``````Examples

River: *****~~*~~~*~~~~*~*~~*** -> true
Steps: 011_2__3___4____5_____6 Success

River: ****~~~~~~~~~~~~** -> false
Steps: 01_2__3 Failure
``````

~~~~~~~~~

This problem, courtesy of Sitong, was an interesting programming challenge we tried to tackle yesterday. The problem itself is a bit unique as it represents a sort of tree traversal problem where we have a series of possibilities (accelerate, decelerate, or maintain constant speed) at every step and search the tree for a valid solution. Given that it is a tree traversal problem, the most basic approach would be recursive.

I have always favored iteration over recursion when I program just because of the way my mind things, but recursive solutions tend to be easy to read and relatively short. However the catch with recursion I always am wary of is issues with run-time, but we’ll get to that problem later!

The solution that we both came up with (myself with a little prodding from Sitong) was one of tree traversal. My solution in ruby follows:

``````def can_cross_river?(river, loc, speed)

# base-case success if we reach land
return true if loc + speed + 1 > river.length

# If we landed on another rock, try 3 steps recursively

# Accelerate first every time so we get the fastest path across
if river[loc + speed + 1] == "*"
return true if can_cross_river?(river, loc + speed + 1, speed + 1)
end
# If accelerating fails try maintaining speed for this step
if speed > 0 && river[loc + speed] == "*"
return true if can_cross_river?(river, loc + speed, speed)
end
# If maintaining speed fails try slowing down
if speed > 1 && river[loc + speed - 1] == "*"
return true if can_cross_river?(river, loc + speed - 1, speed - 1)
end
return false
end
``````

The code checks every path possible starting with the fastest and looks for the first successful run. However, when calculating the run time of this path we ran into some interesting caveats. The initial bound of run time when I first looked at the problem was O(3^n) because the problem recursively results in 3 possible choices for each path. For n choices this results in 3^n paths. However that is merely an upper-bound, as the tree depth shortens as we accelerate in speed and reach the goal faster. Therefore we will have significantly less than 3^n possible paths. I don’t think I can mathematically calculate this bound of worst-case but my intuition can be captured in the figure below:

The triangle represents a normal 3^n tree of possibilities but the grey shaded area represents the area of this problem as we accelerate when we take a right branch and reach a true or false conclusion faster. We cannot go slower than 1 speed so we don’t have any branches that go left from the origin.

There are other solutions for this problem and other optimizations including memoization or caching, however those also have issues. This problem is unique as for each sub-problem while we may face the same remainder of the river, we might approach this at a different speed. Thus caching will involve a huge problem space and questions of efficiency arise. I think this problem was great fodder for the mind however and provided a lot of interesting food for thought. I also asked David the same problem and saw a completely different approach to solving it, however we haven’t figured out the details on how to efficiently tackle the problem from his angle yet. Perhaps if we do I will write another post comparing his solution and this solution.

After a few interviews, I’ve decided to begin writing for myself an interview memorandum to reflect upon improvements and strategies for the next ones. This one I feel like laying out a framework for approaching case interviews.

1. Start off by clarifying goals and results. The most important part for a case is understanding what the desired result is. Whether I’m designing a data system, formulating a solution, or estimating effects, I should understand what the overarching goal is before I even start to walk through my thinking. Who is my interviewer supposed to be? What information can they provide?

2. I tend to work in a iterative fashion as I walk through cases which lends itself to train of thought syndrome. Framework. I should lay out and notate a framework. Start from the beginning. List assumptions, available resources. List the goal and sub-goals that can be derived from that goal. Do not begin to talk about a solution before laying down this framework. My initial solution tends to change as I work through a problem and to mitigate that I can work through the problem on paper and the first solution I explain can at least be a fourth or fifth draft in my mind.

3. Immediately consider these questions as I’m working:
``` 1. What are the advantages to this system? How can it be extended? How generalized is it? 2. What are the disadvantages to this system? What can it not measure? 3. How can this system work with extensions? Other systems? 4. If data-based, what do I track and measure and what do I not know? Can I get the information I don't know? Does it fit into the current scheme? 5. Think about the goal. Does this solve that problem? Does it scale to this problem? Are there any tangential goals that might be in question? 6. What company am I interviewing for and what does this question have to do with the company? What are the parallels and what should I focus on as I explain my solution? ```

4. Breathe. Take time and slow down. I’ve always had a habit on essay tests to just start writing. In class I never take notes and I work from memory. While this approach serves me well internally, I need to highlight my strengths in problem solving in a way that can be followed by the interviewer. Go back to the outline. Go back to the notes. Go back to the goal and review it again. I need to slow down and keep reviewing, move at a deliberate but more coherent and complete pace.

5. When working with data, lay out the specifics. Write down the tables, the relationships and the storage. This might not need to be conveyed during to the interviewer depending on position, but having this laid out provides the organization for explaining what data can be derived from the system.

6. Define the results and capabilities of the system that you’ve designed. Understand its flaws and think through its implementation. Important aspects: scaling, use case, expandability, applications, edge cases, any missing information? Always think about edge cases and the world view of the problem, don’t fall into the trap of assuming the topic, whether a store, business, or other, reflect the first example that comes to mind. Think of other environmental or confounding factors that may change the optimal design.

I may come back and add and edit this as I learn more. It’s important in all circumstance to always keep learning from any situation. Until the next one!