Click here to Skip to main content
13,139,254 members (54,484 online)
Click here to Skip to main content
Add your own
alternative version

Stats

6.3K views
40 downloads
7 bookmarked
Posted 27 Feb 2017

Candidate Screening with a Programming Assignment

, 19 Mar 2017
Rate this:
Please Sign up or sign in to vote.
Programming tests are frequently used to screen job applicants. This article describes one problem given by a large modern technology company and its solution in swift.

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  // calculate food remaining when visiting this room

    roomsVisited += 1  // a statistic to calculate number of rooms visited before a path was found

    path.push(rooms.value)  // push this room on the stack so we can print the successful path

    // no food left return and pop the room off the stack
    guard feed > -1 else { path.pop(); return best }  

    /*  if reached the bottom right corner room then check if this is the best path evaluated yet
     */

    if rooms.count == 1 {

        /*  if remaining food is the lowest calculated or it's the first successful path found 
              then save the path and store the remain food as the new benchmark to beat.
         */

        if (newFeed < best || best == -1)  && newFeed > -1 {

            best = newFeed

            optimalPath =  path._stack

        }

        path.pop()  // backtrack to evaluate the path beginning at the previous room.

        return best

    }


    // if a path was found leaving no food, then no other paths need to be evaluated.
    guard best != 0 else { path.pop(); return best }

    // move to the room to the right if there is one.
    if rooms.width > 1 {

        remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.i, j:rooms.right))

    }

    // if a path was found leaving no food, then no other paths need to be evaluated.
    guard best != 0 else { path.pop(); return best }

    // move to the room below if there is one
    if rooms.height > 1 {

        remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.down, j:rooms.j))

    }

    // all paths from this room have been evaluated so backtrack
    path.pop()

    // return the value of the current best path.
    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 // initialize remaining food to the value of the input

    path.popAll() // empty the path stack

    optimalPath = path._stack // initialize the optimal path stack to the empty path stack

    var roomsToEvaluate = true  // controls the termination of the evaluation loop

    var pop = false  // initialize so that nothing is popped off the stack

    var i = 0, j = 0  // begin at the top left corner of the matrix

    while roomsToEvaluate {  // continue while there are no more rooms to evaluate

        roomsVisited += 1  // statistic for rooms evaluated

        // if backtracking to the previous room
        if pop {

            var lastRoom = Room(i: 0, j: 0, food: 0)  // initialize last room

            /* if there are previous rooms then pop the room off the stack; otherwise, 
                   there are no paths remaining to evaluate and terminate the loop
            */
            if !path.isEmpty()

                { lastRoom = path.pop() }

            else {

                roomsToEvaluate = false;

                break

            }

            let previousRow = i  // save the row of the room currently evaluated

            // set the matrix indices to the backtracked room and restore the 
            //   food remaining when in that room
            i = lastRoom.i

            j = lastRoom.j

            foodRemaining = lastRoom.food

            // if at bottom right, pop again
            if rooms.isAtBottomRightCornerRoom(row: lastRoom.i, col: lastRoom.j)

                { continue } // Pop again

            else if previousRow > lastRoom.i

                /*   if right and bottom paths have been evaluated 
                        from the previous room then backtrack again
                 */

                { continue }  // Pop again

            else  if i + 1 < rooms.rows {  // if there is a room below to evaluate, then move to it

                // move down to the next row and evaluate the path by stoping the backtracking.

                i += 1

                path.push(lastRoom)

                pop = false

            } else  //  backtrack again, there is no path off the last room to evaluate

                { continue }  // pop again

        }

        foodRemaining -= rooms.matrix[i][j]  // calculate remaing food when visiting this room

        path.push(Room(i: i, j: j, food: foodRemaining))  // push this room on the stack

        // if at bottom right most corner than determine if this was a successful path
        if rooms.isAtBottomRightCornerRoom(row: i, col: j) {

            // if this is the best path so far or it's the first time a best path 
            //    was evaluated then save it.
            if foodRemaining >= 0 && foodRemaining < best  || best == -1 {

                best = foodRemaining

                optimalPath = path._stack

            }

            pop = true  // indicate to backtrack to evaluate more paths

        } else if foodRemaining < 0 {

            // if all the food is gone, then backtrack
            pop = true

        }


        if j + 1 < rooms.columns   // move right first if there is a room to

            { j += 1 }

        else if i + 1 < rooms.rows  // move down if there is a room to move to

            { i += 1 }

    }

    return best  // return the food remaining for the best path evaluated

}

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 // calculate food remaining when visiting this room

    roomsVisited += 1 // a statistic to calculate number of rooms visited before a path was found

    path.push(rooms.value) // push this room on the stack so we can print the successful path

    // no food left return and pop the room off the stack
    guard feed > -1 else { path.pop(); return best } 

    /*  if reached the bottom right corner room then check if this is the best path evaluated yet
     */    
    if rooms.count == 1 {

        /*  if remaining food is the lowest calculated or it's the first successful path found then 
               save the path and store the remain food as the new benchmark to beat.
         */
        if (newFeed < best || best == -1)  && newFeed > -1 {

            best = newFeed

            optimalPath =  path._stack

        }

        path.pop() // backtrack to evaluate the path beginning at the previous room.

        return best

    }

    // if a path was found leaving no food, then no other paths need to be evaluated.
    guard best != 0 else { path.pop(); return best }

    /*  Decide to take the right path first or the bottom if it has more food
    */
    if rooms.width > 1 && rooms.vRight >= rooms.vDown && (newFeed - rooms.vRight) > 0 {

        // Evaluate the path
        remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.i, j:rooms.right ))

        // if a path was found leaving no food, then no other paths need to be evaluated.
        guard best != 0 else { path.pop(); return best }

        // move to the room below if there is one
        if rooms.height > 1 {

            remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.down, j:rooms.j ))

        }

    } else if rooms.height > 1 {

        // Evaluate the path
        remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.down, j:rooms.j))

        // if a path was found leaving no food, then no other paths need to be evaluated.
        guard best != 0 else { path.pop(); return best }

        // move to the room to the right if there is one.
        if rooms.width > 1  {

            remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.i, j:rooms.right))

        }

    } else if rooms.width > 1 {     // move to the room to the right if there is one.

        // Evaluate the path
        remains(feed: newFeed, zombieRooms: Matrix(matrix:rooms.matrix, i:rooms.i, j:rooms.right))

    }

    // all paths from this room have been evaluated so backtrack
    path.pop()

    // return the value of the current best path.
    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

  • 2/27/17 - Published

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Will J Miller
Program Manager
United States United States
No Biography provided

You may also be interested in...

Pro
Pro

Comments and Discussions

 
GeneralGraphtheory Pin
Sebastian Lei19-Mar-17 22:20
memberSebastian Lei19-Mar-17 22:20 
QuestionSnippets Pin
Nelek19-Mar-17 19:52
protectorNelek19-Mar-17 19:52 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.170915.1 | Last Updated 19 Mar 2017
Article Copyright 2017 by Will J Miller
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid