Tag Archives: 面试

Coursera: Algorithms, Part I: Week 3

第三周的内容是归并排序和快速排序。视频里我不清楚的内容大多跟具体Java代码有关,我对Java没有兴趣所以不管了。讲的快排里有一点是比较有趣的:如果数组里有很多重复元素的话,经典的partition方法会很坏,极端情况就是如果元素全部相同,复杂度退化为平方级别。这个问题怎么解决呢,其实很简单,就是所谓3-way quick-sort,在partition时把数组分成小于、等于和大于pivot三部分,划分的方法实际上就是上一周最后的荷兰旗问题。然后只对小于和大于的两部分递归处理即可。这个复杂度和数组的熵成正比。

Interview Questions: MergeSort

3. Shuffle一个单链表,要求O(NlogN)时间,常数或O(logN)空间。

答:分治法。把一个链表分成两部分分别Shuffle,然后以各1/2的概率的决定哪部分在前面。 (感谢resty指出错误)在合并的时候,根据两部分的剩余长度动态决定下一个元素从哪一部分的头部取,设两部分长度分别为a和b,则以a/(a+b)的概率从第一部分取一个元素出来,持续此过程直至合并完毕。划分一个链表的复杂度是线性时间,合并两部分是常数时间,所以总时间复杂度就是O(NlogN)。递归需要的空间复杂度是O(logN)。具体实现的时候要注意记录每部分的头尾结点。

Interview Questions: QuickSort

1. 螺母和螺栓。有N个螺母和N个螺栓,每个螺母的大小都不同,每个螺栓的大小也都不同,对每个螺母有且仅有一个螺栓与它对应。每次你可以拿起一个螺母和一个螺栓比较,看看是否匹配,如果不匹配,显然你可以知道哪个大哪个小。但是不允许直接比较两个螺母或两个螺栓。现要求用最少的比较次数找出对应关系。

答:我曾在面试时被问到这个题。这个题很漂亮,不过出现在这一章后面就提示性太强了。方法就是类似快排,随便找一个螺母a,用它把所有螺栓分成小于a、大于a和等于a(只有一个)。再用那个等于a的螺栓把所有螺母也划分一遍。于是就得到了一对匹配和“大于a的螺母螺栓”、“小于a的螺母螺栓”两部分,递归处理。复杂度和随机选取pivot的快排的复杂度一样。

2. 给定两个排好序的数组a和b,长度分别为N1和N2,要找到第k大的数。复杂度应该是log(N1+N2)

答:先假设答案是a中,在a中二分查找,假设答案是a中的第x个数,则检查数组b中第k-x个元素及附近的元素,就可以确定二分查找的范围应该在前一半还是后一半。如果最后没有找到,则答案在数组b中,用同样过程颠倒ab再二分一遍。具体实现上有一些边界细节大概要比较注意才能写对。

3. 给定长度为N的数组,找出其中所有出现次数超过N/10的元素。复杂度是线性。

答:这是那个被出烂了的“找出出现超过一半的元素”的升级版。思路相同:如果我们每次找出10个不同的元素并删掉,直到找不出来为止,那么超过N/10次的那些元素一定会被剩下来。把这个思路用一个比较简单的方式实现出来:

struct Counter {int val, cnt;} counter[9];

for (k in A[]) {
  exist = False;
  for (i = 0 to 8) {
    if (counter[i].val == k) {++counter[i].cnt; exist = True; break;}
  }
  if (exist) continue;
  full = True;
  for (i = 0 to 8) {
    if (counter[i].cnt == 0) {counter[i].val = k; counter[i].cnt = 1; full = False; break;}
  }
  if (full) {
    for (i = 0 to 8) {--counter[i].cnt;}
  }
}

最后把所有剩下的counter[i].val检查一遍即可。

Coursera: Algorithms, Part I: Week 2

第二周的内容是栈、队列和几种排序(选择排序、插入排序、Shell排序)。课程内容比较基本,让我略感兴趣的有这么几点:

1. Java自带GC,链表上删除元素的时候只要没有指针继续指向它就可以了。用数据实现栈或队列时要注意一个貌似叫做loitering的问题,比如元素出栈,不能直接–top就完事了,要写上 stack[–top] = null。

2. 数组的动态增加,大家都知道常用的方法是当数组满了时重新申请一个容量为原来2倍的新数组,把原来数组里的元素逐个复制过去,每次操作均摊复杂度是常数。但是如果我们想在数组元素减少时把容量缩小,注意不能用这样的策略:当元素减少到总容量的1/2时,重新申请一个容量为一半的。因为这样的话最坏情况下元素数目在1/2附近上上下下,每次都要O(n)。一种正确的方法是:当元素减少到总容量的1/4时,重新申请一个容量为1/2的,这样均摊复杂度就仍然是常数。

