第三部分：用“模式识别”来解决面试技术问题的方法学

算法面试指南

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

• 前面说这么多，并不是说非技术因素多么重要，反而是说他们多么简单
• 市面上的所有素材和大牛的教诲
  
  • 告诉你有哪些问题，告诉你答案，而从来不告诉你怎么想到这个答案（问题到答案的思维过程）
  • 大牛：”这个凭感觉” “多练习就可以了”
  • 把运气、感觉、状态、智商这些不可靠因素，转换成可以准备的可靠因素，比如长时记忆
• “模式识别”
  
  • 我的高中数学老师 “和差化积相除接万能公式”
  • 绝大多数面试问题都有模式，可以去假想满足一定的特征问题都属于一类模式，可以用某种办法解决，再去用逻辑去解释，用例子去验证。如果不满足，只需要去扩充或者修改归纳来的模式。
  • 实际上模式并不是让思考机械化，而是把理清思路，并且把大脑从重复的思维过程当中解放出来。比如用方程解决算术问题 （和尚馒头问题）- 用解析解决几何问题 - 用微积分解决物理问题。只有把过程模式化了，才能解决更复杂一个级别的问题，或者反过来说，你不再需要奇技淫巧去解决这个级别的问题。
• 从写Coding笔记开始
  
  • 任何问题实际上都有个思维过程，无论自己有没有意识到，就算是总结、抽象化简单问题的思维过程，也对复杂问题化繁为简的过程大有帮助。
  • Fibonacci 数列 - 三步走
  • subproblem -> problem: 递推公式 f(x) = Q(f(x-1), f(x-2) ...) ,到通项公式。
    
    • 最简单的就是sum和最值，有重复计算的部分，那么就可以尝试用动态规划：coin change可以去练习一下
    • e.g. decode ways
  • 是我找工作最起劲的一段过程，后来我和同学朋友整理成《程序员面试》这本书（京东当当，各大书店，ibooks，amazon，google play都有）
• 最好的结果是你不再需要这些资料
  
  • 你自己去总结，归纳，运用，自然是最好的
  • 但如果你太懒，没有时间，我也已经帮你做了大半了

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

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

• 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的解。
  • Trapping Rain Water; Best Time to Buy and Sell Stock III

• 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 Having N nodes, each with a value.Require each node running a function getSum() to get the sum of the values in the network.The values could vary with time. （网络中有N台机器，每台带有一个值，互相连接，假定他们都始终运行getSum()这样一个函数，返回值应该是网络中所有值的总和）

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 single piece of code which runs on every node simultaneously, such that when it is finished running every node in the system knows the sum of the values of all the nodes in the system.

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

ADT（抽象数据类型）与Data Structure（数据结构）的区别：
ADT代表的是有某种功能，就像是个interface（接口）；而Data Structure是一种它的具体implementation。
e.g. Hashtable也可以用BST，只要实现lookup这种功能。用程序语言表示是两个concrete的class都implement了 ICanLookup 这个interface

Linked List 是 ADT还是Data Structure?
ADT 与具体实现以至于performance是无关的
List是ADT，无论是ArrayList还是LinkedList，都可以插入删除查找。
LinkedList插入删除很高效，但是有额外的overhead，根据index随机访问很低效。

说这些，用意在于思考：我为什么要选择这个Data Structure? 实际上首先是根据问题的特征选择ADT (a sequence of numbers)，其次是根据performance的requirement来选择 (比如是一个数据流，并且需要插入删除）。
e.g. LRU缓存 - 需要插入删除的数据串，并且需要快速地检索

Stack/Queue - ADT 最简单的判定方法是他们有不同的implementation
Heap 堆栈 - Data Structure, Priority Queue 是 ADT
Queue 就是priority queue的一个特例

interface IQueue extends IPriorityQueue (where getPriority() returns getInsertedOrder());
class Heap implements IPriorityQueue;

JAVA的Stack是stack的一个实现，就像C++的PriorityQueue一样。这么命名的用意只是在于你不需要去关心内在的实现。

• 回顾上节的作业：

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 single piece of code which runs on every node simultaneously, such that when it is finished running every node in the system knows the sum of the values of all the nodes in the system.

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

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的节点可以方便地记录其子树的信息，并在节点间传递全局信息，方便检索。