狗狗家fail的面经

发信人: glowinglake (湖清霞远), 信区: JobHunting
标  题: 狗狗家fail的面经
发信站: BBS 未名空间站 (Tue May  6 01:07:54 2014, 美东)

今天HR打电话来说HC没过，记下来参考

电面1：
第一个问题记不得了
第二个，给一系列string，要求找两个string,使得它们没有共同字符，并且长度乘积
最大。好像给了个暴力解

电面2：
给两个string array A,B，要求返回三个array，第一个只包含只出现在A中的字符串，
第二个只包含只出现在B中的字符串，第三个只包含common字符串
然后海量数据下该怎么code。貌似这个电面反馈很好

onsite:
1. 先寒暄介绍，稍稍问现在工作。题目是run length encoding的变种，decoder的规
则是： a3x1bc -> a111bc (用x来表示重复）
该怎么设计encoder。写代码。开头想了很久，才写了代码，写得比较罗嗦。再跑了几
个测试。这轮发挥不好，HR开头也迟到了一会儿，导致时间稍稍不够，没时间再做一题
了，问了几个问题结束。

2. 稍稍介绍下google的工作。题目是常见题二维平面上过最多点的直线。问清后写了
个n^2logn的解法，然后在提示下讲了n^2的方法。扩展问海量数据下的做法，这里纠结
了，给了个比较复杂的方法。时间到。这轮应该还OK。

3. 简单题，给定一个char array,删除里面某个char。
第二题是二维平面有若干个点，找一个点使得到他们的曼哈顿距离最短。就是找median
。分析后讲了quick select找median。
给定一个二维矩阵，有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。
怎么设计使得update()比较快？
怎么设计使得sum()比较快？
怎么设计使得两者都reasonable得快？好像最后讨论到n,log(n)的设计
这轮还不错

4. 简单题。给定一个二叉树，找到最深的leaf，返回深度和节点本身。写code。
找到最浅的leaf，返回深度和节点本身。
给定一系列电影开始和结束时间，怎么选择电影能看最多场次。（greedy O(n))
怎么选择能看最长时间？
返回最长时间，和需要看的电影（写了个dp的方法,nlogn，这轮也还不错)

5. 给定一个数列。返回一个最大的数，使得数列中大于它的数数量也大于它，这个数
不需要在数列里，写代码。（这题真够拗口，当时三哥把题目写在黑板上，读了好几遍
才理解，就是先sort然后一个一个找）代码最后返回处有bug，在提示下修改。然后跑
了几个test，没问题。
然后问如果数列里有很多重复数字该怎么弄比较快，三哥说不需要sort。想了很久，答
bucket sort,再讨论了下具体的bucket细节/数量。这轮也就答了一题就到时间了。

总结：面完感觉整体也就凑合，结果果然悲剧。也不知具体feedback。
面试前HR很强调跟面试官的交流，交流过头了也不行，没时间写代码。写代码越快越好
，最好一口气就写下来。而且有好的solution就应该一步到位，这样有时间做下一题。

--
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 50.]

http://www.mitbbs.com/article_t/JobHunting/32689155.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

京东世界杯零食专场，满100立减30元 ， 更多京东优惠券