Introduction
Oh no! Another brain bender programming assignment to win a ticket to the interview. I must confess: I like them especially the ones I’ve seen from one of the modern tech giants -- not so much as a tool for finding great applicants but as a fun, interesting problem solving exercise. In this article I would like to share one that a colleague of mine was asked to solve.
What I liked about this one is it offered opportunities for some interesting alternative solutions. Unfortunately, passing is only determined by whether the solution returned all the correct values for each input – highlighting one of the drawbacks of screening this way.
Nevertheless, you may be presented with a similar problem and seeing other solutions may help with the next test. Here’s the problem and a solution in Swift. It is abridged and described slightly different from the original.
Background
Slippery Seal Trainer is trapped in an NxN grid of rooms. In each room (except the top left) is a hungry polar bear. To travel through the room and escape the jaws of the hungry bear, Trainer must feed it.
Slippery Seal Trainer begins in the top left room. There’s a door on each wall except for the ones along the perimeter. The doors are locked in a way that only permits Trainer to exit through the door below and the one on the right. Once Trainer enters a room, the bear begins to approach. Trainer must feed the hungry bear until it is full to keep it from being eaten. Trainer is an experienced trainer of zoo animals including bears and knows how much food to feed them.
To escape the confines of the grid, Slippery Seal Trainer must find his way to the bottom right room, which also has a hungry polar bear, using most of his limited food. Trainer decides to take the path leaving him with as little food as possible at the end.
Write a function remains(food, grid). It returns the amount of food Slippery Seal Trainer will have left after taking the root using the most amount of food without being eaten and ending at the bottom right room. Return -1 if no route exists without Trainer being eaten.
The grid is represented by an NxN array of integers. Each element is a room with the value identifying the amount of food required to feed the hungry polar bear to exit. The value at (0,0) is always 0 to indicate there is no bear there.
The grid size does not exceed 20, and the amount of food required to feed each hungry polar bear is a positive integer and does not exceed 10.
Some examples follow:
Example 1
Food = 7
Grid = [[0,2,5], [1,1,3], [2,1,1]]
Output 0
Example 2
Food = 12
Grid = [[0,2,5], [1,1,3], [2,1,1]]
Output 1
The algorithm requires visiting all paths from the top left corner to the bottom right in search of the one resulting in the most amount of food consumed – all of it if possible, but of course not more.
Failed paths are ones where there is insufficient food to exit.
The best path is the one where Trainer reaches the bottom right corner with just the right amount of food. Once a path is found with this condition, no further ones are required to evaluate.
Brainstorming a Solution
Solving the problem requires exhausting all the paths through a grid from the top left corner to the bottom right. It’s natural to begin to think of an algorithm that iterates through all the rows and columns with a number of nested loops.
I spent some time toying with that strategy for this article. That’s the trap that this problem sets for the candidate. If you’re lured into this approach and stay with it for too long, you may exhaust all the time without solving it.
You may even solve it with this kind of algorithm, but if you did, I wouldn’t necessarily want to bring you in for the interview. Did you ever notice that the weakest programmers create the most complicated solutions? It’s one of the paradoxes of this business.
As you begin playing in your mind with a nested approach, it becomes apparent that the number of nests required increases with the size of the grid. If you force it, like I did, it gets very frustrating very fast.
However, the silver lining in thinking about it in this way reveals the alternative strategy. As you reach a dead end, the algorithm needs to back up one room sometimes more than one and try the path it did not take. That’s not easily accomplished with nested loops if at all – especially when the size of the grid isn’t fixed.
Using Recursion
This problem immediately brought to mind my many decades old experience sitting in a Data Structures class. It was the Towers of Hanoi problem where the class learned about stacks and recursive solutions.
When you think about it, each move to an adjacent room is like starting all over at the top left corner but with a smaller matrix. Evaluation stops when the input matrix is a matrix of one or there is insufficient food remaining to continue.
Recursion is a good strategy for solving these problems because they normally can be solved in less code than a loop and a stack, and completing these tests are always time constrained. Following is a recursive function for solving the problem.
func remains (feed: Int, zombieRooms rooms:Matrix) -> Int {
let newFeed = feed - rooms.value
roomsVisited += 1
path.push(rooms.value)
guard feed > -1 else { path.pop(); return best }
if rooms.count == 1 {
if (newFeed < best || best == -1) && newFeed > -1 {
best = newFeed
optimalPath = path._stack
}
path.pop()
return best
}
guard best != 0 else { path.pop(); return best }
if rooms.width > 1 {
remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.i, j:rooms.right))
}
guard best != 0 else { path.pop(); return best }
if rooms.height > 1 {
remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.down, j:rooms.j))
}
path.pop()
return best
}
See the recursive page of the attached swift playground project.
Using a Stack
To solve this problem without recursion requires an algorithm where new paths can be evaluated by backing up to the previous room and evaluating the path not taken. The stack is the collection tool in the programmer’s arsenal to apply these techniques.
The algorithm pushes each room entered on the stack. When the path reaches success or a dead end, a room is popped off the stack to evaluate the alternative path. If the alternative path was taken, another room is popped off the stack. When there are no more rooms to pop from the stack, the exhaustive search has completed with the best path identified.
func remains (feed: Int, zombieRooms rooms:Matrix) -> Int {
var foodRemaining = feed
path.popAll()
optimalPath = path._stack
var roomsToEvaluate = true
var pop = false
var i = 0, j = 0
while roomsToEvaluate {
roomsVisited += 1
if pop {
var lastRoom = Room(i: 0, j: 0, food: 0)
if !path.isEmpty()
{ lastRoom = path.pop() }
else {
roomsToEvaluate = false;
break
}
let previousRow = i
i = lastRoom.i
j = lastRoom.j
foodRemaining = lastRoom.food
if rooms.isAtBottomRightCornerRoom(row: lastRoom.i, col: lastRoom.j)
{ continue }
else if previousRow > lastRoom.i
{ continue }
else if i + 1 < rooms.rows {
i += 1
path.push(lastRoom)
pop = false
} else
{ continue }
}
foodRemaining -= rooms.matrix[i][j]
path.push(Room(i: i, j: j, food: foodRemaining))
if rooms.isAtBottomRightCornerRoom(row: i, col: j) {
if foodRemaining >= 0 && foodRemaining < best || best == -1 {
best = foodRemaining
optimalPath = path._stack
}
pop = true
} else if foodRemaining < 0 {
pop = true
}
if j + 1 < rooms.columns
{ j += 1 }
else if i + 1 < rooms.rows
{ i += 1 }
}
return best
}
See stack page of the attached swift playground project.
When you compare the two approaches, the recursive one is simpler and easier to follow. In fact, the techniques are identical. The recursive solution is doing it implicitly on the call stack while the loop solution is explicit.
Optimizations
The only opportunity for optimizing the algorithm is to quickly identify the path leading to success where all the food is consumed. Once that path is found, no further paths require evaluation, and the method can return immediately.
Since identifying that path requires using the most food rather than the least, the choice to move across a row or down a column can be decided based upon the one requiring the most food to pass. That’s the simplified algorithm for evaluating the door to try first. It may be that factoring more information could improve the choice. An additional variable might be how much food remains. Another may be assessing how close to the corner room the current room lies. I leave that as an exercise to the reader to work with. Following is the heuristic algorithm. It chooses first the path of room requiring the most food.
func remains (feed: Int, zombieRooms rooms:Matrix) -> Int {
let newFeed = feed - rooms.value
roomsVisited += 1
path.push(rooms.value)
guard feed > -1 else { path.pop(); return best }
if rooms.count == 1 {
if (newFeed < best || best == -1) && newFeed > -1 {
best = newFeed
optimalPath = path._stack
}
path.pop()
return best
}
guard best != 0 else { path.pop(); return best }
if rooms.width > 1 && rooms.vRight >= rooms.vDown && (newFeed - rooms.vRight) > 0 {
remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.i, j:rooms.right ))
guard best != 0 else { path.pop(); return best }
if rooms.height > 1 {
remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.down, j:rooms.j ))
}
} else if rooms.height > 1 {
remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.down, j:rooms.j))
guard best != 0 else { path.pop(); return best }
if rooms.width > 1 {
remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.i, j:rooms.right))
}
} else if rooms.width > 1 {
remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.i, j:rooms.right))
}
path.pop()
return best
}
See heuristic page in the attached swift playground project.
To see how the heuristic algorithm compares to the exhaustive approach (implemented to exit when the first path is found having no food remaining) view and run the comparison page in the attached swift playground.
Matrix Manipulation
Navigating the matrix requires manipulation of the 2-diminensional array. In C, an approach of shrinking the matrix into small ones is easily accomplished by returning the pointer to the room entered. In Swift we don’t have such pointer manipulations, so a new matrix must be created from the original.
Another Swift strategy is to keep a pointer to the current top, left most room. To create a submatrix, make a copy of the original and update the origin with the location of the top, left corner room entered. For example, the origin of the first room is (0,0). When you enter the room on the right, a copy of the original matrix is made having an origin at (0,1).
See the source code file “support.swift” for details of the matrix and stack implementations.
Summary
While these tests support screening candidates, it can block some talented ones: ones that you want to hire. The experienced programmer looking to transition to a new technology domain often doesn’t have sufficient mastery of a new language or framework to solve these problems quickly enough or without the documentation by their side.
But hire them on your team, and their strengths in delivering products, solving problems creatively, authoring elegant solutions and architectures, and acquiring new technologies quickly are assets that make the experienced superstars key members of the team - fast. These are skills far more difficult to master than a new programming language or application framework.
Screening for these applicants is an area where the industry needs to improve. We leave too many former superstars untapped and underrepresented in our organizations.
If you’re a test taker, hopefully this article gives you the edge on your next application, and if you’re the test giver, it’s my hope this article inspires you to apply other techniques for screening the experienced and accomplished candidate: one that can make large contributions to your product’s success.
History
