一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 23892|回复: 129
收起左侧

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

    [复制链接] |试试Instant~ |关注本帖
pubobi 发表于 2014-4-23 06:40:59 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 全职@GoogleZillow, YP, Bloomreach, Twitter - 内推 - 技术电面 |Pass

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
心路历程那些话就不说了. 每个找工作的人在没有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的基础知识问题, 只刷题这方面容易忽略.
. visit 1point3acres.com for more.
简历:
从我将近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:
1.写一个Stream的interface, 就是有generic, 有peek(), next(), hasNext(), append()方法. 然后写一个merge List of sorted stream, 就是的k-way merge. 然后因为是generic, 传入参数要包括一个comparator.

2.输出一堆photo, photo有文件名和时间, 输出是一堆album, 要给每个album命名名字, 最多100个photo, 然后分的时候, 要做到user-friendly. 这个面试官是个烙印, 我代码没写完. 大概的思路就是, 按照天数来分, 每个album的名字就是起止时间. 当然还有很多小细节, 比如一天的照片数可能大于100.

3.Leetcode上的minimum window string.

4.shuffle. 输入是[0,2,_,3] 输出是[0,_,2,3].  就是一个乱序数组, 其中缺少了一个值, 然后输出, 每个数值都在自己对应的index上面. 但是移动的时候, 只能把数字放在空缺的位置上, 要求移动的次数最少. (这个我也不知道optimal的方法是什么)

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代码.

7.二叉树的traverse by level和print in vertical order. 前面那个简单, 就是BFS, 后面这个要先遍历, 边遍历边给每个节点一个index, 比如root为0, 做left减1, right加1. 然后建立一个HashMap, key是index, value是list<TreeNode>

8.检测一个图是否是二分图, 就是BFS, 然后给每个节点上色.

9.找名人问题.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
10.会议室问题, 给一堆会议室的schedule(starTtime, endTime), 算出需要几个会议室才能满足要求. 解法就是新建一个class{time, isStart}, 把schedule转化成这个class, 然后对这些时间进行排序, time相同时,end排在start前面, 然后对这个排序好的list进行遍历, 需要start, meeting_room_num++, 遇到end --. 得到max
. Waral 鍗氬鏈夋洿澶氭枃绔,
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.最近在读什么书?
. From 1point 3acres bbs




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

4.Find super-prime with n digit. Super prime是一个prime, 而且所有prefix也是prime. 比如7331是super prime, 因为7, 73, 733, 7331都是prime.方法就是brutal force search + pruning, 比如第一个digit必须是2, 3, 5, 7, 后面的digit必须是奇数. 然后实现boolean isPrime(int)函数, 参考CTCI.

5.给一堆会议室安排, 返回是否有conflict.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
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.
. from: 1point3acres.com/bbs
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.
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

. 1point3acres.com/bbs
Zillow:
这是一家在西雅图的租房卖房交易平台公司,是上市公司, 总部是个海景房, new grad给面试给的很多, 有题库. Offer package刚刚高于100K, 略低于Amazon.
. visit 1point3acres.com for more.
1.Lowest common ancestor.

2.给一个数, 判定他的二进制表示是否是一个palindrome, 比如3的二进制是11, 就是palindrome.
. 鍥磋鎴戜滑@1point 3 acres
3.给了一个int数组, 里面几乎包括了32bit能表示的所有数, 但是missing了几个数字, 你要把这些数字找出来, 用最少的内存. 既然要省内存, 算法就是用bit, java里用byte[]数组,  一个bit表示一个数值是否存在.

4.Blackjack问题, 给一堆牌, 返回尽可能接近21点的组合. 因为A可以表示1或者11.

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一遍.
. 1point3acres.com/bbs


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

1.实现iterator.

2.BST序列化和反序列化.
. more info on 1point3acres.com
3.SQL的话, 都是简单的设计, 还有Query, query最难的就是输出每个group的最大值. 比如有enrollment(student, class, score)和student两张表, 输出每个class的成绩最高的学生的名字和分数.


