ebay 两轮电面面经

原帖地址:一亩三分地

不久前的两轮背靠背的电面。都是烙印,不过到没感觉出来黑我。因为是在职跳槽,上班的时候面试还真是紧张。先是临时找了个会议室,开始几分钟前,突然有人告诉我这个地方是他的办公室。正跟那人边聊着,边收拾东西,然后公司CEO进来了,跟CEO握手的时候电话响了。。赶紧跑到另外一个办公室,刚放下东西,在介绍自己呢,又有人敲门说这个会议室不能用,要预约。挂了电话,跑上楼,找了个挨着过道的会议室。但是手机信号不好,收不到来电,不得已,自己打过去。这时候已经过去了12分钟了。寒暄几句,开始做题:判断一个字符串是否是一段子串重复n次,比如abab是ab重复2次返回true,aba返回false,aaa返回true. 先说了brute force的解法,然后用KMP解法,大概写了20分钟,无比紧张,因为办公室是透明玻璃,外面人来人往,极其担心boss看到。写完,对方表示满意,然后问问题,其实我当时已无心情听他说了,不得已要熬到45分钟结束。后面想我写的程序还是有个bug,不过但是太紧张,没找出来,对面也没看到。第二轮是15分钟后,虽然换了个房间,但面试心情已无,因为外面还是人来人往,曾有同组人经过,好在没注意我。第二轮的烙印我几乎听不懂他的英语,先是问我是不是对database很熟,回答否。然后问了一天:如果有两个table 如:
tbl1
a1 0.98
a2 0.97
a3 0.97
tbl2
a1 0.99
a4 0.98
a3 0.94
第一列是key,第二列是value,两个table是以value排序的,找出两个table中value和为top k的key。比如上面的例子,top 1 是a1(0.98+0.99) top 2 是a1(0.98+0.99)和a3(0.97+0.94)。因为一开始对方问了关于database的问题,而且此题以两个table的形式给出,所以我原以为是要我写sql query。后确认是要我设计算法,我答曰用hashtable,再问如果两个table都有million行,却只要top 10,有无更好方法。想了半天,实在不得其解。心情糟糕至极。面试官问我要不要问下一题,我几乎放弃,说,算了,不用下一题,你跟我说说这题解法吧。对面说了一个解法,似乎挺巧妙,但是我后面一想又有些问题,也有可能我没理解,所以就不在这说了。最后问了一个分层遍历二叉树,用queue实现,5分钟写了两边,因为中间网页刷新,刚写的没有了。

此次面试很不顺利,也怪自己没早做准备,搞的十分紧张。今天说要再面第三轮,到时出乎我的意料。