a*****s 发帖数: 1121 | 1 回来查了一下没签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,题刷几遍再说吧。 |
b**********5 发帖数: 7881 | 2 你最后一道题, 都没说到点子上吧。。。
首先, 你他妈的干嘛要存在HDFS里? 要存, 也要存在Hbase、cassandra里啊。。。
然后你这input data {logitutde, lagitude, driverID} 拿到以后, 怎么算某个区
域有多少出租车啊? 主要讲这个吧。。。 |
s**x 发帖数: 7506 | 3
嗯,所有的题楼主都没做对,不被拒没有任何理由阿。基本都没抓住要点,给提示也不
follow.
人家给提示的时候每个字都很重要。
这些题leetcode 都有吧?
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你最后一道题, 都没说到点子上吧。。。 : 首先, 你他妈的干嘛要存在HDFS里? 要存, 也要存在Hbase、cassandra里啊。。。 : 然后你这input data {logitutde, lagitude, driverID} 拿到以后, 怎么算某个区 : 域有多少出租车啊? 主要讲这个吧。。。
|
a********c 发帖数: 3657 | |
a*****s 发帖数: 1121 | 5 这就是操纵k-v pair,先做个{logitude,lagitude}对应的regionID检查,最后做个
reduce给出(regionID,No.of Cars) 不就是了,当时也这么答了,但是感觉问的是系
统设计。
HBase和Cassendra不也是存在HDFS上么。 :)
俺写系统软件地,多写application没啥感觉。
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你最后一道题, 都没说到点子上吧。。。 : 首先, 你他妈的干嘛要存在HDFS里? 要存, 也要存在Hbase、cassandra里啊。。。 : 然后你这input data {logitutde, lagitude, driverID} 拿到以后, 怎么算某个区 : 域有多少出租车啊? 主要讲这个吧。。。
|
s**x 发帖数: 7506 | 6
系统设计应该考的是你大概用多少台机器,几个tier ? 为什么要这样做,这么做解决
什么瓶颈?
一台机器够吗?哪里会是瓶颈?
求region id 应该不是他们的答案,因为region id 极有可能根本不是固定的,比如打
车,用户出现的地方就是要求的区别。
怎么存储也很重要,内存数据结构,quad tree , special index 都是很好的话题。
系统设计可以扯很多,确实很显水平。
【在 a*****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这就是操纵k-v pair,先做个{logitude,lagitude}对应的regionID检查,最后做个 : reduce给出(regionID,No.of Cars) 不就是了,当时也这么答了,但是感觉问的是系 : 统设计。 : HBase和Cassendra不也是存在HDFS上么。 :) : 俺写系统软件地,多写application没啥感觉。
|
c****2 发帖数: 83 | 7 不是
【在 a*****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这就是操纵k-v pair,先做个{logitude,lagitude}对应的regionID检查,最后做个 : reduce给出(regionID,No.of Cars) 不就是了,当时也这么答了,但是感觉问的是系 : 统设计。 : HBase和Cassendra不也是存在HDFS上么。 :) : 俺写系统软件地,多写application没啥感觉。
|
a*****s 发帖数: 1121 | 8 good point.
但是说俺全答错,有点绝对了。不过无所谓,探讨问题吗,闻者足戒。
region 如果是在map上的话,在相对一段时间内是固定的,可以从某个table上根据划
分查出来的。
用spark-streaming只要读个database的RDD就是了。
瓶颈在系统设计里面永远是个相对概念,是相对于你的上层用户,下层系统,和实际
SLA来说的。如果你用MapReduce解决不了,latency太长,那么瓶颈在这里,换其他计
算平台,实在不行你可以自己写MPI代码。所有“瓶颈”无非是两个方面,时间和空间
,因为图灵机就是一个读写头和纸带。所有系统都是图灵机的实现。
扯再多都是如何根据具体问题优化你当前的图灵机。
好的设计是你能通过对机器来满足你的SLA,你懂得越低层,你的power就越大,实在不
行咱不用现在主流设计,从头来自己搞一套,当然money driven的公司是绝对不允许你
这么干的。解决近期问题就行。不care你用啥。
【在 s**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 系统设计应该考的是你大概用多少台机器,几个tier ? 为什么要这样做,这么做解决 : 什么瓶颈? : 一台机器够吗?哪里会是瓶颈? : 求region id 应该不是他们的答案,因为region id 极有可能根本不是固定的,比如打 : 车,用户出现的地方就是要求的区别。 : 怎么存储也很重要,内存数据结构,quad tree , special index 都是很好的话题。 : 系统设计可以扯很多,确实很显水平。
|
o******0 发帖数: 105 | 9 第一题对应哪一道leetcode题呀?
【在 s**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 系统设计应该考的是你大概用多少台机器,几个tier ? 为什么要这样做,这么做解决 : 什么瓶颈? : 一台机器够吗?哪里会是瓶颈? : 求region id 应该不是他们的答案,因为region id 极有可能根本不是固定的,比如打 : 车,用户出现的地方就是要求的区别。 : 怎么存储也很重要,内存数据结构,quad tree , special index 都是很好的话题。 : 系统设计可以扯很多,确实很显水平。
|
h*****a 发帖数: 52 | |
|
|
s**x 发帖数: 7506 | 11
http://www.geeksforgeeks.org/counting-inversions/
其实这题不容易。
【在 o******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题对应哪一道leetcode题呀?
|
s*****3 发帖数: 87 | |
v******l 发帖数: 60 | |
s*****3 发帖数: 87 | 14 不知道问你inversion问题的国人哥们上不上mitbbs,这题并不容易。我给了个二分查
找树的算法,人家并不满意,因为worst case是n^2.
另外,并不一定只是老印黑了你。我也是上周面的。问了recruiter面试反馈,说是国
人哥们和老印那两轮有concerns。不过我马上move on了,毕竟没达到人家的bar。
【在 a*****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 回来查了一下没签NDA,应该没问题了。说是今天给通知,没收到说明是黄了。就是不 : 知道他家的打车费给不给reimburse,因为不太会用他家软件,给了100刀的coupon,要 : 求来的终点和回的起点时公司地址,自己设置的是公司地址,可是司机最后不知道怎么 : 给我稍微改了位置,结果就TMD charge了俺的信用卡。faint。 : 面的是体系结构engineer : 还是老原则,哥没刷完题,就随便写过几道 : 电面是国人哥们,问的题目不难,属于leetcode的简单题一类的。记不得了。 : onsite: : 1. 国人哥们,典型的问了问以前以前做的什么,然后上题目,说一个未排序的整数数 : 组,找出所有的inversion,就是位置大但是value小的情况。例如:
|
a*****s 发帖数: 1121 | 15 hadoop engineer
【在 v******l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉挺难得,LZ面得什么职位?
|
a*****s 发帖数: 1121 | 16 恩,无所谓了,他家recruiter死气白咧的让俺去面试。俺想给人个面子吧。
本来系统设计这个东西,都是用现有技术先最快做出一个可以用的蓝本,然后再到生产
环境中去检验的,发现那里有瓶颈,根据反馈出的信息来进行定位并解决瓶颈。你们那
么多人多长时间解决的问题,要俺45分钟内给分析出个一模一样的来,老实说,俺要现
在有这本事,也不来这面了。
跟一个以前拿过他家offer的小弟聊了,要察言观色,看人家想你怎么做,先说的宽泛
点,引诱对方给你缩小范围,这有点心理学的技巧。
俺回头问问recruiter的反馈。自我反省一下。
【在 s*****3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不知道问你inversion问题的国人哥们上不上mitbbs,这题并不容易。我给了个二分查 : 找树的算法,人家并不满意,因为worst case是n^2. : 另外,并不一定只是老印黑了你。我也是上周面的。问了recruiter面试反馈,说是国 : 人哥们和老印那两轮有concerns。不过我马上move on了,毕竟没达到人家的bar。
|
b**********5 发帖数: 7881 | 17 不好意思, 我觉得你的知识面, 比我还差。。 algo的题, mergesort都没怎么写对
, 哪个什么boggle的题, 也好像写了个pseudocode。。。
然后存data, 竟然存到hdfs上了。。。 这个我觉得你根本就没怎么准备啊。。。
【在 a*****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩,无所谓了,他家recruiter死气白咧的让俺去面试。俺想给人个面子吧。 : 本来系统设计这个东西,都是用现有技术先最快做出一个可以用的蓝本,然后再到生产 : 环境中去检验的,发现那里有瓶颈,根据反馈出的信息来进行定位并解决瓶颈。你们那 : 么多人多长时间解决的问题,要俺45分钟内给分析出个一模一样的来,老实说,俺要现 : 在有这本事,也不来这面了。 : 跟一个以前拿过他家offer的小弟聊了,要察言观色,看人家想你怎么做,先说的宽泛 : 点,引诱对方给你缩小范围,这有点心理学的技巧。 : 俺回头问问recruiter的反馈。自我反省一下。
|
a*****s 发帖数: 1121 | 18 牛肉姐也是做体系结构的?牛肉姐以直白著称,能聊聊你怎么准备的么?很少见你上面
经,回馈本版啊。
有些知识你做深了,必然就面窄了。
本来就没准备。存HDFS也不是不可以,而且也不是没有大公司用。
前段手机的数据需要个kafka的东西来aggregate,然后写给HDFS,之后给MR或是SPARK
去处理,结果存HDFS,他又没给我latency的SLA requirement,哥也是知道redis啥的
,很了不起么?
说白了就是大家投缘不投缘,你没说的我心坎上,对不起,不要你。门槛而已啦。
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不好意思, 我觉得你的知识面, 比我还差。。 algo的题, mergesort都没怎么写对 : , 哪个什么boggle的题, 也好像写了个pseudocode。。。 : 然后存data, 竟然存到hdfs上了。。。 这个我觉得你根本就没怎么准备啊。。。
|