Hacking a Google Interview

Hacking a Google Interview
Classic Question #1: 
Coin Puzzle You have 8 coins which are all the same weight, except for one which is slightly heavier than the others (you don't know which coin is heavier). You also have an old‐style balance, which allows you to weigh two piles of coins to see which one is heavier (or if they are of equal weight). What is the fewest number of weighings that you can make which will tell you which coin is the heavier one? 

Good answer: Weigh 3 coins against 3 coins. If one of the groups is heavier, weigh one of its coins against another one of its coins; this allows you to identify the heavy coin. If the two groups balance, weigh the two leftover coins. 

Not so good answer: Weigh 4 coins against 4 coins. Discard the lighter coins, and weigh 2 coins against 2 coins. Discard the lighter coins and weigh the remaining two coins.


http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_2.pdf
Classic Question #4: Reversing the words in a string

Question: Nearest Neighbor
Say you have an array containing information regarding n people. Each person is described using a string (their name) and a number (their position along a number line). Each person has three friends, which are the three people whose number is nearest their own. Describe an algorithm to identify each person's three friends. 

Good answer: Sort the array in ascending order of the people's number. For each person, check the three people immediately before and after them. Their three friends will be among these six people. This algorithm takes O(n log n) time, since sorting the people takes that much time.

Classic Question #5: Cycle in a Linked List

Classic Question #6: Data structure for anagrams
Given an English word in the form of a string, how can you quickly find all valid anagrams for that string (all valid rearrangements of the letters that form valid English words)?

Then for the pre‐computing step, go through each word in the dictionary, sort the letters of the word in alphabetical order (so "hacking" would become "acghikn") and add the sorted letters as a key in the table and the original word as one of the values in a list of values for that key. For example, the entry for "opst" would be the list ["opts", "post", "stop", "pots", "tops", "spot"]. Then, whenever you get a string, you simply sort the letters of the string and look up the value in the hash table. The running time is O(n log n) for sorting the string (which is relatively small) and approximately O(1) for the lookup in the hash table.

Question: Factorial Zeros
Without using a calculator, how many zeros are at the end of "100!"? (that's 100*99*98*...*3*2*1)

There are a bunch more 2s than 5s, so the number of 5s is also the number of 10s in the factorization. There is one 5 for every factor of 5 in our factorial multiplication (1*2*...*5*...*10*...*15*...) and an extra 5 for 25, 50, 75, and 100. Therefore we have 20+4 = 24 zeros at the end of 100!
http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_3.pdf
Question: Deck Shuffling Given an array of distinct integers, give an algorithm to randomly reorder the integers so that each possible reordering is equally likely.  

Good answer: Go through the elements in order, swapping each element with a random element in the array that does not appear earlier than the element. This takes O(n) time. 

Binary Search Trees
To remove an element from a binary search tree, we first find the node containing that element. If the node has zero children, we simply remove it. If it has one child, we replace the node with its child. If it has two children, we identify the nextsmaller or next‐larger element in the tree (it doesn't matter which), using an algorithm which we do not describe here for the sake of brevity. We set the element stored in the node to this value. Then, we splice the node that contained the value from the tree. This will be relatively easy, since the node will have at most one child. 

Question: Path Between Nodes in a Binary Tree Design an algorithm to find a path from one node in a binary tree to another. 

Good Answer: There will always be exactly one path: from the starting node to the lowest common ancestor of the nodes to the second node. The goal is to identify the lowest common ancestor. 

For each node, keep track of a set of nodes in the binary tree (using a hash table or a BST) as well as a current node. At each iteration, for each of the two current nodes, change the current node to be its parent and add it to the appropriate set. The first element that is added to one set when it is already present in the other set is the lowest common ancestor. This algorithm takes O(n) time, where n is the length of the path.

Bitwise Operations
Question: Is Power of 2
Question: Compute 2^x

Question: Beating the Stock Market
Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell. 

Good answer: Go through the array in order, keeping track of the lowest stock price and the best deal you've seen so far. Whenever the current stock price minus the current lowest stock price is better than the current best deal, update the best deal to this new value.

Classic Question #7: Ransom Note
http://massivealgorithms.blogspot.com/2014/07/algorithms-and-me-strings-ransom-note.html
We don't scan magazine string and ransom note separately but simultaneously. We scan character from ransom note, and check in hash table, if we find good. If not, we scan magazine string till we find the desired character. 
If we reach end of magazine string, return false.

If we reach end of ransom note, return true.

Question: AxisAligned Rectangles

Describe an algorithm that takes an unsorted array of axis‐aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair.

Good Answer: Create a sorted array of the x coordinates of the left and right edges of the rectangles. Then, use a "scanline" to move from left to right through the rectangles. Keep a binary search tree containing the y coordinates of the top and bottom edges of the rectangles that overlap the scanline. For each element of the array, check whether it is a left or right edge. If it is a right edge, remove the corresponding top and bottom edges from the BST. If it is a left edge, search the BST for rectangles that overlap the current rectangle; if there is one, return the overlap.
Then, add the y coordinates of the top and bottom edges of the rectangle to the BST.
The search takes O(n log n) time, since it takes O(n log n) time to sort the rectangles and each of the 2n iterations takes O(log n) time.

ModelViewController:
Model‐view‐controller (MVC) is a design pattern commonly used in user interfaces. Its goal is to keep the "data" separate from the user interface.
A program that uses model‐view‐controller uses separate programming entities to store the data (the "model"), to display the data (the "view"), and to modify the data (the "controller"). In model‐view‐controller, the view usually makes heavy use of
listeners to listen to changes and events in the model or the controller.
Model‐view‐controller is a good buzzword to whip out when you're asked a design question relating to a user interface.

Book Note 1: An Introduction to Information Retrieval 读书笔记（一）

An Introduction to Information Retrieval 读书笔记（一）
这本书是 Yahoo! Labs 老大 Dr. P 合著的，近日决定泛读一下.

IR 所谓“方法”其实也就 inverted index 搞来搞去，新的东西不多，都是从别的地方借用过来的感觉。这部分我们整理第一章到第五章的内容，这是关于建立 boolean retrieval 的基本知识。大概的分块如下：

• boolean retrieval，第 1-5 章
• vector space model 和 evaluation，第 6-8 章
• relevence 和几个 specific 的 retrieval 问题，第 9-12 章
• machine learning 方法，第 13-18 章
• web search 和 link analysis， 第 19-21 章

boolean retrieval 要解决的就是一堆“（不）含有 xxx”通过和、或连接起来的 bool 表达式下的 retrieval 问题，这最常用的 inverted index 是相对 forward index 而言：所谓前向索引就是文档编号到所包含内容（如 bag of words 表达）的关系，而倒排索引是 word 对应到哪些文档的关系。对一个较大的语料建立 inverted index 可以用一次 Map/Reduce 实现：

• mapper 输入为 doc ID 和内容，输出为 word, doc ID 的 key/value 对；
• reducer 拿到的是同一个 word 对应的 doc ID 序列，一般我们将其顺序存储到一个链表结构里面；

为了从 query 关联到对应的链表，我们可以用 hash table 或者 trie。剩下的就是处理两个 list 的交、并实现 and/or 的逻辑，事实上使用按照 doc ID 排序后的链表取交可以使用类似 merge sort 中 merge 的策略，类似的实现并也可如此。那么如果要实现“非”，也可以类似处理，只是判断是否出现在取非的部分。

有了这么一个概念，剩下的就是细化里面的一些步骤，比如抽取单词，这部分我们一般需要一些 NLP 的工具做 tokenize 获得一个一个的 token，然后根据语言做 stemming/lemmatization 这样一些 normalization 的步骤（如大小写转换）。对某些特定的问题，我们知道 stop words 可以在这个过程中去掉避免产生的 posting list 过长。为了加速 posting list 的遍历，往往加入所谓 skip pointers，将 list 分段，如每隔长度的算术平方根个 doc 加一个跳转。那么比较精细的做法往往会存下该词出现在某个文档中的频率甚至位置列表。加入这些东西以后可以做 proximity search（指定单词之间的距离不能超过多少）。

我们可以为某些 search 提供一个字典方便加入对含有 wildcard 类型 query 的支持，这一般会使用 search tree（通过前缀获得）。另一方面我们也会引入 edit distance（也叫 Levenshtein 距离）对输入有误的 query 进行修正。

建立好一个 index 需要动态的维护是一个相对较复杂的问题。增加我们可以继续前面类似的操作；删除一般需要维护一个删除列表，在合适的时候移除（lazy delete 策略）；头疼的是更新 =.=

存放的 dictionary、index 均可以用某种方式进行压缩，因此有必要研究各种分布。通常认为语料的大小  与字典的大小  满足 heap’s law，即 ；各个文档中间依照词频排序后对应的比例关系满足 Zipf’s 

law，即 。编码方式往往可以利用前缀性质和变长编码。

开源的 lucene为我们提供了一
套建立 boolean retrieval 的机制。我们可以使用 lucene 提供的简单的命令行为一个目录下面的文件建立 index，

java org.apache.lucene.demo.IndexFiles -docs your-docs-dir
java org.apache.lucene.demo.SearchFiles

进行搜索，如果希望修改已有的建立索引、搜索的流程，可以看看对应文件的源代码。

Please read full article from An Introduction to Information Retrieval 读书笔记（一）

Fibonacci heaps - 斐波那契堆

Fibonacci heaps - 斐波那契堆

斐波那契堆同二项堆一样,也是一种可合并堆。斐波那契堆的优势是：不涉及删除元素的操作仅需要O（1）的平摊运行时间。和二项堆一样，斐波那契堆由一组树构成。这种堆松散地基于二项堆，说松散是因为：如果不对斐波那契堆做任何DECREASE-KEY 或 DELETE 操作，则堆中每棵树就和二项树一样；但是如果执行这两种操作，在一些状态下必须要破坏二项树的特征，比如DECREASE-KEY或DELETE 后，有的树高为k，但是结点个数却少于2^k。这种情况下，堆中的树不是二项树。

     与二项堆相比，斐波那契堆同样是由一组最小堆有序树构成，但是斐波那契堆中的树都是有根而无序的，也就是说，单独的树满足最小堆特性，但是堆内树与树之间是无序的，如下图。

     对于斐波那契堆上的各种可合并操作，关键思想是尽可能久地将工作推后。例如，当向斐波那契堆中插入新结点或合并两个斐波那契堆时，并不去合并树，而是将这个工作留给EXTRACT-MIN操作。

http://www.keithschwarz.com/interesting/code/?dir=fibonacci-heap
This allows algorithms that rely heavily on decrease-key
 * to gain significant performance boosts.  For example, Dijkstra's algorithm
 * for single-source shortest paths can be shown to run in O(m + n lg n) using
 * a Fibonacci heap, compared to O(m lg n) using a standard binary or binomial
 * heap.
 *
 * Internally, a Fibonacci heap is represented as a circular, doubly-linked
 * list of trees obeying the min-heap property.  Each node stores pointers
 * to its parent (if any) and some arbitrary child.  Additionally, every
 * node stores its degree (the number of children it has) and whether it
 * is a "marked" node.  Finally, each Fibonacci heap stores a pointer to
 * the tree with the minimum value.
 *
 * To insert a node into a Fibonacci heap, a singleton tree is created and
 * merged into the rest of the trees.  The merge operation works by simply
 * splicing together the doubly-linked lists of the two trees, then updating
 * the min pointer to be the smaller of the minima of the two heaps.  Peeking
 * at the smallest element can therefore be accomplished by just looking at
 * the min element.  All of these operations complete in O(1) time.
http://blog.pengyifan.com/a-java-implementation-of-fibonacci-heep/

Operations  | Linked List | Fibonacci Heap
-------------------------------------------
insert      |     O(1)    |   O(1)
minimum     |     O(n)    |   O(1)
extractMin  |     O(n)    |   O(log n)
union       |     O(1)    |   O(1)
-------------------------------------------
decreaseKey |     O(1)    |   O(l)*
delete      |     O(1)    |   O(log n)*

• extractMin() deletes the node with minimum key from the heap.
• union(H) merge heap H and create a new one.
• decreaseKey(x,k) assigns to node x within the heap the new key value k, which is assumed to be no greater than its current key value.
• delete(x) deletes node x from the heap.

TODO - http://www.growingwiththeweb.com/2014/06/fibonacci-heap.html

http://www.sanfoundry.com/java-program-implement-fibonacci-heap/
FibonacciHeap.java
CHAPTER 21: FIBONACCI HEAPS

https://en.wikipedia.org/wiki/Fibonacci_heap
http://nlfiedler.github.io/2008/05/31/analysis-of-java-implementations-of-fibonacci-heap.html

Please read full article from Fibonacci heaps - 斐波那契堆

Leftist tree - Wikipedia, the free encyclopedia

Leftist tree - Wikipedia, the free encyclopedia
A leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s-value.

The name comes from the fact that the left subtree is usually taller than the right subtree.

When inserting a new node into a tree, a new one-node tree is created and merged into the existing tree. To delete a minimum item, we remove the root and the left and right sub-trees are then merged. Both these operations take O(log n) time. For insertions, this is slower than binomial heaps which support insertion in amortized constant time, O(1) and O(log n) worst-case.

Leftist trees are advantageous because of their ability to merge quickly, compared to binary heaps which take Θ(n). In almost all cases, the merging of skew heaps has better performance. However merging leftist heaps has worst-case O(log n) complexity while merging skew heaps has only amortized O(log n) complexity.

Bias
The usual leftist tree is a height-biased leftist tree. However, other biases can exist, such as in the weight-biased leftist tree.s-value
The s-value of a node is the distance from that node to the nearest leaf of the extended binary representation of the tree. The extended representation (not shown) fills out the tree so that each node has 2 children (adding a total of 5 leaves here). The minimum distance to these leaves are marked in the diagram. Thus s-value of 4 is 2, since the closest leaf is that of 8 --if 8 were extended. The s-value of 5 is 1 since its extended representation would have one leaf itself.

When inserting a new node into a tree, a new one-node tree is created and merged into the existing tree. To delete a minimum item, we remove the root and the left and right sub-trees are then merged. Both these operations take O(log n) time. For insertions, this is slower than binomial heaps which support insertion in amortized constant time, O(1) and O(log n) worst-case.

http://www.cs.princeton.edu/~wayne/cs423/lectures/heaps-4up.pdf
Read full article from Leftist tree - Wikipedia, the free encyclopedia

Binomial Heaps二项堆

Binomial Heaps二项堆
二项堆（Binomial Heap）是一种类似于二叉堆(Binary Heap)的堆结构。与二叉堆相比，其优势是可以快速合并两个堆，因此它属于可合并堆（Mergeable Heap）。斐波那契堆也是可合并堆。一个二项堆由一组二项树所构成，这里的二项树(Binomial Trees)不同于二叉树(Binary Trees)。二叉树是“左孩子，右孩子”的表示方法，而二项树是“左孩子，右兄弟”的表示方法.

二项树与二叉树最大的不同是，二项树是一棵分支数无限制的有根树(Rooted trees with unbounded branching， 下图图示)，而二叉树最多有两个分叉。

二、分支树无限制的有根数

对于多叉树，也许你会想，结点的分支增多，直接用child1, child2…, childk来取代left和right域不就得了。但是如果树中结点的子女数是无限制的，那么就不行了。因为我们不知道事先要开多大的域，通常情况下，为了防止最坏情况，会开一个很大的界，这种情况下如果多数结点只有少数子女，则会浪费大量内存空间。而左图这种“左孩子，有兄弟”的方法可以完美解决这个问题。它的每个结点包含域p[x](顶端)，left-child[x](指向结点x的最左孩子), right-child[x](指向x紧右边的兄弟)。也就是说，一个结点的所有孩子形成一个链表，这样中间就可以任意加入结点了，在加入结点到树中时，动态开辟空间，这样就不会浪费任何空间了。

三、二项树

而二项树则是一种特殊的多分支有序树。结构如右图，(右图a)二项树Bk是一种递归定义的有序树。二项树B0只包含一个结点。二项树Bk由两个子树Bk-1连接而成：其中一棵树的根是另一棵树的根的最左孩子。二项树的性质有：

1)共有2^k个结点。

2)树的高度为k。

3)在深度i处恰有C_i^k个结点。