3. Random shuffle的实现,即使算法是对的,如果元素比较多就要非常注意。比如打乱一副扑克牌,有54!种可能,如果你的随机数种子只有32位,那么最多只能输出2^32种序列,是不够的。

Interview Questions: Stacks and Queues

5. 有一种扩展的单链表,每个节点上除了指向下个节点的指针,还多了一个指向任意其他节点的指针。要求用线性时间复制这个数据结构。可以在过程中改变原有链表的指针,但是算法结束时必须是两个分离的链表。

答:

Node* copy(Node *src) {
    // 在每两个相邻结点中插一个新结点
    for (Node *p = src ; p ; ) {
        Node *tmp = new Node;
        tmp->v = p->v;
        tmp->next = p->next;
        tmp->random = p->random;
        Node *tmp2 = p->next;
        p->next = tmp;
        p = tmp2;
    }
    // 正确设置新结点的random指针
    for (Node *p = src->next ; p->next ; p = p->next->next) {
        p->random = p->random->next;
    }
    // 把两个链表拆开
    Node *res = src->next;
    for (Node *p = src ; p ; ) {
        Node *tmp = p->next;
        p->next = tmp->next;
        Node *tmp2 = tmp->next;
        if (tmp2) tmp->next = tmp2->next;
        else tmp->next = NULL;
        p = tmp2;
    }
    return res;
}

Interview Questions: Elementary Sorts

3. 数组有N个元素,每个元素可能是红色、白色或蓝色。现在要把它们按照颜色排序(左红中白右蓝)。允许两种操作:swap(i,j)表示交换元素i,j;color(i)表示获得元素i的颜色。要求最多调用N次swap,N次color,O(1)的额外空间。

答:从左到右扫描,在扫描过程中,整个数组被分成四部分,[RRR][WWW][XXXX][BBB],X表示未扫描到的部分,检查第一个X,如果它是R,把它与第一个W交换;如果是W,不交换;如果是B,与最后一个X交换。直至X部分都被检查完。

Coursera: Algorithms, Part I: Interview questions week 1

Coursera上Robert Sedgewick的算法课本周开始了,第一周的课是并查集和基本的算法分析方法,大概听了下,一个让我有点感兴趣的地方是有一张ppt里列了并查集的具体应用,里面有一些是我没听说过但是看上去又比较好玩的,不过都被一带而过了。有一个比较有趣的栏目叫Job Interview Questions,题目还不错,不计分,点提交按钮可以看到简略的提示。在这里把我觉得有意思的题目做一下,给我这个blog添些文章充数。

Inverview Questions: Union-Find

3.给定集合S={0,1,…,N-1},有两种操作:
(a)从集合中删除一个给定的数x
(b)求给定的数y的后继,即集合里比y大的最小的数
要求所有操作都是对数时间或更低。

答:如果不是因为出现在这一课,我觉得还是有点不好想的。可以把每个存在的数和比它小的连续的若干被删除的数看作一个集合(如果用X表示被删除的数,这个序列是类似OXOXXXOO的形式,集合为{O}{XO}{XXXO}{O})删除x就是把x所在的集合和x+1所在的集合合并,注意要对每个集合记录一个标记,表示该集合里没被删除的那个数,合并两个集合时把标记更新为较大的那个。查询操作就是得到y+1所在的集合的标记。复杂度就是并查集操作的复杂度。

4. 如果Union操作时是按照树的高度进行合并(让高度大的树的根作为合并后的树的根),证明对N个结点的操作得到的树的高度上界是lgN

答:用归纳法证明:高度为x(只有叶子的树高度为0)的树至少包含2^x个结点。高度为0时显然成立。设高度不超过k时成立,若两树合并后高度比两树都大,只有当两树高度均为k时,合并得到高为k+1的树,此时结点数不小于2^k + 2^k = 2^(k+1),得证。

ps. 在视频里证明了如果是按照树的结点数进行合并,高度上界也是lgN。证法比归纳法更巧妙:考虑结点a距离树根的距离,如果这个距离增加,说明a所在的树被接在了另一棵树上,因为是按结点数合并,另一棵树的结点数不少于a原来在的树,合并后的结点数至少double。因为一共N个结点,这种double最多只能进行lgN次,得证。

Inverview Questions: Analysis of Algorithms

