本文共 10553 字,大约阅读时间需要 35 分钟。
转自于:http://www.cnblogs.com/wei-li/p/3318929.html
0. 零基础入门 Coding interview exposed (3ed) 这个最简单了,基础比较挫的可以从这里开始 “这本书籍不是“课本”,不是“课程”,而是教你做各种常见面试题目的。熟练掌握这本书籍的内容,是你找到工作的基础。” Programming Interviews Exposed 8.0/60 | 程序员面试攻略 7.7/86 MIT的Hacking a google interview(也非常简单) 1. 系统学习 - 不能满足于给出解法,复杂度分析一样重要 careercup不难,参考二爷划的重点,早早开始做,即使先开始做前几章简单的。 Cracking the Coding Interview v5 8.9/88 挑战程序设计竞赛 9.0/72 编程之美 8.3/2289 剑指offer 8.3/159 编程珠玑 9.2/1215 复杂度分析要善于总结归纳,不妨看看算法之排序算法,一图胜千言 2. 真题 - 时间有限,编码真题练手是最直接的。 最好的教材自然就是careercup (类似的网站还有glassdoor) 3. OJ - Bug Free&Code Style比攻克难题更重要 OJ有反馈保持手感,对非ACM选手,即使是google的面试也不会太难 leetcode的题稍难一些,不过很有趣,可以参考这份难度系数表刷题(文末有附),还有一个tips(北美求职群主分类题解/九章的答案/maskray答案) codility 有分类,可以锻炼举一反三能力,比Leetcode更适合入门 九度Online Judge (基于《剑指Offer》) 如果有余力,还有很多OJ网站: interviewstreet (一些海外公司的笔试平台) projecteuler google code jam google面可以做做 九章算法弄的lintcode hihocoder 51node ITint5 英雄会 4 简历和behavior question What A GOOD Resume Should Look Like The Google Resume 8.2/38 | 金领简历 8.2/20 behavior question,准备一些类似于自我介绍、为什么xx公司一类的就行,其它的知道怎么回答就行。http://hrinterviews.blogspot.com/ (64道behavior questions)。 5.系统设计 系统设计面试题思路综述 基础知识整理 一致性哈希算法及其在分布式系统中的应用 此外,Careercup书上Large Scale和面向对象章节讲得很不错 6.资讯 水木社区-校园招聘 北邮人论坛-毕业生找工作 应届生-机器学习校招北京 一亩三分地-内推 7. 网络资源 Topcoder Tutorials 结构之法 算法之道 July的博客 程序员编程艺术 July的新书 剑指Offer:名企面试官精讲典型编程题 何海涛的博客 Python面试题集合 一亩三分地 留美招工Tips Warald mitbbs的JobHunting版(需FQ) 大牛制定的MIT算法导论公开课学习计划,配套精选的ACM题 如何下列各类公司的互联网IT类工作待遇排名 硕士码农的offer档次排行(个人版) 8.其他可供消(shao)遣(qian)的书籍 大话数据结构 8.1/336 大话设计模式 8.3/1139 鸟哥的Linux私房菜.基础学习篇 9.1/1097 UNIX环境高级编程 9.4/1531 UNIX编程艺术 9.1/1651 人人都有好工作 7.9/45 谁是谷歌想要的人才 7.4/195 浪潮之巅 9.1/10221 黑客与画家 8.8/7032 暗时间 8.5/4871 程序员面试宝典 6.1/118(强烈土豪购买这本用来烧钱...里面很多错误,找到就是赚到) 参考: http://www.1point3acres.com/bbs/thread-50411-1-1.html http://www.zzsec.org/tags.html#leetcode-ref 附: leetcode Questions Id Question Difficulty Freqency Data Structures Algorithms 1 Two Sum 2 5 array, set sort, two pointers 8 String to Integer (atoi) 2 5 string math 20 Valid Parentheses 2 5 string stack 21 Merge Two Sorted Lists 2 5 linked list sort, two pointers, merge 65 Valid Number 2 5 string math 70 Climbing Stairs 2 5 dp 88 Merge Sorted Array 2 5 array two pointers, merge 125 Valid Palindrome 2 5 string two pointers 15 3Sum 3 5 array two pointers 50 Pow(x, n) 3 5 binary search, math 73 Set Matrix Zeroes 3 5 array 98 Validate Binary Search Tree 3 5 tree dfs 127 Word Ladder 3 5 graph bfs, shortest path 28 Implement strStr() 4 5 string two pointers, KMP, rolling hash 56 Merge Intervals 4 5 array, linked list, red-black tree sort, merge 57 Insert Interval 4 5 array, linked list, red-black tree sort, merge 27 Remove Element 1 4 array two pointers 13 Roman to Integer 2 4 math 24 Swap Nodes in Pairs 2 4 linked list 67 Add Binary 2 4 string two pointers, math 129 Sum Root to Leaf Numbers 2 4 tree dfs 2 Add Two Numbers 3 4 linked list two pointers, math 12 Integer to Roman 3 4 math 22 Generate Parentheses 3 4 string dfs 23 Merge k Sorted Lists 3 4 linked list, heap sort, two pointers, merge 46 Permutations 3 4 array permutation 49 Anagrams 3 4 string, hashtable 77 Combinations 3 4 combination 78 Subsets 3 4 array recursion, combination 79 Word Search 3 4 array dfs 91 Decode Ways 3 4 string recursion, dp 102 Binary Tree Level Order Traversal 3 4 tree bfs 131 Palindrome Partitioning 3 4 string dfs 69 Sqrt(x) 4 4 binary search 26 Remove Duplicates from Sorted Array 1 3 array two pointers 83 Remove Duplicates from Sorted List 1 3 linked list 112 Path Sum 1 3 tree dfs 7 Reverse Integer 2 3 math 19 Remove Nth Node From End of List 2 3 linked list two pointers 62 Unique Paths 2 3 array dp 108 Convert Sorted Array to Binary Search Tree 2 3 tree dfs 17 Letter Combinations of a Phone Number 3 3 string dfs 39 Combination Sum 3 3 array combination 53 Maximum Subarray 3 3 array dp 63 Unique Paths II 3 3 array dp 64 Minimum Path Sum 3 3 array dp 74 Search a 2D Matrix 3 3 array binary search 82 Remove Duplicates from Sorted List II 3 3 linked list recursion, two pointers 86 Partition List 3 3 linked list two pointers 93 Restore IP Addresses 3 3 string dfs 105 Construct Binary Tree from Preorder and Inorder Tr 3 3 array, tree dfs 106 Construct Binary Tree from Inorder and Postorder T 3 3 array, tree dfs 114 Flatten Binary Tree to Linked List 3 3 tree recursion, stack 116 Populating Next Right Pointers in Each Node 3 3 tree dfs 29 Divide Two Integers 4 3 binary search, math 33 Search in Rotated Sorted Array 4 3 array binary search 34 Search for a Range 4 3 array binary search 43 Multiply Strings 4 3 string two pointers 51 N-Queens 4 3 array dfs 52 N-Queens II 4 3 array dfs 72 Edit Distance 4 3 string dp 94 Binary Tree Inorder Traversal 4 3 tree, hashtable recursion, morris, stack 103 Binary Tree Zigzag Level Order Traversal 4 3 queue, tree bfs, stack 109 Convert Sorted List to Binary Search Tree 4 3 linked list recursion, two pointers 128 Longest Consecutive Sequence 4 3 array 130 Surrounded Regions 4 3 array bfs, dfs 132 Palindrome Partitioning II 4 3 string dp 4 Median of Two Sorted Arrays 5 3 array binary search 10 Regular Expression Matching 5 3 string recursion, dp 44 Wildcard Matching 5 3 string recursion, dp, greedy 81 Search in Rotated Sorted Array II 5 3 array binary search 66 Plus One 1 2 array math 101 Symmetric Tree 1 2 tree dfs 110 Balanced Binary Tree 1 2 tree dfs 9 Palindrome Number 2 2 math 35 Search Insert Position 2 2 array 36 Valid Sudoku 2 2 array 38 Count and Say 2 2 string two pointers 80 Remove Duplicates from Sorted Array II 2 2 array two pointers 113 Path Sum II 2 2 tree dfs 3 Longest Substring Without Repeating Characters 3 2 string, hashtable two pointers 11 Container With Most Water 3 2 array two pointers 18 4Sum 3 2 array 55 Jump Game 3 2 array 59 Spiral Matrix II 3 2 array 61 Rotate List 3 2 linked list two pointers 92 Reverse Linked List II 3 2 linked list two pointers 5 Longest Palindromic Substring 4 2 string 25 Reverse Nodes in k-Group 4 2 linked list recursion, two pointers 37 Sudoku Solver 4 2 array dfs 40 Combination Sum II 4 2 array combination 42 Trapping Rain Water 4 2 array two pointers, stack 45 Jump Game II 4 2 array 47 Permutations II 4 2 array permutation 48 Rotate Image 4 2 array 54 Spiral Matrix 4 2 array 68 Text Justification 4 2 string 75 Sort Colors 4 2 array sort, two pointers 76 Minimum Window Substring 4 2 string two pointers 89 Gray Code 4 2 combination 90 Subsets II 4 2 array recursion, combination 99 Recover Binary Search Tree 4 2 tree dfs 115 Distinct Subsequences 4 2 string dp 117 Populating Next Right Pointers in Each Node II 4 2 tree dfs 124 Binary Tree Maximum Path Sum 4 2 tree dfs 31 Next Permutation 5 2 array permutation 41 First Missing Positive 5 2 array sort 84 Largest Rectangle in Histogram 5 2 array stack 87 Scramble String 5 2 string recursion, dp 97 Interleaving String 5 2 string recursion, dp 58 Length of Last Word 1 1 string 100 Same Tree 1 1 tree dfs 104 Maximum Depth of Binary Tree 1 1 tree dfs 111 Minimum Depth of Binary Tree 1 1 tree dfs 126 Word Ladder II 1 1 14 Longest Common Prefix 2 1 string 118 Pascal's Triangle 2 1 array 119 Pascal's Triangle II 2 1 array 121 Best Time to Buy and Sell Stock 2 1 array dp 6 ZigZag Conversion 3 1 string 16 3Sum Closest 3 1 array two pointers 30 Substring with Concatenation of All Words 3 1 string two pointers 71 Simplify Path 3 1 string stack 96 Unique Binary Search Trees 3 1 tree dp 107 Binary Tree Level Order Traversal II 3 1 tree bfs 120 Triangle 3 1 array dp 122 Best Time to Buy and Sell Stock II 3 1 array greedy 32 Longest Valid Parentheses 4 1 string dp 95 Unique Binary Search Trees II 4 1 tree dp, dfs 123 Best Time to Buy and Sell Stock III 4 1 array dp 60 Permutation Sequence 5 1 permutation, math 85 Maximal Rectangle 5 1 array dp, stack 很可惜二爷不再更新了,未名上Jc2013补充了一点新题 1. Clone Graph-> BFS+HashMap 2. Gas Station->DP 3. Candy->Two Pointers 4. Single Number-> Xor, HashMap, or Sum or Product way to find 5. Single Number II -> Xor, HashMap 6. Copy List with Random Pointers -> Two Pointers, HashMap with two times traverse(like clone graph) 7. List Cycle, List Cycle II, Reorder List-> Two Pointers 8. Binary Tree Preorder, Postorder recursive -> Using stack to mock recursive way, or implement like morris way. 9. LRU Cache-> HashMap + list 10. Insertion sort list -> Two Pointers 11. Sort List-> I implement merge sort, still, two pointers method, combination of merge sort list and split list 12. Word Break -> DFS DP 13. Word Break II -> DP + Backtracking 二爷的Careercup 150总结 很多人都说把这150题做了一遍或几遍,但是我感觉算法题才是重点,其他的很多题面 试基本碰不上,没看出来有必要全做。这里总结一下自己认为重要的题。 第一章 : 全部重要 (1.6, 1.7 Leetcode上有)。 1.5 面A碰到 (string compression) 1.7面Z碰到 (set 0) 1.8面Bigfish碰到 (string rotation) 第二章 (2.4, 2.5 Leetcode上有): 全部重要。 2.2面Bigfish碰到 (find kth) 第三章 : 感觉就是3.2 (min stack), 3.5 (two stack queue) 重要。两道题面M被问到过。3.6 (sort stack)感觉也有可能被考到。 第四章 (4.1, 4.3, 4.5 Leetcode上有): 感觉4.2, 4.3, 4.5,4.6, 4.7 重要。4.5 (valid BST)面E,Q碰到过 第五章:5.4 (n & (n-1)) 第六章:6.5 (drop egg) 第七章:7.3 (line intersection),7.6 (line passes most points) 第八章:8.4 (parking lot), 8.10 (hashtable) 第九章 (9.1, 9.2, 9.5, 9.6,9.8,9.9 Leetcode上有): 感觉都重要 (9.10 (stack of boxes), 9.11 (boolean expression) 貌似可以忽略 )。 第十章(10.1, 10.2, 10.3 Leetcode上有): 10.1 (merge) M碰到过两次 10.3 10.4 (external sort) E碰到 10.6 第十七章(17.8, 17.12, 17.13 Leetcode上有): 17.1 (swap number) 17.2 (tic-tac-toe) 面I遇到过 17.7 (integer->english) 17.8 (largest sum) 经典, 注意变形题 (largest product), 面RF碰到过 17.9 (frequency of occurrences) S碰到 17.11 (rand7) 17.12 (2 sum) G碰到 17.13 (BT -> Linkedlist) 第十八章(9): 18.2 (shuffle deck) 貌似经典 18.3 (random) 18.4 (count 2s) 注意思路,可能会出现类似题 18.5 (shortest distance) 18.6 (quick select) 面Z, G碰到类似题 18.9-18.12 一共50道题。其他很多题可以做练习,但是面试碰到的概率不大。上边一些题面试也很 难碰到但是是不可不练的题,比如八皇后。另外就是别完全follow书上的答案,注意看 有没有bug。希望大家能补充一下自己认为重要的。 二爷的DP总结 “不断看到有新人学习DP,想谈谈我的感受。 我大概是去年底,今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出 了一道最简单的DP题,那时我根本不知道什么是DP,在提示下用recursion做出来的, 没有用cache。 开始学习DP是在careercup 150那本书上。下面是一些感受。 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这 个定义是DP的初级阶段,有误导性,使得我在练习的时候发现很多题型用这个定义套不 上。误导性在于: 1, recursion+cache是DP不错,但是DP并不等于recursion+cache。 2, recursion的DP并不优化,因此从recursion出发做DP不是个好思路。 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出 F(n)来。当然这也是最难的。发现很多难题还是很难想到这个公式的,可能就得多练习 了,培养思路。这个定义跟careercup上的不一样的地方主要是思考的方式不同,一个 是推公式,一个是找recursion的办法。而DP的关键是推公式,如果从recursion出发的 话,很多题可能做不出来。 做DP题需要注意两点: 1. 能用iteration就不要用recursion。这也证明了careercup上的定义有局限性了。 2. DP是用空间换时间。所以DP题做熟了,应该考虑怎样优化空间了。能用常数空间就 不要用O(n), 能用O(n)就不要用O(n^2). (我觉得这也是Vissa的霸气所在。Vissa面F 的时候说过“这么简单的DP题,我从来都是用常数空间”)。 最后就是多做题才能培养思路。一般面试应该不会有很难的DP题,多练习一下有了思路 ,再能写出iteration和空间优化的解法,并且能保证少bug的话,应该面试就差不多了。”