acm等竞赛简介

https://legacy.gitbook.com/book/zhuyuanhao/algorithm-training/details

算法学习之路

http://zh.lucida.me/blog/on-learning-algorithms/

白板编程

http://zh.lucida.me/blog/whiteboard-coding-demystified/

继续看书，抄代码，学算法 => lintcode leetcode白板训练

程序正确性：

https://blog.csdn.net/dc_726/article/details/44785395

面试者应该做什么(项目经历+纸上代码+正确性证明)

面试前

面试之前，面试者应至少做过以下准备：

1. 拥有扎实的数据结构/算法基础
2. 知道如何利用 前条件/不变式/后条件 这些工具编写正确的程序
   https://blog.csdn.net/play_fun_tech/article/details/19626043
3. 能够在白板（或纸上）实现基本的数据结构和算法（如果 1 和 2 做到这一步是水到渠成）
4. 在 leetcode 或 careercup 上面进行过练习，了解常见的技术面试题目（我个人不鼓励刷题，但在面试前建立起对面试题的『感觉』非常重要）

面试中

确定需求

面试者在白板编程时最重要的任务是理解题目，确认需求——确定输入/输出，确定数据范围，确定时间/空间要求，确定其它限制。以最常见的排序为例：

输入：来自数组？链表？或是不同的机器？
输出：是否有重复？是否要求稳定？
数据范围：排序多少个元素？100 个？ 100 万个？ 1 亿个？这些元素是否在某个范围内？
时间要求：1 分钟？1 刻钟？一小时？
空间要求：是否常量空间？是否可以分配新的空间？如果可以，能分配多少空间？是否在内存中排序？
其它限制：是否需要尽可能少的赋值？是否需要尽可能少的比较？
有时面试官不会把题目说的特别清楚，这时就需要面试者自己去确认这些需求，不要认为这是在浪费时间，不同的需求会导致截然不同的解法，此外确认需求会留给面试官良好的印象。

白板编程

理解题目确认需求之后，面试者就可以开始在白板上编写代码，下面是一些我自己的白板编程经验：

• 先写出轮廓（大纲）
  白板编程没法复制粘贴，所以后期调整代码结构非常困难。因此我们最好在开头写出程序的大致结构，从而保证之后不会有大改；

• 确定前条件/不变式/后条件
  我们可以通过注释的形式给出代码的前条件/不变式/后条件，以划分为例：

int* partition(int *begin, int *end, int pivot) {
    int *par =  begin;
    for ( ; begin < end; begin++) {
        if (*begin < pivot) {
            swap(begin, par++)
        }
    }
    return par;
}

就不如

int* partition(int *begin, int *end, int pivot) {
    // [begin, end) should be a valid range
    int *par =  begin;
    // Invariant: All [0, par) < pivot && All [par, begin) >= pivot
    for ( ; begin < end; begin++) {
        if (*begin < pivot) {
            swap(begin, par++)
        }
    }
    // Now All [0, par) < pivot && All [par, end) >= pivot
    return par;
}

• 使用实例数据验证自己的程序
  尽管不变式足以验证程序的正确性，但适当的使用实例数据会大大增强代码的可信性，以上面的划分程序为例：

Given range [2, 3, 4, 5, 1] and pivot 3
[ 2, 3, 4, 5, 1 ]
  ^             ^
 p,b            e
[ 2, 3, 4, 5, 1 ]
     ^          ^
    p,b         e
[ 2, 3, 4, 5, 1 ]
     ^  ^       ^
     p  b       e
[ 2, 3, 4, 5, 1 ]
     ^     ^    ^
     p     b    e
[ 2, 1, 4, 5, 3 ]
        ^     ^ ^
        p     b e
[ 2, 1, 4, 5, 3 ]
        ^       ^
        p      b,e
Now we have all [0, p) < 3 and all [p, e) >= 3

• 使用缩写
  白板编程并不需要面试者在白板上写出能够一次通过编译的代码。为了节省时间，面试者可以在和面试官沟通的基础上使用缩写。例如使用 Iter 替代 Iterable，使用 BQ 替代 BlockingQueue。（此法尤其适合于 Java -_-#）

• 至少留一行半行宽
  出于紧张或疏忽，一般面试者在白板编程时会犯下各种小错误，例如忘了某个判断条件或是漏了某条语句，空余的行宽可以帮助面试者快速修改代码，使得白板上的代码不至于一团糟。
  这就延伸出了另一个问题，如果使用大行宽，那么白板写不下怎么办？一些面试者聪明的解决了这个问题：他们在面试时会自带一根细笔迹的水笔，专门用于白板编程。

不会做怎么办

相信大多数面试者都碰到过面试题不会做的情况，这里说说我自己的对策：

至少先给出一个暴力（Brute force）解法
寻找合适的数据结构（例如栈/队列/树/堆/图）和算法（例如分治/回溯/动态规划/贪婪）
从小数据集开始尝试
如果还是没有头绪，重新考虑题目的前条件，思考是否漏掉了条件（或是隐含的条件）
如果 3 分钟过后还是没有任何思路，请求面试官提示，不要觉得不好意思——经过提示给出答案远强于没有答案
面试后
个人不建议面试者在面试之后把题目发到网上，很多公司在面试前都会和面试者打招呼，有的会签订 NDA（Non Disclosure Agreement）条款以确保面试者不会泄露面试题目。尽管他们很少真的去查，但如果被查到那绝对是得不偿失。

我自己在面试之后会把面试中的编程题目动手写一遍（除非题目过于简单不值得），这样既能够验证自己写的代码，也可以保证自己不会在同一个地方摔倒两次。