2. 在bitonic array里查找一个数。所谓bitonic array是指一个先递增后递减的序列,没有重复元素。要求比较次数最坏大约是3lgN

答:先用三分搜索找到最大值(每次比较把区间缩小到原来的2/3,算了一下大概要1.7lgN次比较)。再在两个序列里分别进行二分搜索(2lgN)。

3. 从楼上扔鸡蛋问题的各种版本:共有N层楼,鸡蛋从第T层扔下摔不坏,在第T+1层扔下会摔坏,想找出这个T值。在各种鸡蛋数和扔的次数的限制下的策略。
a. 1个鸡蛋,<= N次扔
b. ~lgN个鸡蛋,~lgN次扔
c. ~lgT个鸡蛋,~2lgT次扔
d. 2个鸡蛋,~2sqrt(N)次扔
e. 2个鸡蛋,<=c*sqrt(T)次扔, c是固定常数

答:a. 一个鸡蛋从低层向高层依次扔,直到摔坏
b. 二分查找。先试N/2,如果摔坏了,就试N/4,否则试3N/4。要试约lgN次,最坏情况下摔坏约lgN个鸡蛋
c. 以1,2,4,8…倍增的间距从低层向高层扔,即从1,3,7,15…层逐次向下扔,直到摔坏。设扔了k次后摔坏,此时的间距x=2^k满足 1+2+4+…+2^k = 2^(k+1) – 1 >= T,所以k约为lgT,定位出一个不超过2T的区间。在此区间内二分查找,最坏摔坏lgT个鸡蛋,此步又需要扔lgT次。一共约摔坏lgT个鸡蛋,扔2lgT次。
d. 以约sqrt(N)为间距从低层向高层扔,直到摔坏,最坏情况约扔sqrt(N)次,可以确定一个约为sqrt(N)的楼层区间,在这个区间里用第二个鸡蛋从低向高逐层扔,直到摔坏,最坏情况约再扔sqrt(N)次。
e. 以1,2,3,4…递增的间距从低层向高层扔,直到摔坏,此时的间距x满足1+2+…+x = (x^2 + x) / 2 >= T,所以x约为sqrt(T),这一步扔了约sqrt(T)次。再在这个大小为x的区间内逐层扔,最坏约再扔sqrt(T)次。

Facebook面试Q&A

续上篇文章,我把大家在得知此消息后普遍感兴趣的一些问题总结了一下,在此一并写出。

说实话,其实我的眼界从来很狭窄,以前想的是,如果能在天朝帝都扎下脚跟,过上老婆孩子热炕头的日子,对我来说已很满足。所以之前也从未对出国读书或工作有过准备,下文所述很多内容都是我在最近的一小段时间里才接触到的,而且现在离正式入职还早,对于fb内部的情况并没有什么了解,签证之类的麻烦事还在办理中,说不定去不成了也是有可能的(-_-)……扯远了,总之就是说,虽然我已经尽力做到客观准确,但恐怕难免会有错漏,请读者不吝赐教。本文仅供参考,引起什么不好的后果本人不负责任 =,=

Q: 你的学历、学校、专业、英语成绩、论文、竞赛获奖、工作经验、参与开源项目等背景情况?一定很牛吧?

A: 真的不牛,矮丑穷,纯RP爆发而已。本科天津大学软件学院,硕士天津大学计算机学院。高中无竞赛经历,本科阶段ACM-ICPC竞赛亚洲区域赛有几次金奖(其实只是一百个队里前十几名而已的意思),进过一次总决赛但无奖牌。Topcoder现在黄圈未满,最高时曾红了一点点。世界范围的算法比赛比如Topcoder Open, Google Code Jam之类只求混件衣服从没进过决赛,中国范围的如百度之星, GCJ中国站之类运气好的时候进过一两次,但最终没有很高的成绩。没考过托福GRE。没有Top期刊会议论文。没有参与过靠谱的开源项目。毕业前没有实习经验,毕业后在腾讯公司有一年工作经验,做搜索引擎的后台开发,小兵一枚。

Q: 你是怎么和Facebook联系上的?自己投的简历还是找人内推?

A: 一开始是一个国外的猎头公司给我发的邮件,说有Facebook的工作机会,如果有兴趣的话回复简历给他们,我就回了一个。我不清楚这个猎头公司是从什么途径找到了我的联系方式。

Q: 面试用英文还是中文?

A: 全程英文,不过对自己的英语没有信心的同学也不必太担心。书面英语大家应该不太发怵,担心的估计是听和说。

