通过编程作业进行候选筛选
5.00/5 (3投票s)
编程测试经常用于筛选求职者。本文介绍了一家大型现代科技公司给出的一道题目及其 Swift 解决方案。
引言
哦不！又一项烧脑的编程作业，才能赢得面试的入场券。我必须承认：我喜欢它们，尤其是从一家现代科技巨头那里看到的那些——它们不那么像是寻找优秀应聘者的工具，而是作为一种有趣、有趣的解决问题练习。 在本文中，我想分享一个我的同事被要求解决的问题。
我喜欢这个题目的一点是它提供了进行一些有趣的替代解决方案的机会。 遗憾的是，是否通过仅仅取决于解决方案是否为每个输入返回了所有正确的值——这突显了这种筛选方式的一个缺点。
尽管如此，你可能会遇到类似的问题，看到其他解决方案可能会帮助你应对下一次测试。 这是问题以及 Swift 解决方案。 它经过删减，描述方式与原文略有不同。
背景
“Slippery Seal Trainer”（滑溜的密封训练师）被困在一个 NxN 的房间网格中。在每个房间（除了左上角）都有一只饥饿的北极熊。要穿过房间并逃离饥饿北极熊的爪子，训练师必须喂饱它。
滑溜的密封训练师从左上角的房间开始。 除了周边墙壁外，每面墙上都有一扇门。 门被锁定的方式只允许训练师从下面的门和右边的门出去。 一旦训练师进入一个房间，熊就开始靠近。 训练师必须喂饱饥饿的熊，直到它吃饱为止，才能避免被吃掉。训练师是动物园动物（包括熊）的经验丰富的训练师，他知道该喂它们多少食物。
为了逃离网格的限制，滑溜的密封训练师必须找到通往右下角房间的路，那里也有一只饥饿的北极熊，并利用他有限的食物。训练师决定选择一条让他最后食物最少的路。
编写一个函数 `remains(food, grid)`。 它返回滑溜的密封训练师在采取消耗最多食物（但不被吃掉）并最终到达右下角房间的路径后剩余的食物量。如果不存在不被吃掉的路径，则返回 -1。
网格由 NxN 个整数数组表示。每个元素是一个房间，其值表示喂饱饥饿的北极熊以逃脱所需的食物量。 (0,0) 的值始终为 0，表示那里没有熊。
网格大小不超过 20，并且喂饱每只饥饿的北极熊所需的食物量为正整数，不超过 10。
以下是一些示例
示例 1
食物 = 7
网格 = [[0,2,5], [1,1,3], [2,1,1]]
输出 0
示例 2
食物 = 12
网格 = [[0,2,5], [1,1,3], [2,1,1]]
输出 1
该算法要求遍历从左上角到右下角的所有路径，以找到消耗食物最多的路径——如果可能的话，消耗所有食物，但当然不能超过。
失败的路径是指食物不足以逃脱的路径。
最佳路径是训练师到达右下角时食物量刚刚好的那条路径。 一旦找到符合此条件的路径，就不需要再评估其他路径了。
构思解决方案
解决问题需要遍历从左上角到右下角的所有路径。 自然地，人们会想到一个算法，通过嵌套循环来遍历所有行和列。
我在本文中花了些时间研究这种策略。 这正是这个问题为应聘者设下的陷阱。如果你被这种方法吸引，并在此停留太久，你可能会耗尽所有时间而无法解决它。
你甚至可能用这种算法解决了问题，但如果你这样做了，我未必想让你来面试。 你有没有注意到，最弱的程序员往往会创造出最复杂的解决方案？ 这是这个行业的一个悖论。
当你在脑海中尝试嵌套方法时，你会发现所需的嵌套层数会随着网格的大小而增加。 如果你强行这样做，就像我一样，会很快变得非常沮丧。
然而，通过这种方式思考的启示在于揭示了另一种策略。当你到达死胡同时，算法需要后退一个房间，有时是多个房间，并尝试未采取的路径。 这很难通过嵌套循环来实现，如果可以的话，尤其是当网格大小不固定时。
使用递归
这个问题立刻让我想起了我在数据结构课上几十年的经验。 那是汉诺塔问题，我们在课上学习了堆栈和递归解决方案。
仔细想想，移动到相邻房间就像从左上角重新开始，但使用一个更小的矩阵。 当输入矩阵为 1x1 或剩余食物不足以继续时，评估就会停止。
递归是解决这些问题的有利策略，因为它们通常可以用比循环和堆栈更少的代码解决，而完成这些测试总是时间受限的。 以下是解决该问题的递归函数。
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
}
请参阅附带的 Swift Playground 项目的递归页面。
使用堆栈
要在没有递归的情况下解决此问题，需要一种算法，通过回退到前一个房间来评估新路径，并评估未采取的路径。 堆栈是程序员工具箱中的集合工具，用于应用这些技术。
该算法会将进入的每个房间推入堆栈。 当路径成功或达到死胡同时，会从堆栈中弹出一个房间以评估另一条路径。 如果选择了另一条路径，则会从堆栈中弹出另一个房间。 当堆栈中没有更多房间可弹时，将完成穷举搜索并识别出最佳路径。
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
}
请参阅附带的 Swift Playground 项目的堆栈页面。
当你比较这两种方法时，递归方法更简单，更容易理解。 事实上，技术是相同的。 递归解决方案是在调用堆栈上隐式执行，而循环解决方案是显式执行的。
优化
优化算法的唯一机会是快速识别所有食物都被消耗掉的成功路径。 一旦找到该路径，就不需要再评估其他路径，方法可以立即返回。
由于识别该路径需要使用最多的食物而不是最少的食物，因此根据消耗食物最多的那一个来决定跨行或向下列移动。 这是评估首先尝试的门的简化算法。 因子化更多信息可能会改进选择。 另一个变量可能是剩余多少食物。 另一个可能是评估当前房间离角落房间有多近。 我将把它作为一项练习留给读者去探索。 以下是启发式算法。 它首先选择消耗食物最多的房间路径。
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
}
请参阅附带的 Swift Playground 项目中的启发式页面。
要查看启发式算法与穷举方法（实现为找到第一条不剩余食物的路径时退出）的比较，请查看并运行附带的 Swift Playground 中的比较页面。
矩阵操作
导航矩阵需要对二维数组进行操作。 在 C 语言中，通过返回进入房间的指针可以轻松地将矩阵缩小为小矩阵。 在 Swift 中，我们没有这样的指针操作，因此必须从原始矩阵创建一个新矩阵。
另一种 Swift 策略是保留当前左上角房间的指针。 要创建子矩阵，请复制原始矩阵，并将原点更新为进入的左上角房间的位置。 例如，第一个房间的原点是 (0,0)。 当你进入右边的房间时，会创建一个原始矩阵的副本，其原点位于 (0,1)。
有关矩阵和堆栈实现的详细信息，请参阅源文件“support.swift”。
摘要
虽然这些测试支持筛选候选人，但它可能会阻碍一些有才华的候选人：那些你希望聘用的人。 寻求转向新技术领域的经验丰富的程序员通常没有足够精通新的语言或框架，因此无法足够快地解决这些问题，或者没有文档在身边。
但是，如果将他们聘入你的团队，他们在交付产品、创造性地解决问题、编写优雅的解决方案和架构以及快速掌握新技术方面的优势，将使经验丰富的超级明星迅速成为团队的关键成员。 这些技能比掌握一门新编程语言或应用程序框架要困难得多。
为这些应聘者进行筛选是行业需要改进的领域。 我们让太多曾经的超级明星未被发掘，在我们的组织中代表性不足。
如果你是一名应试者，希望本文能让你在下次申请中占得优势；如果你是出题者，我希望本文能启发你采用其他技术来筛选经验丰富、成就卓著的候选人：他们能够为你的产品成功做出巨大贡献。
历史
- 2017 年 2 月 27 日 - 发布