. 1point3acres.com/bbs
最后分享一点点面试心得:
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,  联系我内推肯定没问题. 祝大家找工作顺利.

. more info on 1point3acres.com
. 1point3acres.com/bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2014-4-24 06:10):.鏈枃鍘熷垱鑷1point3acres璁哄潧
Zillow面试的时候, 第四轮也是最后一轮是CTO亲自上阵, 问简历和一个简单的log分析问题. 如果你没见到CTO, 或者只面了3轮, 基本估计是挂了.

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

补充内容 (2014-4-25 01:28):
CTCI如果有不理解的地方, 这个中文网站上包括了所有的CTCI solution的中文详解: http://hawstein.com/posts/ctci-solutions-contents.html. 1point 3acres 璁哄潧
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2014-4-25 01:30):. 1point3acres.com/bbs
如果要准备系统设计题(NewsFeed之类), 这两个博客讲得很好, 看看面试就够用了:
http://dongxicheng.org/search-en ... ng-in-finging-jobs/
http://blog.csdn.net/sigh1988/article/details/97903. From 1point 3acres bbs

补充内容 (2014-4-25 01:33):
上面那个系统设计问题的第二个网站链接错了, 应该是:
http://blog.csdn.net/sigh1988/article/details/9790337. 1point3acres.com/bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2014-4-26 01:20):
关于简历应该怎么弄, 60楼我写了一点点个人经验.
关于GPA, 我觉得其实不太重要, 低于3.5就别写在简历上了, Google, Oracle会要非正式的成绩单.

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

评分

67

查看全部评分

本帖被以下淘专辑推荐:

数字媒体技术 发表于 2014-4-25 12:15:56 | 显示全部楼层

发信人: peking2 (clojure), 信区: JobHunting. 1point 3acres 璁哄潧
标  题: 我的面试题总结. visit 1point3acres.com for more.
发信站: BBS 未名空间站 (Sat Oct 26 19:32:12 2013, 美东). Waral 鍗氬鏈夋洿澶氭枃绔,

好多人问,我就发到这里吧。
. more info on 1point3acres.com
面试题的构成和分类

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

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我认为一道面试题由以下几个方面组成的

Question

Data structure in question

Data structure in solution

Algorithm in solution. from: 1point3acres.com/bbs

Coding

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


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

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
解决方案中的数据结构:可以是in-place的,也就是利用已有的数据结构,也可能是创. Waral 鍗氬鏈夋洿澶氭枃绔,
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系,而很多问题都是一
题多解,可能采取不同的数据结构。
-google 1point3acres

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

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


总结面试题目的关键就是要把面试题目进行分类之后分析。由于面试题目由以上几个部
分组成并且混杂在一起,因此怎样合理的分类就变得非常的困难。其实Careercup150的.鐣欏璁哄潧-涓浜-涓夊垎鍦
分类就比较好,它是这样进行分类的。-google 1point3acres

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

算法:Bit Manipulation, Mathematics and Probability, Recursion and
Dynamic Programming, Sorting and Searching
.鐣欏璁哄潧-涓浜-涓夊垎鍦
但是我感觉这样分类比较适合初级阶段学习,并不适合系统地对面试题目进行分析。我
其实目前也没有什么特别好的idea,想跟着感觉先来,可能慢慢就能悟出更多了。
. visit 1point3acres.com for more.

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是必须熟练掌握的基本编程技巧。

. 鍥磋鎴戜滑@1point 3 acres
Two pointers大概分三种类型

1. 两个pointers从头往后走:感觉绝大多数的linked
list的题目都涉及到这个操作,当然还有array。这类题目很多时候又可以称为sliding.鏈枃鍘熷垱鑷1point3acres璁哄潧
window。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Implement strStr()

Longest Substring Without Repeating Characters

Minimum Window Substring
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Remove Duplicates from Sorted Array &
II
. more info on 1point3acres.com
Remove Duplicates from Sorted List & II

