pocket gems面经

发信人: unichen (greedyrouter), 信区: JobHunting
标  题: pocket gems面经
发信站: BBS 未名空间站 (Sat May 24 10:58:35 2014, 美东)

总共有4轮。给的offer不是很好看，所以没去。他们家的阿三面完第三轮和我说你应该
已经面完了，但是后来HR又给了我第4轮，我猜应该是前面两轮面的不错吧。他们家的
面试题是最独特，也是我最喜欢的。

第一轮：
1‘  Shortest Manhattan distance. 有一个网格。在这个网格上有若干个人，如何在
此网格上找出一个约会地点，使其到所有人的距离之和最短。
2’  如何去serialize一棵树。

第二轮：
1‘  字符串分割。有一个字符串和一个字典，问此字符串是否可以分割成字典中的若
干个词。时间复杂度为何？
2‘  random sampling。有一个infinite的stream，你想sample其中的k个元素。每次
遇到新元素你可以选择加入它，同时放弃原有的一些元素。如何让每个元素被选到的概
率一样，同时不使用多余的空间。
3‘  你有一个棋盘。从原点出发，定义f(x,y)为其坐标所有数字之和。例如f(185,233
) = 1+8+5+2+3+3。每次你都可以选择走任何8个方向。问：最后你能够到的点是有限个
吗？试证明之。

第三轮：
设计一个游戏的scoreboard。假设每个人都有若干个任务。完成每个任务都会有相应的
奖励。

第四轮：
设计一个mutable string，支持下列的功能：
1' getCharAt   2' substring  3'setCharAt
要求每个operation的space cost都是O(1)


--
※ 修改:·unichen 於 May 24 19:30:28 2014 修改本文·[FROM: 71.]
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 71.]

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

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

钟表618满1500元减100元京东优惠券免费领 ， 更多京东优惠券