4)根的度数（子女的个数）为k，它大于任何其他结点的度数；如果根的子女从左到右的编号设为k-1, k-2, …, 0，子女i是子树Bi的根。

右图中图(b)表示二项树B0至B4中示出了各结点的深度。图(c)是以另外一种方式来看二项树Bk。PS : 在一棵包含n个结点的二项树中，任意结点的最大度数为lgn.

四、二项堆

前边已经说过一个二项堆由一组二项树所构成，这里的二项树需要满足下列条件：

1）H中的每个二项树遵循最小堆的性质：结点的关键字大于等于其父结点的关键字。

2）对于任意非负整数k，在H中至多有一棵二项树的根具有度数k。

对于性质2，任意高度最多有一棵二项树，这样就可以用二项树的集合唯一地表示任意大小的二项堆，比如13个结点的二项堆H，13的二进制表示为（1101），故H包含了最小堆有序二项树B3， B2和B0， 他们分别有8， 4， 2， 1个结点，即共有13个结点。如下图（另外：二项堆中各二项树的根被组织成一个链表，称之为根表）

http://www.princeton.edu/~crmarsh/binomial_heaps/
Please read full article from Binomial Heaps二项堆

Binomial Heap

Binomial Heap

A binomial heap is implemented as a collection of binomial trees (compare with a binary heap, which has a shape of a single binary tree). A binomial tree is defined recursively:

• A binomial tree of order 0 is a single node
• A binomial tree of order k has a root node whose children are roots of binomial trees of orders k−1, k−2, ..., 2, 1, 0 (in this order).

Binomial trees of order 0 to 3: Each tree has a root node with subtrees of all lower ordered binomial trees, which have been highlighted. For example, the order 3 binomial tree is connected to an order 2, 1, and 0 (highlighted as blue, green and red respectively) binomial tree.

A binomial tree of order k has 2^k nodes, height k.

Because of its unique structure, a binomial tree of order k can be constructed from two trees of order k−1 trivially by attaching one of them as the leftmost child of root of the other one. This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps.

The name comes from the shape: a binomial tree of order  has  nodes at depth . (See Binomial coefficient.)

Structure of a binomial heap

A binomial heap is implemented as a set of binomial trees that satisfy the binomial heap properties:

• Each binomial tree in a heap obeys the minimum-heap property: the key of a node is greater than or equal to the key of its parent.

• There can only be either one or zero binomial trees for each order, including zero order.

The first property ensures that the root of each binomial tree contains the smallest key in the tree, which applies to the entire heap.

The second property implies that a binomial heap with n nodes consists of at most log n + 1 binomial trees. In fact, the number and orders of these trees are uniquely determined by the number of nodes n: each binomial tree corresponds to one digit in the binary representation of number n. For example number 13 is 1101 in binary, , and thus a binomial heap with 13 nodes will consist of three binomial trees of orders 3, 2, and 0