. from: 1point3acres.com/bbs Remove Element.1point3acres缃

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.鏈枃鍘熷垱鑷1point3acres璁哄潧

3Sum Closest
. 鍥磋鎴戜滑@1point 3 acres
4Sum

Container With Most Water
. 1point3acres.com/bbs
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
. more info on 1point3acres.com
Merge Two Sorted Lists

Multiply Strings. more info on 1point3acres.com

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

-google 1point3acres
Next Permutation: 经典算法,背吧

Permutation Sequence: 非常有意思的题目. 鍥磋鎴戜滑@1point 3 acres


Combination

纯粹的subset

输入没有重复:Subsets, CC150 9.4, PIE Chapter7 Combinations of a. Waral 鍗氬鏈夋洿澶氭枃绔,
String
输入有重复,输出不能有重复:Subsets
II
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

需要满足一定要求的组合

一个元素只能取一次(输入没有重复): Combinations
.鐣欏璁哄潧-涓浜-涓夊垎鍦
一个元素可以取多次(输入没有重复): Combination Sum, CC150
9.8. From 1point 3acres bbs
一个元素只能取一次(输入有重复,输出不能有重复):
Combination Sum II 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.鐣欏璁哄潧-涓浜-涓夊垎鍦

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

. 1point 3acres 璁哄潧
Peking2面试题总结(4) - 数据结构和算法

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


数据结构

Array, ArrayList. 1point 3acres 璁哄潧

String, StringBuffer

LinkedList
-google 1point3acres
HashMap, HashSet

Stack and Queue

Tree:

BT: binary tree. more info on 1point3acres.com

BST: binary search tree,-google 1point3acres
. From 1point 3acres bbs
Balanced BST (red-black tree): TreeMap, TreeSet

Trie: prefix tree.鐣欏璁哄潧-涓浜-涓夊垎鍦

Heap: PriorityQueue
Grpah

. 1point 3acres 璁哄潧
注意:

Array和Linkedlist是最最基本的数据结构,因为他们可以构造很多其他的数据结构,
比如String
(C语言里String就是字符数组),HashMap, Stack和Queue. Waral 鍗氬鏈夋洿澶氭枃绔,
(Java里Queue就是LinkedList实现了Queue的interface;
Ruby里stack和queue都是array), 以及Heap。

Heap is a tree logically, but array physically.-google 1point3acres

HashMap, Stack and. 鍥磋鎴戜滑@1point 3 acres
Queue通常不会出现在问题里的数据结构中,因此一般作为solution的数据结构。但是
面试中也常会让你实现这三种数据结构,另外就是CC150的3.2和3.5都是典型的Stack和.1point3acres缃
Queue的题。Leetcode中并不涵盖这些内容,这几种数据结构在Leetcode中都是作为
solution数据结构出现的. 1point 3acres 璁哄潧
(没有的原因是这些题目不太适合OJ,因此需要单独练习)。

目前Leetcode还不包含graph的题型. 1point 3acres 璁哄潧


. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
算法
. 1point 3acres 璁哄潧
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.
. 1point 3acres 璁哄潧
Binary search:

Stack:

Recursion and Iteration:.鏈枃鍘熷垱鑷1point3acres璁哄潧

DFS:pre-order, in-order, post-order for trees
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
BFS: 需要用Queue

DP: Top down and bottom up
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Greedy:

Toposort: 需要用Queue. 鍥磋鎴戜滑@1point 3 acres
. From 1point 3acres bbs

注意:. from: 1point3acres.com/bbs

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

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

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

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


Peking2面试题总结(5) - Binary search and divide and conquer. Waral 鍗氬鏈夋洿澶氭枃绔,

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