听的方面:因为面试的时候大多数时间都是在白板上(在线白板或者现场白板)写代码,而代码是地球人都看得懂的~ 面试问题中一些关键的信息,面试官为了清楚起见都会写在白板上(如果没有,你也可以要求他写一下),所以总的来说还好。值得注意的是有些面试官会有口音(最常见的就是印度口音了),如果之前完全没有听过的话会很不好懂,尤其是在电话面试时加上噪音的干扰,这个也没什么好办法,听不清就让对方重复几遍好了,关键信息可以让对方写在在线白板上。我在电话面试时遇见的就是印度面试官,答得磕磕绊绊,还好通过了。(扯远两句,不知道多听TBBT里Raj的说话有没有帮助,嘿嘿。据说对于成年人,练习听力的最好办法不是只听非常标准的英语,而是要尽可能多地接触各种口音,这样才能把耳朵的分辨能力练出来)

说的方面:人脑的纠错功能不是盖的,你作为non-native speaker,语法错误没人会care,哪怕你毫无语法的一个个单词往外蹦,老外也能基本听懂。切记这是技术面试不是口语考试,不要因为组织不好语言就不敢说话了。比如你的思路被卡住的时候,不要一直闷头苦想,要把你目前想到东西说出来,让面试官知道你不是毫无头绪的,他也可以根据你的想法给出些提示。再比如在白板上实现算法的时候,如果代码不是显而易见的,最好能一边写一边简单解释一下,让面试官跟上你的思路。(上面这段其实不只限于英文面试)

当然,虽说不用太担心,但基本的英文水平(包括一些专业术语)还是需要的,比如如果你连二叉树、排序都不知道对应的英文单词怎么说,那还是不行的。我觉得如果能在英文字幕的帮助下看得懂MIT算法导论的讲课视频的大部分内容,这种程度的话英文和算法应该就都没有问题了,哈哈。

Q: 面试的流程是怎样的?

好像每个人都略有不同,只说我自己的。发简历过去之后,先被要求在interviewstreet.com上限时做一道题(很水,就是看看你会不会写代码的程度。难度远低于那网站上的题目的平均水平,不要被那网站公开出来的题目吓到了)通过之后就是预约时间进行电话面试,电话面试的形式是面试官打电话过来,然后一边讲电话一边在一个在线白板网站(collabedit.com)上写代码,双方都可以实时看到,约45分钟到1小时。我只电面了一轮,据后来了解,也有人电面了两轮或三轮的。然后被叫到香港去现场面试(三轮,每轮45分钟左右),前两轮是纯技术面试,最后一轮一半技术,一半应是所谓behavioral question。然后就是等消息了。

关于面试地点,我们那批是在香港。之前有大神是直接去美国面的,之后据说又有一批是在北京面的。

Q: fb这次招了多少中国人?

我不知道。我们去香港的那批估计有二十人左右,有应届生,也有两三年工作经验的,我不知道多大比例拿到offer。我知道的ACMer里面大约有五六个。

Q: 面试时写代码的语言是?

A: 无限制。不过我觉得最好是用比较主流的语言,比如C++/Java/Python之类。我不确定用伪代码行不行。

Q: 面试题什么类型?难度如何?

A: 基本全是算法/数据结构题,但我不太确定这是普遍情况,还是因为我的简历上强调自己算法还行,从而导致他们有针对性地问。难度的话,不能算容易,但也不算太难,至少比Google中国的题简单。(ps. 貌似据说Google中国的题也比Google总部难-_-)代码量不会很大,不超过二三十行的样子。

另外需要说的一点是,这些面试官给的感觉是真的“懂”自己出的题的,和他们能够进行有效率的交流。举个例子,有一道面试题我有个地方用了带点trick的写法,面试官指着代码刚要问,我也刚要进一步解释,他忽然自己看明白了”Oh I see. Good.”,于是就继续后面了。另外一场面试时,我有个不太重要的地方粗心写漏了些东西,面试官说“There is a little mistake…”又马上说“but never mind.” 我不顾他说了好几次”never mind”,又仔细盯了半天才终于发现了错误,确实是并不影响大局的,他可以看出我是找到了正确的解法的,并不在意这种明显是手误的bug。反观国内有些公司,有的面试官给人的感觉是临时从网上找了几道题目,自己也对某些细节不明所以,于是双方都稀里糊涂,互相跟不上对方的思路。

我感觉如果fb继续在海外招人,他们应该很快会发现“啊……原来中国有这么多神牛啊……之前招的那个叫roba的真是弱的像渣一样啊……裁掉算了吧……” 所以还请各位神牛轻虐……orz……