http://www.growingwiththeweb.com/2014/01/binomial-heap.html

Operation	Description	Complexity
Decrease key	Decreases an existing key to some value	$\Theta(\log n)$
Delete	Deletes a node given a reference to the node	$\Theta(\log n)$
Extract minimum	Removes and returns the minimum value given a reference to the node	$\Theta(\log n)$
Find minimum	Returns the minimum value	$O(\log n)$*
Insert	Inserts a new value	$O(\log n)$
Union	Combine the heap with another to form a valid binomial heap	$\Theta(\log n)$**

* This can be reduced to $\Theta(1)$ by maintaining a pointer to the minimum element
** Where $n$ is the size of the larger heap

A binomial heap is made of a series of binomial trees each of which have a unique order. The order of a binomial tree defines how many elements it can contain, namely $2^{order}$. Each tree of the order $x$ is constructed by linking trees of the order together.

An interesting property of the structure is that it resembles the binary number system. For example, a binomial heap with 30 elements will have binomial trees of the order 1, 2, 3 and 4, which are in the same positions as the number 30 in binary ‘11110’.

Links
The typical method of implementing the links between nodes is to have pointers to a parent, sibling and child. A tree does not have a direct link to all it’s immediate children, instead it goes to its first child and then iterates through each sibling. Here is an illustration of the regular pointer structure for a binomial tree.

