前言：用“模式识别”来解决SDE面试问题的方法学

Next1. Array - Sliding Window

Last updated 4 years ago

Was this helpful?

前言：用“模式识别”来解决SDE面试问题的方法学

0.1 什么是“模式识别”？有什么用

0.1.1 市面上的所有素材和大牛的教诲

告诉你有哪些问题，告诉你答案，而从来不告诉你怎么想到这个答案（问题到答案的思维过程）
大牛：”这个凭感觉” “多练习就可以了”
我们需要把运气、感觉、状态、智商这些不可靠因素，转换成可以准备的可靠因素，比如长时记忆

0.1.2 "模式识别”

我的高中数学老师给我的启发，把问题根据特征归类并总结他们的解决模式，比如：已知两角和的正弦，两角差的余弦，求两角的正弦和或余弦和，一定是用 “和差化积相除接万能公式”。虽然这些公式我早已忘记，但十多年后，我还是记得解法模式。
绝大多数面试问题都有模式，可以去假想满足一定的特征问题都属于一类模式，可以用某种办法解决，再去用逻辑去解释，用例子去验证。如果不满足，只需要去扩充或者修改归纳来的模式。
实际上模式并不是让思考机械化，而是理清思路，并且把大脑从重复的思维过程当中解放出来。比如用方程解决小学智力算术问题 (和尚馒头问题) - 用解析解决几何问题 - 用微积分解决物理问题。只有把过程模式化了，才能解决更复杂一个级别的问题，或者反过来说，你不再需要奇技淫巧去解决这个级别的问题。
总结好模式，其实是去减轻面试时候的思考负担，用平时复杂、全面的思考让面试的时候把自己从这些已经做过的思考当中解放出来。

0.1.3 如何归纳模式

任何问题实际上都有个思维过程，无论自己有没有意识到，就算是总结、抽象化简单问题的思维过程，也对复杂问题化繁为简的过程大有帮助。
- subproblem -> problem: 递推公式 f(x) = Q(f(x-1), f(x-2) ...)
  - 最简单的例子就是求sum (或求最值)，每一个问题都与前一个子问题的结果有递推关系: sum(i) = sum(i-1) + arr[i] # sum(i) 代表到i这个位置的总和
  - Fibonacci 数列 - 三步的思维过程: 先找出递推公式，再发现有重复计算部分用动态规划，再发现只用得到前两个结果所以并不需要整个DP table。

你可以参考的资料：

这本GitBook

最好的结果是你不再需要这些资料
- 你自己去总结，归纳，运用，自然是最好的
- 但如果你太懒，没有时间，我也已经帮你做了大半了

0.2 “模式识别”的思维方法和举例

我们来模拟一下用“模式识别”和我们之前提到的原则来应对面试（而不只是解决这个题目）注意所有的讲解都会尽量以英文术语为主，一方面是避免混淆，另外一方面通过这些希望大家养成程序中用英文规范命名的习惯。

每个问题我们总是可以先进行题意的“翻译"，再识别模式，找到题目模式对应的解法。接下去就只是把解法翻译成code了。

e.g.1 Sort a number of people by their ages.（对一群人按照年龄排序）

题目特征：age是离散的，number of people 与 age range 相比较 (面试表现机会: input的分布特征，排序要求时间还是空间优先)

模式: Key分布密集的排序问题，一般可以使用Bucket Sort(Count sort)，将Key值直接作为其index存入table。

面试表现机会：结果有没有可能超过integer上限？

如果当前节点的解依赖于两边的解，则可考虑先顺序遍历，记录DP Table，再倒序遍历，与DP Table里的解合并。

e.g.3 Design the data structures for a very large social network and an algorithm to show the connection between two people （为一个大规模的社交网络设计数据结构，以及计算两者之间关系的算法）

题目特征: 大数据前提下的问题

对这类问题一般采用D&C策略，即对问题进行预处理，将问题的输入进行分割、归类（sorting），放入相应的Bucket（单机上的某一块Chunk，或者分布式系统中的一台单机），再对每个Bucket进行后期处理，最后合并结果。

整个过程中应该用hash提供全局lookup办法，对于Memory Limits问题一般可以使用简单的hash function；对Scalability问题一般可以用hash table来记录输入对象的key与machine之间的映射。

e.g.4 N nodes, each node consists of a couple fields and methods. These are:

int id; //every node has an ID. All of these IDs are sequential, and begin with 0. 
int val; //every node has a value  
int max; //max = N. Every node knows how many nodes are in the system.  
void send(int idTo, int payload);  
int recv(int idFrom);

Write a function getSum which runs on every node simultaneously, which returns the sum of the value of every node. ( 网络中有N台机器，每台带有一个值，互相连接，假定他们都始终运行getSum()这样一个函数，返回值应该是网络中所有值的总和。)