Binary search非常tricky,虽说道理简单,但是面试的时候却很容易出bug,因此总结
一下是必须的。假设i=0,. visit 1point3acres.com for more.
j=A.length-1, 我做了一下LeetCode上的所有binary
search的题目,发现了以下几点值得注意。. from: 1point3acres.com/bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
. from: 1point3acres.com/bbs
终止条件不同 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。. Waral 鍗氬鏈夋洿澶氭枃绔,

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

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
如何合理分半:下边这几道题都很tricky,分半的时候都有各自的特点,很不容易一次
写对。需要多多练习和体会。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Search in Rotated Sorted Array
. 鍥磋鎴戜滑@1point 3 acres
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. visit 1point3acres.com for more.
. visit 1point3acres.com for more.


.鐣欏璁哄潧-涓浜-涓夊垎鍦
首先LeetCode上几乎所有的Linked list的题目都可以用two pointers来解决,或者会
用到two
pointers这个基本编程技巧。因此two pointers跟linked list是紧密相关的。因为two
pointers以前已经总结过了,就不多讲了。
. 1point 3acres 璁哄潧

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

Add Two Numbers
.1point3acres缃
Convert Sorted List to Binary Search. 1point 3acres 璁哄潧
Tree
. Waral 鍗氬鏈夋洿澶氭枃绔,
Insert Interval

Merge Intervals

Merge k Sorted.1point3acres缃
Lists
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Merge Two Sorted
Lists

Remove Duplicates from Sorted.鏈枃鍘熷垱鑷1point3acres璁哄潧
List. visit 1point3acres.com for more.

Remove Duplicates from Sorted List
II


第三,LinkedList的题目大多自然而然使用iteration来解决的,但是我发现有些时候
iteration比较容易出bug,换成recursion实现更容易。面试的时候万一iteration卡住.鏈枃鍘熷垱鑷1point3acres璁哄潧
可以换换recursion的思路。. from: 1point3acres.com/bbs


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


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

面试题总结(7) - Tree

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

1. Recursive DFS. visit 1point3acres.com for more.
. visit 1point3acres.com for more.
2. Iterative DFS
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
3. BFS

.鐣欏璁哄潧-涓浜-涓夊垎鍦
有些tree的题目比较tricky一些,但是最终解法还是逃不出这三个套路,所以我觉得面. visit 1point3acres.com for more.
试的时候代码的质量就变得更加的重要了。因为没有什么太多总结的,下边就随便聊一
下了。

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
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Minimum Depth of Binary Tree

Same Tree
-google 1point3acres
Symmetric Tree

Unique Binary Search Trees

Unique Binary Search Trees II. from: 1point3acres.com/bbs


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


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


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

Convert Sorted List to Binary Search Tree

Flatten Binary Tree to Linked List-google 1point3acres
(这题原题在CC150是一道双向链表题,不知道Leetcode上怎么改单向了。双向链表应该
更复杂一些,大家要注意一下). more info on 1point3acres.com

评分

4

查看全部评分

回复 支持 2 反对 0

使用道具 举报

 楼主| pubobi 发表于 2014-4-26 01:11:37 | 显示全部楼层
rialmat 发表于 2014-4-25 22:48
LZ对简历有什么体会和建议么?什么样的简历比较容易拿到面试?
. 1point 3acres 璁哄潧
各大公司的new grad职位, 其实没有具体的技能要求, requirement都写得比较泛.

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

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

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

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

doveonthewing 发表于 2014-4-23 07:28:00 | 显示全部楼层
好帖无人顶?
回复 支持 反对

使用道具 举报

discoveryi 发表于 2014-4-23 07:34:27 | 显示全部楼层
谢谢楼主!!
回复 支持 反对

使用道具 举报

Shooter_T 发表于 2014-4-23 07:52:11 | 显示全部楼层
非常实在的帖子~顶
回复 支持 反对

使用道具 举报

weixc1234 发表于 2014-4-23 08:05:33 | 显示全部楼层
非常感谢~ 果然拿offer是天道酬勤+怒攒人品的结果 赞一个~
回复 支持 反对

使用道具 举报