Please read full article from Binomial Heap

Matrix Multiply - 矩阵乘法

Matrix Multiply - 矩阵乘法

     两个矩阵 A，B：A 的列数等于 B 的行数，则A、B可以相乘。即，如果 A = （a_ij）是一个m * n的矩阵，B =（b_jk）是一个 n * p 的矩阵，则它们的乘积 C = AB 是 m * p 矩阵 C = （c_ik）。

    学过计算机图形学，会发现，不管是二维图形的平移，旋转，缩放，三维图形的取景变换，投影变换等都是通过矩阵乘法来实现，例如，二维点P（x，y）平移（tx，ty）后得到 P’(x’，y’)，可以通过矩阵计算：

                                                   

                                              

                                             

求矩阵相乘的通用公式为：

还有一个常见用法，求斐波那契数列：               

     所以当求 Fn 时可以用求幂来快速求出，而求幂也是建立在矩阵乘法的基础上：

                        

     矩阵相乘有两种方法，普通的矩阵乘法（Matrix Multiply）和Strassen算法。

最普通的矩阵乘法

Matrix operator * (Matrix a, Matrix b) {

    Matrix ret;

    ret.init(a.n, b.m);

    for (int i = 0; i < a.n; i++) {

        for (int k = 0; k < a.m; k++) if (a.mat[i][k]) {

            for (int j = 0; j < b.m; j++) if (b.mat[k][j]) {

                ret.mat[i][j] = ret.mat[i][j] + a.mat[i][k] * b.mat[k][j]; 

                if (ret.mat[i][j] >= mod) {

                    ret.mat[i][j] %= mod;

                }//if

            }//for(j)

        }//for(k)

    }//for(i)

    return ret;

}//乘法

