1. 什么是深度优先搜索算法
深度优先搜索（Depth-first Search）对应于广度优先搜索（Breadth-first Search），是一种可应用于树的遍历的算法，常见的深度优先遍历方式分为先序遍历、中序遍历和后序遍历。
以上定义对于从未接触树这种数据结构的人而言实在是生僻难懂，所以一图胜千言。
假设有如下一颗二叉树：
一颗二叉树
假设去掉以上1至6的数字，让你数这棵树有多少节点，一般思路是从第一行开始，然后第二行，第三行，每一行都从左至右数一遍，直至最后一行。这种思路就是广度优先搜索，如果将数节点的过程排序，则我们数节点的顺序正好对应着图中的1至6的数字。
现在我们换一个思路，每个节点左下角和右下角的连线节点我们称为左子节点和右子节点，对于左子、右子和自身三者在“被我们数”的过程中的优先级顺序可以有A(3,3) = 6种，但是我们对于左右子仍然是按照先左后右，所以A(3,3) / 2 = 3种。即：
- 自身 > 左子 > 右子（先序遍历，此处“先”对应自身的优先级）
- 左子 > 自身 > 右子（中序遍历）
- 左子 > 右子 > 自身 （后序遍历）
对于1，遍历顺序为 1 -> 2 -> 4 -> 5 -> 3 -> 6；
对于2，遍历顺序为 4 -> 2 -> 5 -> 1 -> 3 -> 6；
对于3，遍历顺序为 4 -> 5 -> 2 -> 6 -> 3 -> 1；
从以上的三种思路中可以看出，与广度优先搜索的一层层向下访问的逻辑不同，这里每次我们都要一直沿着某一条路径访问到二叉树的最底层、直至没有左右子节点，才会返回上层再继续下一优先级的访问，这是我们称之深度优先搜索的原因。
2. 什么是剪枝
树的节点有一些额外属性，在遍历树的过程中，同时判断节点的属性，并删除不符合属性要求的分支节点，称为剪枝。比如我们设置一个属性为“在广度优先遍历中的顺序”，即途中节点中的数字，我们要找出上面那颗二叉树中所有满足“广度优先顺序小于5”的节点，那么先序遍历过程为：1 -> 2 -> 4 -> 5（删） -> 3 -> 6（删），先序遍历最终结果为：1 -> 2 -> 4 -> 3。
3. 一道产品面试题：为失明者设计一个闹钟
拿到这道题之后，首先考虑四要素：
- WHO it works for——失明者
- WHAT it exactly is——闹钟
- WHEN&WHERE it should be used——日常家用
- WHY it's necessary——常规闹钟对失明者而言存在使用困难
3. 1. 第一点，产品所服务的对象，分析失明者人群具体如何分类。
失明者可以分为：
- 先天失明和后天失明
- 不完全失明和完全失明
- 儿童、成人和长者
- 等等
想到这里，我们可以和面试官尝试沟通并表达如下看法，争取获得他的认可：
- 先天失明与后天失明的区别在于失明者是否能“脑补”出一些画面，不是主要矛盾；
- 还尚存能看清闹钟的视力的失明者也不是我们产品服务的对象；
- 儿童和长者在面对闹钟时与成年人并无本质区别。
因此在大部分情况下，我们面对的是完全失明的成人。
3. 2. 第二点，产品的本质，分析产品定位的分类。
闹钟可以分为：
- 家用闹钟、随身闹钟
- 电子闹钟、指针闹钟
- 实体闹钟、软件闹钟
- 电池闹钟、充电闹钟
- 等等
- 失明者在外出时如果有获取时间等需求，可以借助外人的帮助；
- 用于手机的软件闹钟对于失明者的不友好程度可能比有按键旋钮的实体闹钟更高；
- 指针闹钟如果采用触摸指针的方式获取时间，因为反复触摸可能影响耐用性，而且指针闹钟的初衷是采用可视化反馈大部分信息，电子闹钟在应对失明者的特殊需求上更为灵活；
- 至于还是指针闹钟至于是电池闹钟还是充电闹钟，我们可以先继续向后思考。
3. 3. 第三点，产品应用场景，分析产品被使用的场景分类。
闹钟可以用于：
- 叫醒
- 提醒办事（吃药等）
- 倒计时
- 获取时间
- 等等
这些都是可能会用到的场景。
3. 4. 第四点，产品需求点，结合常规闹钟的基本功能，综述分析产品可能的潜在需求所在。
基本需求：
- 增加盲文说明及按键文字
- 获取现在的时间
- 提醒将来的时间
- 开关机
- 是否低电量
- 关闭当前闹钟
- 盲文对于失明者的使用是基本需求；
- 采用语音报时满足失明者获取时间的需求；
- 还有一些视觉反馈的非0即1功能，比如开关机、是否低电量、是否已设置闹钟、关闭当前闹钟等也需要设置触觉或者听觉反馈。
高级需求：
-
倒计时
-
整点报时
-
闹钟重复
-
语音备注闹钟
-
已有闹钟播报
-
小睡模式
-
震动提醒
-
无线充电
- 失明者无法使用一些电器的倒计时功能，比如煮饭、微波炉热菜等；
- 失明者在设置时可以语音备注“吃XX药”“做午饭”，闹钟到时提醒会一并播报语音备注；
- 闹钟重复功能可对某一定点提醒设置重复规则，比如每天重复、每周重复等；
- 失明者可以通过已有闹钟播报来查看当前设置的所有闹钟；
- 闹钟提醒后，启动小睡模式推迟5分钟再次提醒；
- 失明者因为担心闹钟吵到同居其他人等原因可设置为震动提醒；
- 闹钟如果不采用电池供电而是充电模式，在低电提醒响起后，失明者将闹钟放置在无线充电器周围，闹钟开始充电并发出反馈。
4. 结果分析
到这里，对于如何为失明者设计一个产品的问题，我们已经总结为一系列需求。
以上这类产品经理面试题，从题目逐渐分析直至得出结论的思维过程，也就是本题的考察重点所在。
回过头看上述思路，如果将原问题视为树的根节点，具体的功能点视为树的最底层节点，我们的每一次发散思维都在产生更多节点、每一次向本质分析都在增加树的深度，当我们找出当前并列的很多分析角度（也就是树的当层所有节点）之后，都会从第一个节点向下分析（深度优先搜索），直至其不符合我们的想法，便将其剔除（剪枝），一个节点及其所有子节点处理完后再分析同层次的下一个节点及其子节点。
在常规的广度优先搜索的分析方式中，每一层次都在无限发散而产生大量可能性、重要性不同的分析角度都需要一并发散，产生大量无用功（比如我们甚至要分析指针闹钟拨指针时的盲文怎么设计等等），直至可能性众多庞杂使我们无法继续向下层分析。
相比较而言，我们可以发现，深度优先搜索+剪枝这样一边发散、一边精简可能性、并将结论反馈到同层下一个分析角度的分析问题的思维方法，能避免无用功、帮助收拢发散的思路、维持分析问题逻辑的一致性。
网友评论