johnnychou 发表于 2014-4-23 08:27:46 | 显示全部楼层
cong!自己多努力好了
回复 支持 反对

使用道具 举报

HolyPrince 发表于 2014-4-23 09:11:42 | 显示全部楼层
big cong! 大牛啊. 楼主最后签了G家卖身契么
回复 支持 反对

使用道具 举报

eusoff 发表于 2014-4-23 10:57:29 | 显示全部楼层
4.找工作期间多攒RP, 从小事做起, 比如没事打扫house卫生, 清理灶台, 倒垃圾, 接送其他要面试的同学去机场. 这辈子没有比这段时间更需要RP的时候了.


哈哈,赞这一条!!!

话说我一年半毕业的那种是不是要第二年第一学期开始找?这个时候会有公司招人么?你应该是第二年第二学期才开始找的,是么?谢谢。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2014-4-23 10:58):
听说facebook进去有个六周的试用期,会有10%的人转不了正。然后每年performance最后10%左右会被炒掉?
回复 支持 反对

使用道具 举报

Erma 发表于 2014-4-23 11:10:20 | 显示全部楼层
big cong!
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| pubobi 发表于 2014-4-23 11:38:03 | 显示全部楼层
HolyPrince 发表于 2014-4-23 09:11
big cong! 大牛啊. 楼主最后签了G家卖身契么

去FB了, Google加试后还是没过HC.
回复 支持 反对

使用道具 举报

f1371342385 发表于 2014-4-23 11:54:43 | 显示全部楼层
pubobi 发表于 2014-4-23 11:38
去FB了, Google加试后还是没过HC.

cong一计!
回复 支持 反对

使用道具 举报

eusoff 发表于 2014-4-23 13:39:29 | 显示全部楼层
pubobi 发表于 2014-4-23 11:37
是有6周的bootcamp, 入职培训+分组. 每个公司都有的performance的评级系统的, 太差被裁很正常, 你是CEO也 ...

确实是。
lz是两年的ms?
回复 支持 反对

使用道具 举报

RonHe 发表于 2014-4-23 15:27:35 | 显示全部楼层
恭喜LZ!

第一个link打不开,是不是贴错了?
回复 支持 反对

使用道具 举报

数字媒体技术 发表于 2014-4-23 22:19:42 | 显示全部楼层
RonHe 发表于 2014-4-23 15:27
恭喜LZ!

第一个link打不开,是不是贴错了?

你没FQ吧。。。买买提要翻的
回复 支持 反对

使用道具 举报

RonHe 发表于 2014-4-23 22:48:30 | 显示全部楼层
数字媒体技术 发表于 2014-4-23 22:19
你没FQ吧。。。买买提要翻的

现在好了。。:)
回复 支持 反对

使用道具 举报

数字媒体技术 发表于 2014-4-23 22:51:59 | 显示全部楼层

建议大家把原PO主二爷(peking2)的所有帖子都翻看一下,确实是大牛,很有帮助,虽然买买提90%是老屌丝,不过jobhunting版还是有不少大牛的,军版梦版就一群傻逼了。。。
回复 支持 反对

使用道具 举报

readman 发表于 2014-4-23 22:53:10 | 显示全部楼层
4.找工作期间多攒RP, 从小事做起, 比如没事打扫house卫生, 清理灶台, 倒垃圾, 接送其他要面试的同学去机场. 这辈子没有比这段时间更需要RP的时候了.. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

 楼主| pubobi 发表于 2014-4-24 00:28:54 | 显示全部楼层
eusoff 发表于 2014-4-23 13:39
确实是。
lz是两年的ms?

恩, 是的
回复 支持 反对

使用道具 举报

 楼主| pubobi 发表于 2014-4-24 00:29:49 | 显示全部楼层
RonHe 发表于 2014-4-23 15:27
恭喜LZ!

第一个link打不开,是不是贴错了?

抱歉啊, 我不知道mitbbs要翻墙...你翻墙看看吧
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 13:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表