面试题总结(1) - 面试题的构成和分类

cleverman

首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在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，想跟着感觉先来，可能慢慢就能悟出更多了。

cleverman

有人想转开发可以看看。

cleverman

面试题总结(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

cleverman

看来这里转开发感兴趣的人不多。我就不贴我的文章了。如果有想转开发的去我新开的博客看看吧。我会把文章发到那里。

http://blog.sina.com.cn/leetcode