滴滴算法二面凉经

面试官迟到半个多小时，上来先3个智力题：

1. abcd四个人过桥时间分别为10，5，2，1分钟，但是桥最多同时两个人通过。他们在晚上过河，必须照明，但只有1把火把，问什么方案过河时间最短？

先答了简单方案19分钟，让优化，想了半天说17分钟以及方案，让给出思考的思路过程，给出思路后反问，然后解释。

2. 口袋里有n种球，每种球数量无限，每次随机取出1个球，问n种球全部取出的所用次数的期望？

这个我回答：恰好n次的概率乘n，恰好n+1次的概率乘n+1，以此类推，使用无穷级数求和，他说太暴力，再优化，答不上来，到这里心态有点稳不住了

3. 两个容器容量为a、b，只能相互倒水、全部倒出、装满，问如何判断能否取到k的水？

这个我先说暴力求解，用宽度优先搜索，问我终止条件，我说搜到k则返回true，做记忆化，遇到相同情形跳过，所有情形走完后都没遇到k则false。让用非暴力方法，我说思路，相互倒水相当于取模运算，不断进行取模如果能得到k则true，所有情况走完都不能得到k则false，他说思路接近了，循循善诱，最后还是没想出来😅

最后就是深入拷打项目，根据我做的东西问原理性的东西，每次答完都找我的漏洞反问，最后好多没答上来，直接心态崩了说不知道。十分钟后遗憾短信。

# 滴滴面经