首先应该从问题的特征去翻译和分析问题：每台机器上运行的代码都完全一致，但每台机器并不一定是对等的（因为每台机器有id）；机器之间有互相连接的关系；每台机器都同时发送和接收

设计的关键点：1.机器之间是怎么样的连接关系，也就是怎么样的数据结构？ 2.连接关系之间的方向性，也就是发送给谁，向谁接收？

思维过程： a. 两两互相传递 b. 假定一台为SERVER ，负责发送，其他都接收总和的值 c. 时间复杂度是否可能比O(n)更好呢？能否从机器之间并行计算的角度出发，避免不平衡的计算 (load balance)，抽象到数据结构就是用具备D&C特性的tree，通过并行计算subproblem来更快的解决problem

Binary Tree 天生具有D&C的特性，能够很方便地掌握子树的情况，并在整个数据结构中传递全局信息。

int getSum() {    //as member function of the node
    int parent = (id - 1) /2;
    int left = 2*id + 1;
    int right = 2*id + 2;

    // DFS
    int subsum = val;
    if( right < max ) subsum += recv(right);
    if( left < max ) subsum += recv(left);

    if(parent >= 0 ) send( parent, subsum);
    int sum = 0;
    if(parent >= 0) sum = recv( parent);
    else sum = subsum;

    send( left, sum);
    send(right, sum );

    return sum;
}

这是一道难以解答模式的问题，但也并非没有规律。Divide and Conquer（分治法）加上并行计算的概念。BST天生具有D&C（分治）属性，并且：利用BST维护的稳定性，BST的节点可以方便地记录其子树的信息，并在节点间传递全局信息，方便检索。

0.3 抽象数据类型与数据结构

ADT（抽象数据类型）与Data Structure（数据结构）的区别： ADT指的是有某些功能的数据类型；而Data Structure是这种数据类型的具体实现 (Implementation)，在大多数程序语言中就是一个具体的class。

ADT 与具体实现乃至performance都是无关的。
List 是 ADT，代表的是具备插入删除查找功能的列表，但这个概念并不代表具体的实现细节。无论是Array还是LinkedList，都可以插入删除查找，都是List的implementation。用程序语言来表示，就是这两个concrete的class都implement了 IList 这个interface。LinkedList插入删除很高效，但是有额外的overhead，根据index查找很低效。
ADT 最简单的判定方法是他们是否有不同的implementation：Heap和Stack就是ADT，因为可以用Array 或者 LinkedList 去实现。JAVA里的class Stack 就是ADT stack的一个实现，这样命名的用意是你不需要去关心它里面是怎么实现的，只要知道他具有stack的功能即可。

强调ADT与Data Structure的区别用意在于引出一个准备技术面试中经常被忽略的问题：

在使用一个Data Structure之前，我为什么要选择这个Data Structure去解题?

实际上首先是根据问题的特征选择ADT，比如问题的路径空间是一维的关系，还是二维的；如果是二维，那么是tree还是graph （无论这个问题给定的数据结构是什么，比如基于array of strings的graph问题）。其次是根据performance的requirement来选择具体的data structure。对于设计问题，经常需要根据需求来选择data structure的组合。

这个问题经常被忽略的原因是，我们大多数的练习，都已经预知需要使用什么Data Structure，而很多实际的面试内容，并不会告诉你这一点。所以第一步就是去选择Data Structure，而这一部分依赖于我们对数据结构的熟悉程度。

0.4 模式识别的解题流程

一般可以先通过问题的特征试图找到问题的模式，如果不可行则walkthrough 一个test case，找到我们用人脑解决这个test case的pattern。然后再对应到这种模式对应的解法

Next1. Array - Sliding Window

Last updated 4 years ago

Was this helpful?

0.1 什么是“模式识别”？有什么用

0.1.1 市面上的所有素材和大牛的教诲

告诉你有哪些问题，告诉你答案，而从来不告诉你怎么想到这个答案（问题到答案的思维过程）
大牛：”这个凭感觉” “多练习就可以了”
我们需要把运气、感觉、状态、智商这些不可靠因素，转换成可以准备的可靠因素，比如长时记忆

0.1.2 "模式识别”

我的高中数学老师给我的启发，把问题根据特征归类并总结他们的解决模式，比如：已知两角和的正弦，两角差的余弦，求两角的正弦和或余弦和，一定是用 “和差化积相除接万能公式”。虽然这些公式我早已忘记，但十多年后，我还是记得解法模式。
绝大多数面试问题都有模式，可以去假想满足一定的特征问题都属于一类模式，可以用某种办法解决，再去用逻辑去解释，用例子去验证。如果不满足，只需要去扩充或者修改归纳来的模式。
实际上模式并不是让思考机械化，而是理清思路，并且把大脑从重复的思维过程当中解放出来。比如用方程解决小学智力算术问题 (和尚馒头问题) - 用解析解决几何问题 - 用微积分解决物理问题。只有把过程模式化了，才能解决更复杂一个级别的问题，或者反过来说，你不再需要奇技淫巧去解决这个级别的问题。
总结好模式，其实是去减轻面试时候的思考负担，用平时复杂、全面的思考让面试的时候把自己从这些已经做过的思考当中解放出来。

