算法ACM和白板编程算法ACM和白板编程

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/
【算法ACM和白板编程】继续看书，抄代码，学算法 => lintcode leetcode白板训练
程序正确性： https://blog.csdn.net/dc_726/article/details/44785395
面试者应该做什么(项目经历+纸上代码+正确性证明) 面试前面试之前，面试者应至少做过以下准备：

拥有扎实的数据结构/算法基础
知道如何利用前条件/不变式/后条件这些工具编写正确的程序
https://blog.csdn.net/play_fun_tech/article/details/19626043
能够在白板（或纸上）实现基本的数据结构和算法（如果 1 和 2 做到这一步是水到渠成）
在 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,be [ 2, 3, 4, 5, 1 ] ^^ p,be [ 2, 3, 4, 5, 1 ] ^^^ pbe [ 2, 3, 4, 5, 1 ] ^^^ pbe [ 2, 1, 4, 5, 3 ] ^^ ^ pb e [ 2, 1, 4, 5, 3 ] ^^ pb,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）条款以确保面试者不会泄露面试题目。尽管他们很少真的去查，但如果被查到那绝对是得不偿失。

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