p*****2
发帖数: 21240 | 1 面试题总结(1) - 面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive, iterative的要求。而根据题
目的变形与要求，可能会极大的影响到你能够采取的数据结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定，相应的数据结构也就确定了。这两个没有先后的关系，但解决方案
中的数据结构和算法具有非常紧密的联系。
代码：非常关键。代码就是解决方案的数据结构和算法的实现了。目前来看，题目，数
据结构和算法在面试中出现的类型比较固定，因此代码的好坏则是拉开面试者水平的一
个有效手段。这也是为什么F，G如此看中代码的质量了。我发现上面几点比较容易突击
，但是写代码的功力还是需要实打实的积累的。
总结面试题目的关键就是要把面试题目进行分类之后分析。由于面试题目由以上几个部
分组成并且混杂在一起，因此怎样合理的分类就变得非常的困难。其实Careercup 150
的分类就比较好，它是这样进行分类的。
数据结构：Arrays and Strings, Linked Lists, Stacks and Queues, Trees and
Graphs
算法：Bit Manipulation, Mathematics and Probability, Recursion and Dynamic
Programming, Sorting and Searching
但是我感觉这样分类比较适合初级阶段学习，并不适合系统地对面试题目进行分析。我
其实目前也没有什么特别好的idea，想跟着感觉先来，可能慢慢就能悟出更多了。 |
t**********h
发帖数: 2273 | |
l*****a
发帖数: 14598 | 3 你小不是下周就要跟二爷亲切会面了吗？
【在 t**********h 的大作中提到】
: 膜拜，牛逼，收藏
: 二爷纵欲出手了，我辈幸哉
|
t**********h
发帖数: 2273 | 4 不敢不敢。是二爷屈尊接见我等
【在 l*****a 的大作中提到】
: 你小不是下周就要跟二爷亲切会面了吗？
|
o***d
发帖数: 313 | 5 re, and mark
【在 p*****2 的大作中提到】
: 面试题总结(1) - 面试题的构成和分类
: 首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
: Leetcode上面的题目上。
: 我认为一道面试题由以下几个方面组成的
: Question
: Data structure in question
: Data structure in solution
: Algorithm in solution
: Coding
: 题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
|
c********t
发帖数: 5706 | 6 顶
说得好，好的面试应该对candidate数据结构，算法，coding三个方面分别打分。我等
面试者自然是初学的时候分别下手研究，等高级了就合三为一，融会贯通，和RPG升级
防御，内力，招式打老怪差不多。
【在 p*****2 的大作中提到】
: 面试题总结(1) - 面试题的构成和分类
: 首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
: Leetcode上面的题目上。
: 我认为一道面试题由以下几个方面组成的
: Question
: Data structure in question
: Data structure in solution
: Algorithm in solution
: Coding
: 题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
|
l**h
发帖数: 893 | 7 nice, continue please
【在 p*****2 的大作中提到】
: 面试题总结(1) - 面试题的构成和分类
: 首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
: Leetcode上面的题目上。
: 我认为一道面试题由以下几个方面组成的
: Question
: Data structure in question
: Data structure in solution
: Algorithm in solution
: Coding
: 题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
|
b*****n
发帖数: 482 | |
w****x
发帖数: 2483 | 9
一直想问你和二爷究竟是啥关系？？
【在 l*****a 的大作中提到】
: 你小不是下周就要跟二爷亲切会面了吗？
|
p*****2
发帖数: 21240 | 10
其实是师徒关系。
【在 w****x 的大作中提到】
:
: 一直想问你和二爷究竟是啥关系？？
|
|
|
l*****a
发帖数: 14598 | 11 我是外地粉丝啊.没你们那么幸运能跟偶像一起吃饭
我只好神往了。。
【在 w****x 的大作中提到】
:
: 一直想问你和二爷究竟是啥关系？？
|
l*********u
发帖数: 19053 | 12 多谢二爷总结
【在 p*****2 的大作中提到】
:
: 其实是师徒关系。
|
f*********m
发帖数: 726 | |
t**********h
发帖数: 2273 | 14 你去买瓶五粮液，哥给你带过去。。。
【在 l*****a 的大作中提到】
: 我是外地粉丝啊.没你们那么幸运能跟偶像一起吃饭
: 我只好神往了。。
|
w****x
发帖数: 2483 | 15
二爷徒弟遍天下啊
【在 p*****2 的大作中提到】
:
: 其实是师徒关系。
|
t**********h
发帖数: 2273 | 16 你跟二爷啥关系？你是女生么？
【在 w****x 的大作中提到】
:
: 二爷徒弟遍天下啊
|
l*****a
发帖数: 14598 | 17 谢了。
我看看是不是有机会混一个seattle的onsite再去求见
【在 t**********h 的大作中提到】
: 你去买瓶五粮液，哥给你带过去。。。
|
p*****2
发帖数: 21240 | 18
我是徒，他是师呀。lolhaha是论坛第一个帮助我的人。
【在 w****x 的大作中提到】
:
: 二爷徒弟遍天下啊
|
p*****2
发帖数: 21240 | 19
没在。湾区大牛太多了，不敢过去呀。
【在 f*********m 的大作中提到】
: 顶。二爷没在湾区吧？
|
l*******b
发帖数: 2586 | 20 有机会了也拜一拜，哈哈
【在 p*****2 的大作中提到】
:
: 没在。湾区大牛太多了，不敢过去呀。
|
|
|
p*****2
发帖数: 21240 | 21 面试题总结(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。
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
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 |
w****x
发帖数: 2483 | |
p*****2
发帖数: 21240 | 23
还要开新的呀。
【在 w****x 的大作中提到】
: 你这个要再开一个帖子
|
M**u
发帖数: 10158 | 24 二爷威武！
150
【在 p*****2 的大作中提到】
:
: 还要开新的呀。
|
j*****n
发帖数: 1545 | 25 牛翻天啊。。
境界已经到这个地步了，已经完全超越单纯做题了。 |
w****x
发帖数: 2483 | 26
版上没人相信我是女的
【在 t**********h 的大作中提到】
: 你跟二爷啥关系？你是女生么？
|
c*****a
发帖数: 808 | 27
你换个大爷头像
【在 w****x 的大作中提到】
:
: 版上没人相信我是女的
|
l**h
发帖数: 893 | 28 这个好!
【在 p*****2 的大作中提到】
: 面试题总结(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。
: Implement strStr()
: Longest Substring Without Repeating Characters
|
w*****t
发帖数: 485 | |
d******e
发帖数: 164 | 30 赞啊！
【在 p*****2 的大作中提到】
: 面试题总结(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。
: Implement strStr()
: Longest Substring Without Repeating Characters
|
|
|
t**********h
发帖数: 2273 | 31 内牛满面。。。
【在 p*****2 的大作中提到】
: 面试题总结(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。
: Implement strStr()
: Longest Substring Without Repeating Characters
|
e****e
发帖数: 418 | |
g********o
发帖数: 132 | |
l**b
发帖数: 457 | 34 2爷明显把所有的DP题目的难度说太低了。我觉得DP的题目一般都是4这样的，当然，你
用recusrive的做就不是4的难度，但是真的要能做出来DP的，我觉得都要有4的难度。 |
p*****2
发帖数: 21240 | 35
我感觉很多DP题都挺简单呀。比如爬楼梯的。
【在 l**b 的大作中提到】
: 2爷明显把所有的DP题目的难度说太低了。我觉得DP的题目一般都是4这样的，当然，你
: 用recusrive的做就不是4的难度，但是真的要能做出来DP的，我觉得都要有4的难度。
|
M**u
发帖数: 10158 | 36 。。。DP我觉得一向都很难。。。
，你
度。
【在 p*****2 的大作中提到】
:
: 我感觉很多DP题都挺简单呀。比如爬楼梯的。
|
p*****2
发帖数: 21240 | 37
你研究的都是啥DP呀。我看也不敢看。
【在 M**u 的大作中提到】
: 。。。DP我觉得一向都很难。。。
:
: ，你
: 度。
|
w****x
发帖数: 2483 | 38
跪求爬楼梯的那题
【在 p*****2 的大作中提到】
:
: 你研究的都是啥DP呀。我看也不敢看。
|
p*****2
发帖数: 21240 | 39 面试题总结(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) |
K*****z
发帖数: 32 | |
|
|
i**********e
发帖数: 1145 | |
t**********h
发帖数: 2273 | 42 二爷，你的dp教程准备放在第几课？
【在 p*****2 的大作中提到】
: 面试题总结(3) - Permutation and Combination
: 基本题，但是非常重要。面试中碰到任何一题一点也不奇怪。PIE, CC150和Leetcode都
: 不约而同地包含了这类题。把这些题目做熟是必须的。基本上来说这类题的解法都是
: DFS，程序的大体框架非常类似，只是根据题目的要求代码稍作修改。当然每道题也有
: 不同的解法，但是你应该根据自己的喜好把这类题目的解决方案统一化。熟悉了这类题
: 目以后对于DFS(will be discussed in a separate section) 的理解会非常深刻。基
: 本上一般的DFS的题目应该没什么问题了。
: 无论是排列还是组合，这类题都有一个变形，就是要求不能有重复的输出。PIE和CC150
: 都没有提到相应的解法，大家应该很好的体会一下。如果没有相应的准备，属于面试的
: 时候比较容易跪的题目。
|
w****x
发帖数: 2483 | 43 二爷这样写不行啊， 信息量太低， 你得至少出本书啊 |
t**********h
发帖数: 2273 | 44 +1
与leetcode一人写一本，或者双剑合璧
【在 w****x 的大作中提到】
: 二爷这样写不行啊， 信息量太低， 你得至少出本书啊
|
p*****2
发帖数: 21240 | 45
其实这次主要是为了自己总结。DP的东西貌似以前总结过了呀。
【在 t**********h 的大作中提到】
: 二爷，你的dp教程准备放在第几课？
|
p*****2
发帖数: 21240 | 46
嗯。想先总结一下。不写那么多细节先。
【在 w****x 的大作中提到】
: 二爷这样写不行啊， 信息量太低， 你得至少出本书啊
|
g*******4
发帖数: 155 | 47 LZ大概打算写几章呢？好让我们跟帖的有个准备啊 |
p*****2
发帖数: 21240 | 48
我也没确定。现在就是想到哪里总结到哪里。总结完这一遍再说。我感觉我需要总结的有
binary search
linkedlist
tree
【在 g*******4 的大作中提到】
: LZ大概打算写几章呢？好让我们跟帖的有个准备啊
|
t**********h
发帖数: 2273 | 49 请给个dp的连接？谢谢
【在 p*****2 的大作中提到】
:
: 我也没确定。现在就是想到哪里总结到哪里。总结完这一遍再说。我感觉我需要总结的有
: binary search
: linkedlist
: tree
|
p*****2
发帖数: 21240 | |
|
|
p*****2
发帖数: 21240 | 51 我整了一个博客，便于纪录和整理。后续的文章会发到博客里边去。
http://blog.sina.com.cn/leetcode |
w****x
发帖数: 2483 | 52
滔滔江水啊！~
【在 p*****2 的大作中提到】
: 我整了一个博客，便于纪录和整理。后续的文章会发到博客里边去。
: http://blog.sina.com.cn/leetcode
|
p*****2
发帖数: 21240 | |
c***p
发帖数: 221 | 54 收藏了！！！
【在 p*****2 的大作中提到】
: 我整了一个博客，便于纪录和整理。后续的文章会发到博客里边去。
: http://blog.sina.com.cn/leetcode
|
p*****2
发帖数: 21240 | 55
你还在准备面试吗？
【在 c***p 的大作中提到】
: 收藏了！！！
|
w****x
发帖数: 2483 | 56
以前看过火鸡的面试之路七步曲，蛮震撼的
【在 p*****2 的大作中提到】
: 我的算法路 (1)
: http://blog.sina.com.cn/s/blog_b9285de20101gwa5.html
: 给基础差的人看的。里边提到了火鸡，lolhaha和yangcheng.
|
O******2
发帖数: 210 | |
O******i
发帖数: 269 | 58 二爷已经修炼的炉火纯青，再度出山就是秒杀李大师的FLG了。 |
h****e
发帖数: 928 | 59 赞！二爷还是每一段总结单开一个主题吧，方便查找阅读。 |
d*********4
发帖数: 409 | |
|
|
p*****2
发帖数: 21240 | 61
好吧。下次单开一个。
【在 h****e 的大作中提到】
: 赞！二爷还是每一段总结单开一个主题吧，方便查找阅读。
|
z*******8
发帖数: 30 | |
k***x
发帖数: 6799 | 63 绝代双娇
【在 t**********h 的大作中提到】
: +1
: 与leetcode一人写一本，或者双剑合璧
|
a*****s
发帖数: 1121 | |
a*****s
发帖数: 1121 | |
f*****u
发帖数: 501 | 66 怎么办 又搞个人崇拜 跟定二爷了 不行 我要去教会 祷告一下 平静一下
【在 p*****2 的大作中提到】
: 面试题总结(1) - 面试题的构成和分类
: 首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
: Leetcode上面的题目上。
: 我认为一道面试题由以下几个方面组成的
: Question
: Data structure in question
: Data structure in solution
: Algorithm in solution
: Coding
: 题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
|
