立夫特面经（已跪，求人品）

raynorchenfr · 发表于 10-30-2015 07:30 PM

亲！马上注册或者登录会查看更多内容！

您需要登录才可以下载或查看，没有帐号？立即注册

x

本帖最后由 Sophia 于 10-30-2015 11:48 PM 编辑

公司：立夫特，粉红色标志的打车软件。
电面：
貌似是这公司的经典题了，给你一串存放着Array的表（可以视为一个N 行2列的矩阵，每一行的首数字是开启驾驶模式的时间，尾数字是关闭的时间），里面是一个司机打开“驾驶模式”的开始时间和结束时间，让你编程序算他接下来可不可以开启驾驶模式。
判断标准：
如果一个司机累计开了12个小时或以上，则他必须连续休息8小时，中间不可以重新打开驾驶模式。如果最近的累计12个小时驾驶之后有一段连续且8小时以上的休息时间，则可以打开驾驶模式。

要点：
1，问题本身不一定给的清楚，多问问题，把问题的详细要求问清楚，比如我一开始就以为这一串表是只记录24小时的，结果面试官说这可以是非常长的历史数据，而里面表示的小时数是单调递增的。比如说一个老司机就会有【2001，2004】这样的数据出现。并且司机现在的状态（是否正在驾驶）也可以随面试官的心情改变。我的面试官说假设现在司机没有开车，有一个现在的时间提供给你。

2，和面试官多说想法不会错

做法很简单，从矩阵的最后一行开始算，先遇上12个小时的累计驾驶时间则回答否，先遇上单次连续8小时以上的休息时间则回答是。

Onsite：
四轮，两轮算法两轮设计。
1. 给你一个DAG（有向无环图），再给你一个节点，找出这个节点的所有前驱结点。
要点：
面试官首先给我的问题是怎么表示这个DAG比较好，讨论了一下以后我回答用临近列表（List里面套List）。同时作出了一些假设，比如预先会提供一系列图的插入点，并且每个点的ID和临近列表的大列表里的小列表下标对应（比如说，点1它的临近列表在大列表的index = 0处）

最后讨论出的比较好的做法是用一个集合维护结果，对DAG进行深搜，达到那个节点则将前面记录下来的路径点加入集合中，随后的搜索如果走到了集合里已经有了的点，则不用继续搜而是将之前的路径加入集合中就可以了。

2.给两个非常长的还在不断读数据的数据流，如何筛选出数据流中的重叠部分？
如果数据没有规律，则必须记录下来。
后来面试官说数据会是递增的，那时候就维持两个非常短的list就好了,其中每个流读进来就和另外的一个list比对，如果找到了，则可以舍弃另外那个list的前面的所有元素。

3，设计推特。push和pull的选择是一个重点，cache怎么用是另一个

4，设计长地址变短地址。

总结：
1.还是要把算法和数据结构理解好，这家似乎不怎么考原题和类似原题的题目。
2.设计是个痛，我设计短地址的时候就被面试官各种问卡壳，因为虽然了解了其中一些原理，无奈了解得不够透彻。

之前在网上几乎完全找不到这个公司的面经让我很纠结，这里分享给大家吧。
注：已经设置了不需要权限，但是以免我设置不成功，希望管理员看到了能移除权限要求，毕竟这家的面经实在太少了。
又注：楼主还在心塞招工作中，要是有内推的各位，求个内推。