0.1.3 如何归纳模式

任何问题实际上都有个思维过程，无论自己有没有意识到，就算是总结、抽象化简单问题的思维过程，也对复杂问题化繁为简的过程大有帮助。
- subproblem -> problem: 递推公式 f(x) = Q(f(x-1), f(x-2) ...)
  - 最简单的例子就是求sum (或求最值)，每一个问题都与前一个子问题的结果有递推关系: sum(i) = sum(i-1) + arr[i] # sum(i) 代表到i这个位置的总和
  - Fibonacci 数列 - 三步的思维过程: 先找出递推公式，再发现有重复计算部分用动态规划，再发现只用得到前两个结果所以并不需要整个DP table。

你可以参考的资料：

这本GitBook
2015年在这份笔记基础上编写的【程序员面试白皮书】( , , )

最好的结果是你不再需要这些资料
- 你自己去总结，归纳，运用，自然是最好的
- 但如果你太懒，没有时间，我也已经帮你做了大半了

0.2 “模式识别”的思维方法和举例

每个问题我们总是可以先进行题意的“翻译"，再识别模式，找到题目模式对应的解法。接下去就只是把解法翻译成code了。

e.g.1 Sort a number of people by their ages.（对一群人按照年龄排序）

题目特征：age是离散的，number of people 与 age range 相比较 (面试表现机会: input的分布特征，排序要求时间还是空间优先)

模式: Key分布密集的排序问题，一般可以使用Bucket Sort(Count sort)，将Key值直接作为其index存入table。

e.g.2 Replace each element with the product of all elements other than that element. （把数组里的每个数替换成其他数的乘积）

面试表现机会：结果有没有可能超过integer上限？

如果当前节点的解依赖于两边的解，则可考虑先顺序遍历，记录DP Table，再倒序遍历，与DP Table里的解合并。

题目特征: 大数据前提下的问题

e.g.4 N nodes, each node consists of a couple fields and methods. These are:

int id; //every node has an ID. All of these IDs are sequential, and begin with 0. 
int val; //every node has a value  
int max; //max = N. Every node knows how many nodes are in the system.  
void send(int idTo, int payload);  
int recv(int idFrom);

首先应该从问题的特征去翻译和分析问题：每台机器上运行的代码都完全一致，但每台机器并不一定是对等的（因为每台机器有id）；机器之间有互相连接的关系；每台机器都同时发送和接收

设计的关键点：1.机器之间是怎么样的连接关系，也就是怎么样的数据结构？ 2.连接关系之间的方向性，也就是发送给谁，向谁接收？

Binary Tree 天生具有D&C的特性，能够很方便地掌握子树的情况，并在整个数据结构中传递全局信息。

int getSum() {    //as member function of the node
    int parent = (id - 1) /2;
    int left = 2*id + 1;
    int right = 2*id + 2;

    // DFS
    int subsum = val;
    if( right < max ) subsum += recv(right);
    if( left < max ) subsum += recv(left);

    if(parent >= 0 ) send( parent, subsum);
    int sum = 0;
    if(parent >= 0) sum = recv( parent);
    else sum = subsum;

    send( left, sum);
    send(right, sum );

    return sum;
}

0.3 抽象数据类型与数据结构

ADT 与具体实现乃至performance都是无关的。
List 是 ADT，代表的是具备插入删除查找功能的列表，但这个概念并不代表具体的实现细节。无论是Array还是LinkedList，都可以插入删除查找，都是List的implementation。用程序语言来表示，就是这两个concrete的class都implement了 IList 这个interface。LinkedList插入删除很高效，但是有额外的overhead，根据index查找很低效。
ADT 最简单的判定方法是他们是否有不同的implementation：Heap和Stack就是ADT，因为可以用Array 或者 LinkedList 去实现。JAVA里的class Stack 就是ADT stack的一个实现，这样命名的用意是你不需要去关心它里面是怎么实现的，只要知道他具有stack的功能即可。

强调ADT与Data Structure的区别用意在于引出一个准备技术面试中经常被忽略的问题：

在使用一个Data Structure之前，我为什么要选择这个Data Structure去解题?

e.g. LRU (Least Recently Used) 缓存 - 需要插入删除的数据串，并且需要快速地检索。这里需要a sequence of numbers，所以ADT是List。而performance的requiement是快速的插入删除，以及查找，因此自然想到可以用LinkedList 结合 Hash。