Arrays

1. Array Manipulation
   问题：对于一个全部初始化为0的数组(其实初始化为0不重要)，每次将其中的一个区间\([a,b)\)里的所有数都加上一个值\(k\)，进行若干次这样的操作之后，问这个数组里的最大值？
   标准答案：比较巧妙，对于每次操作的区间\([a, b)\)，把数组的\(arr[a]\)加上\(k\)，\(arr[b]\)减去\(k\)，然后依次计算数组前\(n\)个数的和，便是每个数经过这么若干次操作之后得到的值了，取其中最大值就可以了。
   我的答案：使用线段树(segment tree，延迟每次操作要加的\(k\)值，将其累加到代表这个区间的各个节点上，求最大值遍历时再求和。虽然Hackerrank给的答案说用线段树过不了，可我就是过了，不知道数据是不是变弱了。另外一查才发现区间树(interval tree)和线段树不一样，区间树是基于红黑树的。

Stacks

2. Maximum Element
   问题：不停地将一些树压栈出栈，问你任何一个时刻栈中的最大值？
   答案：本来看难度标的是easy，以为模拟一下栈操作，每次问最大值就遍历整个栈就可以了，结果超时了。正确方法时维护一个额外的栈，用于保存当前栈里的非减序列，这样这个额外的栈的栈顶就总是当前栈里的最大值。
3. 判断出栈顺序合法性
   问题：假设有一个1到n的序列，问这个序列是否可能通过依次入栈或者出栈变成另外一个序列？
   答案：模拟操作即可，依次将元素入栈，然后和目标序列对比，检查栈顶元素是否应该出栈即可。

Linked List

3. Reverse a linked list
   问题：反转一个单链表
   答案一：搞一个栈，顺序把所有的节点压入栈，然后把所有的节点依次出栈并拼接成一个新的单链表就可以了。
   答案二：假设原有的链表头叫head，那么不停的删除head的下一个节点，并且将删除的这个节点变成链表头就可以了。
4. Cycle Detection
   问题：检测单链表是否存在循环。
   答案一：最直白的想法当然是搞个map变成查重问题。
   答案二：让两个指针以不同的步长从头开始一齐遍历，如果这个链表是存在循环的，那么这个遍历过程是可以无限进行下去的(如果不能无限进行下去那就说明这个链表里没有环了)，当这两个指针进入这个链表的圈之后，就变成了两个人绕着操场匀速跑步，一个跑的快，一个跑的慢，似乎总有一个时刻会发生后一个人与前一个人相遇的情形(之所以加了似乎，是因为这两个指针的移动是按节点跳跃前进的，是离散的，万一这两个指针在这个圈里落脚的节点是没有交集的呢)。
   我们下面来证明合理的选取两个指针遍历的步长，只要这个链表有循环，那么这两个指针就会在遍历的过程中再次相遇：假设一个指针按步长\(m\)前进，那么他落脚的节点索引序列是：\(0, m, 2m, … \)，另外一个指针按步长\(n\)前进，那么他落脚的节点索引序列是：\(0, n, 2n, … \)，假设这个链表里有一个从索引为\(a\)的节点开始的长度(就是这个循环里的元素个数)为\(T\)的循环，并且假设\(m > n\)好了，那么问题就变成了：\( m \times k = n \times k + p \times T \) 是否存在正整数\((m, n)\)使得对任意正整数\(T\)都有\(k > 0\)并且\(n \times k >= a \)的让这个不定方程成立的正整数解\((k, p)\)？把这个不定方程再稍微化简一下：\( (m – n) \times k = 0 (mod T)\)。因为不定方程如果有解的话就是有无数组解，所以有解的情况下\(k > 0\)和\(n \times k >= a\)这两个条件很好满足，就只用想办法找\((m, n)\)，使得这个不定方程总是有解就好了。显然这个不定方程总是有解的，只要让\(k\)取\(T\)的倍数就好了。
   时间复杂度分析：只要让\(k\)取\(T\)的整数倍，并且\(n \times k >= a\)。让\(k\)取一个大于等于链表长度的\(T\)的倍数好了，\(k\)就是遍历时两个指针各自移动的次数，所以这个方法是正比于链表长度的线性复杂度的算法。

Tree

1. lca
   就是如果一个节点是这两个节点的最小公共祖先的话，那么这个祖先不能比这两个节点都大或者都小。
2. tree level order traversal
   就是利用队列，宽搜的思想来做。