Google, Facebook, Twitter, Amazon, Square, Zillow, YP, Bloomreach 面经

心路历程那些话就不说了. 每个找工作的人在没有offer前都是一样的...

准备:

1.CTCI一遍, Leetcode, 一亩三分地+mitbbs的面经, 然后坚持每个面过的面试题都再重新写写一遍(尽可能的做到最优).

2.这里强烈推荐下这2个贴子, 一个是我见过最好的面试题总结, 30道左右, 都是高频, 做完就开始电面. 我把这个帖子打印下来, 写上笔记, 每次onsite在走廊里等的时候, 都温习这个. (http://www.mitbbs.co.nz/article_t/JobHunting/32564237.html)

还有一个是讲怎么写Binary search的, 讲的很好, 按照他的写法, 就从来没出过错, 也很少考虑边界情况. (http://fihopzz.blogspot.com/2013 ... ary-search-and.html)

3.对于写Java的同学, 建议先去ProgramCreek.com上把关于java基础概念的帖子看完, 再开始做算法. 因为不少面试会问到java的基础知识问题, 只刷题这方面容易忽略.

简历:

从我将近30轮的面试经历来看, 简历的作用只有一个: 帮我拿到面试.

面试的时候, 全部是coding, 根本没人看我简历. 最多最多让你挑一个你觉得有意思的项目来讲下.

既然这样, 建议写简历的时候千万千万不要谦虚(你再吹都吹不过三哥), 不然面试都没有, 什么都是白搭. recruiter看你简历的时候, 他也不认识你, 你说什么那就是什么.

我周围有很多背景还是可以的, 就是没面试, 唯一的可能就是简历出了问题. 如果因为简历不好没拿到面试的, 可以历好好改下简历, 然后换个名字, 换个邮箱, 不留电话, 重新投. 简历上可以不用写真名, 真名一般就onsite的时候, 买机票必须要.

时间:

我这学期毕业, 2月开始投刷题和简历, 面试从3月开始, 没offer前一直在投, 4月中旬收到3个offer结束, 结束的时候还有两个公司没面完.

我这个时间算比较晚了, 建议第二年一开学就开始找new grad全职. 当时投的时候, 发现Yahoo和LinkedIn基本已经招满了. 原来联系我去面试的recruiter也不理我了.

然后其他的几个大公司全部找人内推, 包括学长, 实习时候的老板, 还有LinkedIn上直接搜"公司+USC", 找到一个USC的, 就直接发站内信, 求内推. 总之尽量内推, 实在不行在网投.

第一次面试开始前,就刷了CTCI那本书和leetcode 30道高频题. 后来边面面试边刷, 逐渐刷完leetcode全部. 由于我之前的编程的经验还可以, 所以刷起来没有花太多时间在理解算法上面, 主要是记忆一些通用的解法.

面经, 按照时间顺序, 我写java和python:

Google:

电面:

1. BST的add, find和delete函数

2.给string, 只包含{0,1,?}, ?可以代表0或者1, 输出所有的组合. 例如"10?", 输出"100", "101"

onsite:

您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

5.shuffle数组, 输入是一个数组, 没排序, 输出是奇数index的数字比相邻的偶数数值大即可. O(n)

6.加试电面, 写jump iterator类, 构造函数传入一个普通的iterator, 然后实现next(), hasNext(). next()返回传入iterator的next().next(), 就是每次跳过一个元素输出.

然后再实现一个rotateIterator(), 构造函数传入List<Iterator<T>>, 实现next(), hasNext(). 例如:

传入的三个iterator里面的值分别是[[1,2,3],[4,5,6], [7,8]], 那rotateIterator的next()应该输出[1,4,7,2,5,8,3,6]. 就是竖着遍历每个iterator输出, 如果当前的iterator没有了, 就跳到下一个.

Facebook:

我觉得Facebook是有题库的, 因为当我面试完的时候, 回去看网上的面经和问其他onsite的同学, 重复度相当高. FB的题目都不难, 关键是代码要bug-free, optimal, 然后能多写一种解法就多写一种.

1.anagram, 输出一个句子, 里面的单词是空格隔开, 输出list of anagram in this sentence. 就是List<List<String>>.

2.sort colors, 三色旗问题, 用swap, O(n)时间, O(1)空间.

3.Pow

4.给一堆point(x, y), 返回前k个离远点最近的点, 用k-selection算法, 核心就是那个partition, 平均时间复杂度可以做到O(n).

5.实现哈希表, 只实现lookup()和add()

6.树的中序遍历和前序遍历的iterative代码.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

11.给一个每行和每列都排序好的矩阵, 求第k大的数值. 可以用heap做.

12.Lowest common ancestor, 注意要写CTCI上面那个代码, 输入可能不来自同一棵树.

13.给一个span(min, max)和BST, 返回一个子树, 子树里面的节点都在这个span里面.

14.jump river的题目, 给一个数组[1,0,1,0,1], 1代表可以站, 0不可以站. 从速度为1开始往前跳, 每次跳的时候, 可以跳当前速度那么多格, 也可以跳当前速度+1那么多格. 问最少跳几次可以跳过河(即跳出数组), 或者跳不过河. 解法直接递归+cache就可以. 上面的例子跳2次就能跳过河了, 第一次从index=0, 速度为1跳到2, 然后速度为2刚好跳出去.

Facebook onsite的时候还有一轮Culture Fit面试, 除了讲讲你的简历, 下面几个问题经常会问到:

1.为什么选Facebook?

2.给FB的一个产品提点改进意见.

3.当你和你的同事有冲突了, 怎么解决? (focus on "let the code talk")

4.最近在读什么书?

Twitter:

Twitter 我面试了两个职位, Site Reliability Engineer和普通的software engineer. 先面完SRE(4轮电话+5轮onsite), onsite没过, 然后又给我安排SDE的面试, 面了一轮我就收到FB的offer了, 就终止了Twitter的面试.

SRE问了很多OS, 文件系统, 网络, shell和trouble shooting的问题, 太细就不说了. 我就说下遇到的算法题.

0.online test的话, 自己去搜其他的面经吧, 我当时的online test的题目基本和其他人的面经差不多.

1.给一个数组, shuffle. (我记得不说非常清楚, 大概是)当前的数值的三次方是前两个数值的三次方的和.

2.2sum, 3sum

3.trap rain water

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

6.Python语言的问题, 包括GIL, iterator.

7.Machine Learning问题, SVM的原理之类.

Amazon:

我直接是group interview, 没有电面, group的题目网上能找到, 太长我就不说了.

我知道的一些onsite题目:

1.BFS搜一些product和friend.

2. 3Sum

3.validBST

4.word search in grid.

5.序列化BT, 反序列化BT和BST

Square:

这个公司据说近况不太好, 我当时就面了一轮电话, 没答好就挂了.

1.给一堆源代码文件, 每个文件有dependency on 其他源代码文件, 就像java里面, 会import其他的源文件. 写个函数检测这堆源代码文件里面有没有circular dependency.

抽象出来, 就是检测一个有向图里有没有环, 用BFS就可以, 如果搜到以前已经访问过的节点, 就有circle.

SalesForce:

找到一个manager内推的, 安排了一个面试, 结果面试的那个组做ruby的, 我不懂, 就没什么好聊的, 问了一个binary search的简单问题, 就结束没有后续了. 而且那个组在Indiana…

Bloomreach:

这个startup还是不错的, 就在Google总部旁边, 我面了一轮就收到其他offer, 没继续面了.

1.输入是log文件, "customer, query, url". 读这个文件, 返回每个customer搜得最多的query和对应的url.

follow up如果输入文件很大, 怎么map-reduce来做, 描述下怎么写出简单mapper和reducer.

Zillow:

这是一家在西雅图的租房卖房交易平台公司,是上市公司, 总部是个海景房, new grad给面试给的很多, 有题库. Offer package刚刚高于100K, 略低于Amazon.

1.Lowest common ancestor.

2.给一个数, 判定他的二进制表示是否是一个palindrome, 比如3的二进制是11, 就是palindrome.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

5.给一个字符串, 返回第一个出现了一次的字母.

6.给一个字符串, 还有一个字典, 返回这个字符串否被字典里的单词分割. follow up, 出了hashSet, 还能怎么表示字典, trie.

7.validBST

8.给一个sorted array和一个数值v, 返回subarray的中位数, subarray就是array里面数值大于v的数组成的. 算法就是binary search找到subarray的开始index, 然后计算中位数.

9.reverse 字符串的单词顺序, "i am boy" -> "boy am i". in-place的, 算法就是整个string reverse一遍, 然后每个单词再reverse一遍.

YP:

这家公司在洛杉矶, 是一个广告公司, 规模也不小了. offer在洛杉矶算比较高的了, package有110K. 我投的data warehouse engineer. 题目全是数据库和SQL的, 算法题目都比较简单.

1.实现iterator.

2.BST序列化和反序列化.

3.SQL的话, 都是简单的设计, 还有Query, query最难的就是输出每个group的最大值. 比如有enrollment(student, class, score)和student两张表, 输出每个class的成绩最高的学生的名字和分数.

最后分享一点点面试心得:

1.电话面试的话, 大家应该都有两个显示器, 一个用来打代码, 另外一个屏幕可以把自己之前写的算法题目代码打开, 如果遇到之前写过的, 直接搜, 或者Google, leetcode都行. 当然, 搜的时候注意键盘声音要小.

2.onsite, 如果遇到之前做过的题, 你要么直接给面试官说做过了, skip到下一题(理论上如果你胆子够大, 遇到一个很难的题目, 也可以假装说做过了, 要求skip, 不过可能被拆穿).

要么就假装没做过, 演戏. 演就一定要演真一点, 不要一口气3分钟就直接把昨晚背的代码写出来, 又optimal又bug-free的, 这样也太明显了. 最好还是一步一步的来, 就当重新做了一遍, 从简单的算法入手, 一步一步优化, 和面试官"沟通", 假装灵光一闪, aHa, 得到optimal的solution, 化身影帝, 大功告成.

千万不要做到一半, 给面试官说自己之前做过这个题目, 我有血的教训. 下场就是不仅这道题不算, 面试官还认为你不诚实, 而且还没时间做下一道题目.

3.白人普遍fair, 不会刁难也不会放水. 三哥三姐看RP, 校友都很好, 毕竟都是一个算法老师教出来的, 同师同门, 不是校友被黑出翔的几率很大. 中国人都很好, 我就Twitter遇到1个国人. 不过我有同学RP爆发, Google onsite, 4轮3个中国人, 这feel...

4.找工作期间多攒RP, 从小事做起, 比如没事打扫house卫生, 清理灶台, 倒垃圾, 接送其他要面试的同学去机场. 这辈子没有比这段时间更需要RP的时候了.

写了这么多面经, 也差不多业界良心了. 衷心感谢之前分享自己面经的同学, 不管是mitbbs还是地里的.

我最后选择去Facebook, package比其他offer高不少, 毕业入职后, 只要没被layoff,  联系我内推肯定没问题. 祝大家找工作顺利.

补充内容 (2014-4-24 06:10):
Zillow面试的时候, 第四轮也是最后一轮是CTO亲自上阵, 问简历和一个简单的log分析问题. 如果你没见到CTO, 或者只面了3轮, 基本估计是挂了.

补充内容 (2014-4-25 01:25):
在所有的leetcode solution博客里面, 对于Java来说, 这个"二娃"的博客讲得不错:http://www.cnblogs.com/lichen782 ... ow_substring_3.html
当然还有那个: programcreek.com.

补充内容 (2014-4-25 01:28):
CTCI如果有不理解的地方, 这个中文网站上包括了所有的CTCI solution的中文详解: http://hawstein.com/posts/ctci-solutions-contents.html

补充内容 (2014-4-25 01:30):
如果要准备系统设计题(NewsFeed之类), 这两个博客讲得很好, 看看面试就够用了:
http://dongxicheng.org/search-en ... ng-in-finging-jobs/
http://blog.csdn.net/sigh1988/article/details/97903

补充内容 (2014-4-25 01:33):
上面那个系统设计问题的第二个网站链接错了, 应该是:
http://blog.csdn.net/sigh1988/article/details/9790337

补充内容 (2014-4-26 01:20):
关于简历应该怎么弄, 60楼我写了一点点个人经验.
关于GPA, 我觉得其实不太重要, 低于3.5就别写在简历上了, Google, Oracle会要非正式的成绩单.

补充内容 (2015-5-1 05:31):
如果有自信的话, 希望找FB内推可以联系我. 把自己的背景和简历发送到exsonic@163.com, 以"FB内推"为标题即可.

Tsien 发表于 2014-4-25 09:46
帮忙搬运下第一个link， 翻墙还是打不开。。。

发信人: peking2 (clojure), 信区: JobHunting
标  题: 我的面试题总结
发信站: BBS 未名空间站 (Sat Oct 26 19:32:12 2013, 美东)

好多人问，我就发到这里吧。

面试题的构成和分类

首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。


我认为一道面试题由以下几个方面组成的

Question

Data structure in question

Data structure in solution

Algorithm in solution

Coding


题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。


问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构


解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。


算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定，相应的数据结构也就确定了。这两个没有先后的关系，但解决方案
中的数据结构和算法具有非常紧密的联系。


代码：非常关键。代码就是解决方案的数据结构和算法的实现了。目前来看，题目，数
据结构和算法在面试中出现的类型比较固定，因此代码的好坏则是拉开面试者水平的一
个有效手段。这也是为什么F，G如此看中代码的质量了。我发现上面几点比较容易突击
，但是写代码的功力还是需要实打实的积累的。


总结面试题目的关键就是要把面试题目进行分类之后分析。由于面试题目由以上几个部
分组成并且混杂在一起，因此怎样合理的分类就变得非常的困难。其实Careercup150的
分类就比较好，它是这样进行分类的。

数据结构：Arrays and Strings, Linked Lists, Stacks and Queues, Trees and
Graphs

算法：Bit Manipulation, Mathematics and Probability, Recursion and
Dynamic Programming, Sorting and Searching

但是我感觉这样分类比较适合初级阶段学习，并不适合系统地对面试题目进行分析。我
其实目前也没有什么特别好的idea，想跟着感觉先来，可能慢慢就能悟出更多了。


Peking2面试题总结(2) - Two/Three pointers
简称two pointers吧。大概把分类粗略的搞了一遍（http://leetcode.cloudfoundry.com/),
发现利用two pointers解决的题目数量很大。two pointers我指的是一类题，而不一定
是真正的two pointers,
比如可能是three pointers, 也可能不是pointer， 而是index。这类题基本上就是发
生在array,
string, linked
list这三种数据结构上，是一种基本的算法和编程技巧，同样超高频率的出现，可以说
是面试必遇的题。

two pointers常常和其他的算法混杂起来出现。比如binary search本身也可以归类为
two
pointers的。如果这样算的话，Leetcode上边1/4的题目都跟它相关。因此，two
pointers是必须熟练掌握的基本编程技巧。


Two pointers大概分三种类型

1. 两个pointers从头往后走：感觉绝大多数的linked
list的题目都涉及到这个操作，当然还有array。这类题目很多时候又可以称为sliding
window。

Implement strStr()

Longest Substring Without Repeating Characters

Minimum Window Substring

Remove Duplicates from Sorted Array &
II

Remove Duplicates from Sorted List & II

Remove Element

Remove Nth Node From End of List

Reverse Linked Llist II

Rotate List

Substring with Concatenation of All Words

Swap Nodes in Pairs
2.
两个pointers从两头往中间走：一般面试出现的的都是singly linked list,
因此这类题主要是array题。

3Sum

3Sum Closest

4Sum

Container With Most Water

Sort Colors

Trapping Rain Water

Two Sum

Binary search (will discuss it in a separate section)
3.
两个pointers控制两个不同的数组或链表：一般出现在跟merge相关的题目上。

Add Binary

Add Two Numbers

Merge Sorted Array

Merge Two Sorted Lists

Multiply Strings

Partition List


Peking2面试题总结(3) - Permutation and Combination
基本题，但是非常重要。面试中碰到任何一题一点也不奇怪。PIE,
CC150和Leetcode都不约而同地包含了这类题。把这些题目做熟是必须的。基本上来说
这类题的解法都是DFS，程序的大体框架非常类似，只是根据题目的要求代码稍作修改
。当然每道题也有不同的解法，但是你应该根据自己的喜好把这类题目的解决方案统一
化。熟悉了这类题目以后对于DFS(will
be discussed in a separate section)
的理解会非常深刻。基本上一般的DFS的题目应该没什么问题了。

无论是排列还是组合，这类题都有一个变形，就是要求不能有重复的输出。PIE和CC150
都没有提到相应的解法，大家应该很好的体会一下。如果没有相应的准备，属于面试的
时候比较容易跪的题目。


Permutation

输入没有重复：Permutations, CC150 9.5, PIE Chapter7 Permutations of a
String
输入有重复，输出不能有重复：Permutations
II


Next Permutation: 经典算法，背吧

Permutation Sequence: 非常有意思的题目


Combination

纯粹的subset

输入没有重复：Subsets, CC150 9.4, PIE Chapter7 Combinations of a
String
输入有重复，输出不能有重复：Subsets
II


需要满足一定要求的组合

一个元素只能取一次(输入没有重复): Combinations

一个元素可以取多次(输入没有重复): Combination Sum, CC150
9.8
一个元素只能取一次(输入有重复，输出不能有重复）:
Combination Sum II


Gray Code: 具有subset的序列特点 （考虑CC150 9.4 Solution#2:
Combinatorics)


Peking2面试题总结(4) - 数据结构和算法

下边是我认为面试中常见的数据结构和算法，以Java的类库作为标准。


数据结构

Array, ArrayList

String, StringBuffer

LinkedList

HashMap, HashSet

Stack and Queue

Tree:

BT: binary tree

BST: binary search tree,

Balanced BST (red-black tree): TreeMap, TreeSet

Trie: prefix tree

Heap: PriorityQueue
Grpah


注意：

Array和Linkedlist是最最基本的数据结构，因为他们可以构造很多其他的数据结构，
比如String
(C语言里String就是字符数组），HashMap, Stack和Queue
(Java里Queue就是LinkedList实现了Queue的interface;
Ruby里stack和queue都是array）, 以及Heap。

Heap is a tree logically, but array physically.

HashMap, Stack and
Queue通常不会出现在问题里的数据结构中，因此一般作为solution的数据结构。但是
面试中也常会让你实现这三种数据结构，另外就是CC150的3.2和3.5都是典型的Stack和
Queue的题。Leetcode中并不涵盖这些内容，这几种数据结构在Leetcode中都是作为
solution数据结构出现的
(没有的原因是这些题目不太适合OJ，因此需要单独练习）。

目前Leetcode还不包含graph的题型



算法

Sort: quick sort, merge sort, count sort, heap sort, bucket sort,
radix sort, external sort, K selection etc.

Merge: 2 array/list merge, k-way merge, interval merge
etc.

Binary search:

Stack:

Recursion and Iteration:

DFS：pre-order, in-order, post-order for trees

BFS: 需要用Queue

DP: Top down and bottom up

Greedy:

Toposort: 需要用Queue


注意：

Leetcode并没有包含各种sort算法，而通常面试很少让你直接去实现sort算法，但是大
部分的相关编程技巧是包含在很多题目当中的,
比如quick sort的two pointers。

Merge跟sort是紧密相关的，单独拿出来是因为有很多这个类型的题目，需要一起总结
。Merge操作的对象基本都是已经排好序的。

Stack虽说是数据结构，但是一般出现在solution里，因此代表了一类算法

Toposort面试作为难题也很有可能遇到，目前Leetcode还没有包括进去


Peking2面试题总结(5) - Binary search and divide and conquer

玩竞赛对面试不利的一个地方就是面试经常遇到的数据结构比如LinkedList, Tree, 和
算法Binary
search，竞赛很少涉及到，因此一直心里都感觉到有些不安。

Binary search非常tricky，虽说道理简单，但是面试的时候却很容易出bug，因此总结
一下是必须的。假设i=0,
j=A.length-1, 我做了一下LeetCode上的所有binary
search的题目，发现了以下几点值得注意。


终止条件不同 i<=j, i<j

mid的上下取向不同 i+(j-i)/2, j-(j-i)/2

如何合理分半

分半的时候取=mid, mid-1, or mid+1


Search a 2D Matrix： 这是一道普通的binary search。终止条件i<=j,
mid取向i+(j-i)/2, 分半的时候=mid-1 or mid+1。

Search for a Range：这道题需要终止条件i<j,
mid取向两种都需要用到，分半的时候需要用到=mid。我发现一般＝mid的时候，终止条
件往往是i<j,
不然会有死循环。


如何合理分半：下边这几道题都很tricky，分半的时候都有各自的特点，很不容易一次
写对。需要多多练习和体会。

Search in Rotated Sorted Array

Search in Rotated Sorted Array II

Median of Two Sorted Arrays


还有一个有趣的现象就是很多数学相关的题目也是通过binary search来解决的：

Divide Two Integers：这题没做过面试也容易跪

Pow(x, n)

Sqrt(x)：其实算是一道典型的binary
search题目，不过里边包括了几个tricky的地方，很难一次写对


总的来说，LeetCode上边的这些binary
search的题目cover的还比较全面，而且题目全部是面试高频题，需要练习一次写对。



Peking2面试题总结(6) - Linked List




首先LeetCode上几乎所有的Linked list的题目都可以用two pointers来解决，或者会
用到two
pointers这个基本编程技巧。因此two pointers跟linked list是紧密相关的。因为two
pointers以前已经总结过了，就不多讲了。


其次，因为LinkedList和Array/ArrayList一样都具备有List的特性，因此很多题目都
出现在了两种数据结构上，或者说很多题目都是可以把这两种数据结构互换的。比如：

Add Two Numbers

Convert Sorted List to Binary Search
Tree

Insert Interval

Merge Intervals

Merge k Sorted
Lists

Merge Two Sorted
Lists

Remove Duplicates from Sorted
List

Remove Duplicates from Sorted List
II


第三，LinkedList的题目大多自然而然使用iteration来解决的，但是我发现有些时候
iteration比较容易出bug，换成recursion实现更容易。面试的时候万一iteration卡住
可以换换recursion的思路。


第四，dummy head非常有用，可以使代码简洁很多，并且容易写bug
free的code。这个技巧可以大量使用。


第五，今天做了一遍LinkedList的题目，发现两个地方容易出bug。一是two pointers
loop完之后常常会有一个收尾的工作，比如Add Two
Numbers需要处理carrier>0的情况。二是在swap了nodes之后，新的tail需要把next置
空，不然就出现死循环了。

面试题总结(7) - Tree

一直没有总结Tree，这次想总结一下结果却发现没有什么太多可以总结的。Leetcode上
tree的题目还是比较全面的。我做了一遍发现基本上跑不出三个套路：

1. Recursive DFS

2. Iterative DFS

3. BFS


有些tree的题目比较tricky一些，但是最终解法还是逃不出这三个套路，所以我觉得面
试的时候代码的质量就变得更加的重要了。因为没有什么太多总结的，下边就随便聊一
下了。

Leetcode上graph的题目涉及的很少，不过从算法和coding来说DFS，BFS完全适用于
tree和graph。因此，把tree的题目练好了，graph的多数题目应该也不会有什么问题才
对。当然graph涉及的算法比tree还是要多的，比如shortest
path,
toposort等等，但是DFS,BFS还是基本中的基本。因此做Leetcode上的tree的题目也相
当于练习了graph的题目了。


由于Tree的题目比较多，我感觉一些可以skip掉，如果时间不充裕的话。或者做一遍即
可，不需要反复练习。这些题目或者太简单，或者面试不太可能碰到。

Balanced Binary Tree

Binary Tree Level Order Traversal II


Maximum Depth of Binary Tree

Minimum Depth of Binary Tree

Same Tree

Symmetric Tree

Unique Binary Search Trees

Unique Binary Search Trees II


Pre-order, In-order, Post-order traversal
需要会recursive和iterative的两种实现方式。可惜Leetcode上只包含了In-order，有
些遗憾。


Tree的serialization/deserialization也是常常被考到的题目，这个Leetcode目前还
没有包含，当然套路还是DFS/BFS。


LinkedList和Binary Tree相互转换的题目。

Convert Sorted List to Binary Search Tree

Flatten Binary Tree to Linked List
(这题原题在CC150是一道双向链表题，不知道Leetcode上怎么改单向了。双向链表应该
更复杂一些，大家要注意一下）

rialmat 发表于 2014-4-25 22:48
LZ对简历有什么体会和建议么？什么样的简历比较容易拿到面试？

各大公司的new grad职位, 其实没有具体的技能要求, requirement都写得比较泛.

对于这种, 一般recruiter就不太看重你写的什么语言和框架, 这些说明不了能力, 因为每个人都基本写了好几个语言, 各种框架. 关键是你的experience和project那块, 所以尽量不要写course project, 最多就一个吧(最好还是best final project之类). experience这块都写"工作经历", 实习啊, 以前上的班啊, 校内的编程工作啊都行, 然后描述的时候, 别写太多, 突出重点, 基本上就是一看你就是这个项目的核心开发人员.

总之最后要的效果就是拿到这个简历看10秒钟(基本也就看下前两项experience), 基本觉得比较靠谱, 不是那种学校刚学CS, 除了几个course project, 其他啥也不会的那种.

顺便提下, LinkedIn和Github也弄好一点, 一些不太知名的小公司会在上面招人, 我收到过几个面试邀请.

写了下jump iterator，还是有些tricky的。

1. public class JumpIterator {
   
2. 
   
3.         private Iterator<Integer> iterator;
   
4.         private Integer next = null;
   
5.         public JumpIterator(Iterator<Integer> ite) {
   
6.                 this.iterator = ite;
   
7.                 next = null;
   
8.         }
   
9.        
   
10.         public int next() {
    
11.                 if (next != null) {
    
12.                         int res = next;
    
13.                         next = null;
    
14.                         return res;
    
15.                 }
    
16.                 if (iterator.hasNext()) {
    
17.                         iterator.next();
    
18.                         if (iterator.hasNext()) {
    
19.                                 return iterator.next();
    
20.                         }
    
21.                 }
    
22.                 return -1;
    
23.         }
    
24.         public boolean hasNext() {
    
25.                 if (next != null) {
    
26.                         return true;
    
27.                 }
    
28.                 if (iterator.hasNext()) {
    
29.                         next = iterator.next();
    
30.                         if (iterator.hasNext()) {
    
31.                                 iterator.next();
    
32.                         }
    
33.                         return true;
    
34.                 }
    
35.                 return false;
    
36.         }
    
37.        
    
38.         public static void main(String[] args) {
    
39.                 List<Integer> list = new ArrayList<Integer>();
    
40.                 list.add(1);
    
41.                 list.add(2);
    
42.                 list.add(3);
    
43.                 list.add(4);
    
44.                 list.add(5);
    
45.                 list.add(6);
    
46.                 list.add(7);
    
47.                 JumpIterator ji = new JumpIterator(list.iterator());
    
48.                 while (ji.hasNext()) {
    
49.                         System.out.println(ji.next());
    
50.                 }
    
51.                
    
52.         }
    
53. }
    

复制代码

好帖无人顶?

谢谢楼主！！

非常实在的帖子~顶

非常感谢~ 果然拿offer是天道酬勤+怒攒人品的结果 赞一个~

cong！自己多努力好了

big cong! 大牛啊. 楼主最后签了G家卖身契么

4.找工作期间多攒RP, 从小事做起, 比如没事打扫house卫生, 清理灶台, 倒垃圾, 接送其他要面试的同学去机场. 这辈子没有比这段时间更需要RP的时候了.


哈哈，赞这一条！！！

话说我一年半毕业的那种是不是要第二年第一学期开始找？这个时候会有公司招人么？你应该是第二年第二学期才开始找的，是么？谢谢。

补充内容 (2014-4-23 10:58):
听说facebook进去有个六周的试用期，会有10%的人转不了正。然后每年performance最后10%左右会被炒掉？

big cong!

eusoff 发表于 2014-4-23 10:57
4.找工作期间多攒RP, 从小事做起, 比如没事打扫house卫生, 清理灶台, 倒垃圾, 接送其他要面试的同学去机场. ...

是有6周的bootcamp, 入职培训+分组. 每个公司都有的performance的评级系统的, 太差被裁很正常, 你是CEO也会这么干.  就像我们当年拿到美国研究生院的录取, 来了这边, 每门课都可能挂, GPA不到3.0不能毕业一样. 这个只能尽最大努力工作吧, 其他的担心也没用. 担心这个还不如担心H1B抽不中....