矩阵加法只需简单的将两个矩阵的元素相加：

Matrix operator + (Matrix a, Matrix b) {

    Matrix ret;

    ret.init(a.n, a.m);

    for (int i = 0; i < a.n; i++) {

        for (int j = 0; j < a.m; j++) {

            ret.mat[i][j] = a.mat[i][j] + b.mat[i][j];

            if (ret.mat[i][j] >= mod) {

                ret.mat[i][j] %= mod;

            }

        }

    }

    return ret;

}//加法

矩阵求幂

Matrix operator ^ (Matrix a, int b) {

    Matrix ret = a,  tmp = a;

    ret.init_e();

    for ( ; b; b >>= 1) {

        if (b & 1) {

            ret = ret * tmp;

        }

        tmp = tmp * tmp;

    }

    return ret;

}//

幂求和，即求S = A + A² + A³ +… + A^k  ，同样的二分思想，但是利用递归，可以很快求出：

//递归幂求和

//用二分法求矩阵和,递归实现 

Matrix Power_Sum1(Matrix a, int b) {

    Matrix ret = a;

    ret.init_e();

    if (b == 1) {

        return a;

    } else if (b & 1) {

        return (a ^ b) + Power_Sum1(a, b - 1);

    } else {

        return Power_Sum1(a, b >> 1) * ((a ^ (b >> 1)) + ret);

    }

}