Q: 去了之后主要做什么方向?

A: 只知道是Software Engineer,具体未知。他们的说法是在刚去的几周内有机会在各个方向都体验一下,然后自己选择。我觉得这应该只是理想情况,估计应该是个双向选择吧。

Q: 工资?

A: 具体数字不能说,呵呵。可以参考glassdoor.com上给出的统计,还是比较接近实际情况的。

Q: 什么时候过去?听说有绿卡?

A: 只是工作签证(H1B)而已,绿卡什么的是很久远以后的事了,fb哪有那么大能量直接发绿卡的。如果这期间我被公司裁掉了又没找到下家,就得直接回来了。

关于H1B签证的申请和发放时间是值得一说的,每年H1B的开始申请时间是4月1日,签证发放时间是10月1日,所以即使拿到了名额,从中国过去工作的话也只能在10月份以后。近年的名额数目是每年65000个普通名额+20000个高学历名额 (仅给在美国大学取得硕士以上学位的留学生),用完为止。以我自己为例,收到和接受offer是在今年5月初,公司请的律师把申请递交到美国移民局是在5月中旬,递交上去就算占住坑了,当时65000个名额里我记得是已经用了一半多一些。这次的名额全部被用完是在6月中旬。我知道的几个应届生大神,因为学校的毕业证差不多也是那时候才刚发下来,所以就搞得相当危险。H1B名额的申请速度每年波动很大,以前甚至出现过在4月一开始就被占满的情况,这次的消耗速度就比去年快得多,有牛人预测明年的速度可能会更快,所以如果想从国内直接找美国工作的话,要早做准备。比如现在因为今年h1b已用完,听说facebook已经暂停了从海外招人[Edit: 我不确定,可能不实](呃……我不清楚美国的公司如果有意向从海外招人,一般每年是从什么时候开始……我一开始收到猎头的信好像是在3月份……总之要记住4月和10月这两个时间点来安排计划,呵呵)

上面这一段是我现炒现卖,详请大家可以去自行搜索。如有错误请高人指正。

Q: 妹纸怎么办?

A: H1B签证是可以带家属的(当然得先领了结婚证),不过家属过去的话是H4身份,法律上规定不能找有收入的工作。要想工作的话,一种是也直接找到一个可以帮她申请H1B的公司,另一种办法是先读个书,这样再找工作会容易些。

ps. 具体到我自己的妹纸,她的事业心还是比较强的,决不甘心在那边当主妇。目前正在准备英语考试中,打算看看能不能申请到一个附近学校的master读。这次facebook的面试,从投简历,准备面试,到后来去往香港过程中的诸多波折(没有且来不及办港澳通行证,买了到泰国的机票想装作过境香港,出发前一天发现泰国虽然落地签但是中国边检不放,又退了换成到印尼的,在机场被工作人员拦下说必须有往返票,又临时改签+买回程票),每次我觉得太折腾想放弃的时候,都是她一边忙前忙后地查票打电话上网搜索,一边鼓励我,才终于有了现在的结果,我对此非常的欣赏与感激。

Q: 需要托福GRE成绩么?

H1B和H4都不需要

Q: 能否推荐一些对面试有用的资源?

A: 如果时间充裕的话,看书我还是推荐算法导论……只为准备面试的话,有一本叫Career cup Top 150题之类名字的书可以看一下(可以搜到电子版,这里就不提供链接了),类似的针对程序员面试的英文书还有另外几本,比那个《程序员面试宝典》靠谱些。

网站资源的话,上面提到的interviewstreet.com, glassdoor.com都不错,另外careercup.com,leetcode.com都是听别人提起比较多的,上面有各种各样的算法题目(我自己都没怎么上过,不知道哪个更好些)。当然对于ACMer来说,各个OJ都是很好的资源,对于非ACMer来说,如果想接触一下竞赛题的话,我推荐topcoder.com里面的Algorithm竞赛里Div2难度的题目。Topcoder的题目代码量通常不会太大,更接近面试时的情况,而且多数题目都会在赛后有解答,而且可以看到别人的提交,所以也是学习的好机会。

论坛的话,我上的最多的是水木社区的算法版(newsmth.net),另外mitbbs.com上关于在美国签证、找工作、移民等等的讨论都很多。前不久发现一个叫”一亩三分地(www.1point3acres.com/bbs)的论坛看上去也很赞。

突然发现写了这么多了,先到此为止。最后,最近RP消耗太多了,求RP……