回馈本版,最有名的出租车公司onsite面经

原帖地址:mitbbs

回来查了一下没签NDA,应该没问题了。说是今天给通知,没收到说明是黄了。就是不知道他家的打车费给不给reimburse,因为不太会用他家软件,给了100刀的coupon,要求来的终点和回的起点时公司地址,自己设置的是公司地址,可是司机最后不知道怎么给我稍微改了位置,结果就TMD charge了俺的信用卡。faint。

面的是体系结构engineer

还是老原则,哥没刷完题,就随便写过几道

电面是国人哥们,问的题目不难,属于leetcode的简单题一类的。记不得了。

onsite:
1. 国人哥们,典型的问了问以前以前做的什么,然后上题目,说一个未排序的整数数组,找出所有的inversion,就是位置大但是value小的情况。例如:

9, 10, 1, 4, 100

那么应该返回4

先给了最白痴的解法,也就是n平方时间复杂度,然后主动提出可以优化,发现可能需要排序,然后被提示说先试试merge sort,忘记了,想了一会,现自己动手写一个,没写对,后来被提示说可以用递归,没时间了,把merge的顺序搞颠倒了,应该先二分逐步递归,想反了。

2. 国人老板问了问behavior问题,主要侧重你为什么要离开原来的公司,现在流行的hadoop调度体系结构区别等等。的这个问题被后面很多人多次问到,要小心,很容易掉进坑里。

3. 一个国人和一个印度人
印度人很低调,问了以前做的东西,还在apache上查了一下,发现俺没说谎后,开始问题目:
一个字母矩阵,和一个str,如何找出可能的矩阵路径组成这个str,并打印出来,其中每步只能往上下左右走。
首先确认了用recursion不会exhaust内存,然后解释了算法,把matrix变成邻接表,需要一个global变量来存之前走过的路径,被提示到没必要换成邻接表,不需要global 变量,需要个vector就好了。然后考虑到如果要倒回去,需要清理现有的vector。中间他们给提示错了,俺更正了一下,勉强psuedo code坑吧的写完了,

4. bar raiser,别的组的一个白人和一个印度人
先问你以前做了什么,最坑的时问你以前做的最失败的东西时什么。还着重扣你如何协调公司和个人的关系,为什么离开原来公司,尤其印度人比较恶心,用你刚回答的问题的答案,来反问你。俺没忍住,有点睁大眼睛跟丫郑重地说,说觉得至少信任链是公司和员工之间维系关系的纽带,公司欺骗了你,你当然有权利表示不同意见,如果不能解决,离开可以是备选项之一。后来白人开始问code题目。说给一个密码,然后给一个hashtable,里面是密码的字母的各种变体,要找出所有的可能的密码组合。又是一个recursion。给了最基本的解法,先处理第一个字母,然把密码第一个字母砍掉,剩下的recursion

followup是如果并行化,俺是做并行化的,就扯了些并行化的基本方法和思路,说,这个问题有数据依赖,所以如果并行化,要么需要数据冗余,要没需要通信,就选了每个节点处理一个字母的变体,然后broadcast给所有节点,每个节点收到后要做相应的升级和重计算,最后reduce到一个节点上。白板上写的有点乱,白人没听见broadcast,说也是recursive,俺有点晕了。解释了broadcast后

5 bar raiser 2 电面的国人哥们和一个印度人
问系统设计题目,因为俺是做后台的,所以被问到streaming的问题,和application level的tricks有点迷失方向。让设计一个能够现实某个区域有多少出租车的汇报系统。从司机的信息接收端开始。先说可以用storm,可是却是不熟悉,就改了spark-streaming,并说明spark-streaming的两个主要缺点:1.microbatch不balance,有的处理事件长,有的短,没有流控;2. 容易漏掉关键事件;

前段5-10个server足以确认了QPS是10k/s,然后每个server根据timestamp写给hdfs,spark-streaming 负责pickup 数据,处理后送给后端的RDBMS,存在表里以供查询,处理完后,把hdfs处理过的数据周期性的删除掉,分析了可能的bottleneck在前段server写给HDFS时候,因为可能造成很多小文件,还有就是HDFS是基于disk的,可以加上tachyon做内存缓存。烙印问你怎么在HDFS上存数据。我靠对俺来说,这可问到了,俺就说,要提高HDFS的performance,需要1.JBOD或是RAID5,这样可以物理上提高硬盘的读写速度,2.合并小文件,并减少replication到2个。烙印说,你可以把文件按照时间顺序存储,个人感觉,他是做BI的,是从文件的逻辑结构考虑,俺考虑的是block level,鸡同鸭讲。

还问了如何优化RDBMS的表,俺不是做数据库的,老实承认了,只给了简单的分表方法,如果表太大。说的国人大哥都打瞌睡了。心中很是尴尬。

总体感觉,很少见到这么多国人的组,挺好的,中国人团结互助才能生存下去。估计是
被烙印黑了,算了,move on,题刷几遍再说吧。