//非递归幂求和

Matrix Power_Sum2(Matrix a, int b) {

    int k = 0 ,ss[32];

    Matrix tp1, tp2, ret;

    tp1 = tp2 = ret = a;

    ret.init_e();

    while (b) {

        ss[k++] = b & 1;

        b >>= 1;

    }

    for (int i = k - 2; i >= 0; i--) {

        tp1 = tp1 * (tp2 + ret);

        tp2 = tp2 * tp2;

        if (ss[i]) {

            tp2 = tp2 * a;

            tp1 = tp1 + tp2;

        }

    }

    return tp1;

}

二、Strassen算法

     Strassen算法核心思想是分治，是一种递归算法，运行时间为O（n^lg7） = O（n^2.81），当 n 很大时，优化很明显，在普通的矩阵乘法中，C = A * B，按照：

     每计算一个元素C[i，j]，需要做 n 个乘法和 n – 1 次加法。因此，求出矩阵 C 的 n² 个元素所需的计算时间为0（n^3）。Strassen算法的分治体现在：假设 n 是 2 的幂，将将矩阵A，B和C中每一矩阵都分块成为 4 个大小相等的子矩阵，每个子矩阵都是n / 2 × n / 2的方阵。由此可将方程C = AB重写为:

   由此可得

     可以看出，进行了8次乘法，4次加法，当子矩阵的阶大于2时，为求2个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降为2，利用这个简单的分治策略，最后可以得出：T（n） = 8T（n / 2) + O（n²），但是这个式子的解任然为T（n）= O（n³），和普通的方法效率一样，没有任何提高，原因是上边的四个式子并没有减少矩阵乘法的次数（乘法极其耗费时间，学过底层二进制计算的，必然了解，而加减操作非常轻松），所以改进算法的关键是，减少乘法次数。

     Strassen算法的高效之处，就在于，它成功的减少了乘法次数，将8次乘法，减少到7次。不要小看这减少的一次，每递归计算一次，效率就可以提高1 / 8，比如一个大的矩阵递归5次后，（7 / 8）⁵ = 0.5129，效率提升一倍。不过，这只是理论值，实际情况中，有隐含开销，并不是最常用算法，《算法导论》中给出四条理由：1）隐含的常数因子比简单的O（n3）方法中的常数因子要大。2）矩阵是稀疏矩阵时，为稀疏矩阵设计的方法更快。还有两点已经被缓解，可以不考虑。所以，稠密矩阵上的快速矩阵乘法实现一般采用Strassen算法。

M1 = (A0 + A3) × (B0 + B3)

M2 = (A2 + A3) × B0

M3 = A0 × (B1 – B3)

M4 = A3 × (B2 – B0)

M5 = (A0 + A1) × B3

M6 = (A2 – A0) × (B0 + B1)

M7 = (A1 – A3) × (B2 + B3)

C0 = M1 + M4 – M5 + M7

C1 = M3 + M5

C2 = M2 + M4

C3 = M1 – M2 + M3 + M6

      求解M1，……，M7总共7次乘法，其他都是加法和减法，比如将C0扩展开后，最后结果是，C0 = A0 * B0 + A1 * B2，《算法导论》里有一句奇怪的话：“现在我们还不清楚Strassen当时是如何找出算法正常运行的关键——子矩阵乘积”，一次乘法的消失过程真的这么吊诡？

Please read full article from Matrix Multiply - 矩阵乘法