编程之美
面试考察
基础知识
自我了解和企业文化的了解
cpu占有率问题
- 首先确定好CPU占有率的定义，如何查看（通过任务管理器，定时刷新，占有率 就是在这个周期内CPU工作的时间的占比）
- 确定好前提，只有一个进程工作。该进程工作一段时间（死循环）然后睡眠一段时间以此满足占有率比例。
- 工作时间的计算根据CPU周期，每周期执行的指令条数（将死循环转换为汇编语言）来确定循环次数，经过调整即可得到指定占有率。
- sleep的时间不可太小或太大。太小会频繁调度造成干扰，太大波形可能不对。
- 如果还有其他进程或是多核等问题如何确定占有率，可以考虑用window的api来解决这个问题。
中国象棋将帅问题
如何用一个byte来存储更多信息
- 每个位存储一个信息，总共8位
- 将8位的byte分为两部分，每部分可以存储0到16的数。（或者更多部分）可以使用移位操作来得到各部分的值。但是使用结构体中的位操作更好：
unsigned char a:4。
如果需要记录行列信息，我们可以行列分别存储，也可以一起存储，通过取余操作得到列信息。
一摞烙饼的排序
要对一个数组进行排序，每次只能将数组头部到数组某一位置的元素翻转顺序。如何得到一个排好序的数组
我们可以得到数组的最大值，经过一次翻转将其置于顶部，再将整个数组翻转置于底部。这样子就可以将最大值排除，再重复上述过程一直到得到排好序的数组。复杂度为2（n-1）。
我们可以使用穷举法（每次翻转1个，2个……n个）得到最优的方案。穷举的边界就是数组是否有序以及翻转的次数（小于2n）
买书问题
很难找到一个合适的贪心算法来解决这个问题。因此只能使用动态规划了。因为五种类型的书是一样的并没有区别，我们按书的数量排序。买当前数量和种类的书花费的钱等于买掉五类书，四类书，三类书，二类书，一类书花的钱加上剩下的书花费的钱，我们取最小值即可。
快速找出故障机器
一组数字，里面每个数都出现两次，有一个数出现1次，要求找出这个数。
一种空间复杂度为O（1）的做法。将所有的数字进行异或得到结果就是了。
如果有两个数只出现1次呢？
还是进行异或，得到的结果是两个只出现一次的数的异或值。拿其中一位值为1的，根据这一位，将所有数分为两部分（1部分该位为1，1部分该位为0），那么两部分各自的异或值就是唯一的ID值。
如果原来的全部值和是知道的，那拿全部值减去当前值就可以知道两个出现1次的数的和。同理，如果有原来全部值的乘积或平方和，可以得到另一个等式。
饮料供货
- 使用动态规划。遍历每一种可能。（从后往前）
- 动态规划的变形备忘录法。可以避免计算一些不可能到达的状态。（从前往后，用递归）
- 借助题目的限制条件，使用贪心算法。
光影切割问题
小飞的电梯调度算法
对每层楼都计算一个路径，全部遍历完成后返回一个最小值。
从一楼开始计算路径长度，可以知道路径长度会随着楼梯的上升先降后升。每次路径的变化值为（N1+N2-N3）。
高效率地安排见面会
n个人参加m个见面会，每个人参加若干个。要求尽可能快地开展见面会。可以转换为一个着色问题。如果一个人参加多个见面会，则多个见面会之间彼此相连。有相连的节点不能着同一种颜色。着色问题至今没有一个有效的算法。
一天有多场面试，每场面试有个开始时间和结束时间。要求同一时间同一地点只能有一场面试。求最少的面试场地。也可以转化为一个着色问题。但是可以使用贪心算法来解决。按开始时间将面试排序。当检查第i场面试时，从头到尾遍历前面的面试，如果已经结束结束遍历并将该颜色用来着当前面试。否则使用新的颜色。
也可以将所有的开始时间，结束时间一起来排序。遍历这个数组，遇到开始时间+1，结束时间-1。
双线程高效下载
石头的游戏
一排有序的石头，每次只能取一个或者相邻编号的两个石头，怎么保证第一个取的人能拿到最后一个石头？
先从数目小的石头入手解决这个问题。如果只有1/2个，先拿者肯定取胜。如果有三个，先拿者取中间一个取胜。如果有四个，先拿者取中间两个能取胜。如果大于等于五个呢，我们发现，先拿者只要拿走中间的一个或两个，保证剩下的两边石头数目相等。接下来后拿者拿走任一边的石头，先拿者跟着拿走另一边相应的石头，则先拿者可以保证取胜。
N块石头分成M堆，每次可以拿走任一堆中任一数量的石头。A先对N块石头分堆，然后B开始拿石头，怎么保证A能够赢？
有N,M两个变量。如果只分为一堆，A肯定输。那我们考虑分两堆的情况，如果是偶数，两边分一样的数量，那么B怎么取A跟着在另一堆怎么取就一定能赢。如果是奇数，不可以保证A赢。因为无论怎么分A分完后各堆数量的异或值肯定不是0（肯定有奇数堆拥有的石头个数是奇数），而B可以让各堆数量异或值便为0，接着A又让各堆数量变为异或值不为0的，重复下去，最后B让各堆值都变为0。
两堆石头，每次可以取任一堆的任一数量，或者两个堆相同数量的石头，怎么保证先拿者赢？
还是先从数目少的开始，列举（10*10）的情况，类似于用素数筛法解决这个问题。通过观察所有的不安全局面，可以得到数学公式来更好地解决这个问题。
连连看游戏设计
点击两个图案，首先判断两个图案是否一致，接着判断两个图案之间是否有路径，要求找到转弯次数最小（且要小于3次）的最短路径。这是寻找最短路径的一种扩展。首先，我们从一个图案出发，记录能直接到达的格子，判断是否能到达指定的图案，否则再从到达的图案出发，记录四个方向能直接到达的格子（转弯次数为1了），依次寻找下去。
构造数独
生成一个数独界面，最经典的就是使用深度优先搜索。第一个格子随意挑选一个，第二个格子随意挑选符合的一个，依次类推下去，如果有一个格子无数可选，就进行回溯。采用二维数组作为数据结构。
简单的方式是随意组成一个3*3的小矩阵（数字不重复），然后将其放在9*9的正中间，通过行置换得到左右两个矩阵，列置换得到上下两个矩阵，再对旁边四个矩阵进行扩展，可以得到结果值。
24点游戏
使用穷举法递归进行计算。（课本还有另一种好的解法）
俄罗斯方块游戏
挖雷游戏
求二进制数中1的个数
- 不断除以2
- 使用移位操作，效率更好
- 拿这个数跟这个数减去1的数相与，判断结果值是否为0，到0则退出循环。循环的次数正好等于这个数中1的个数。
- 使用分支的办法，但是如果这个数是255，要检测到最后一个分支，效率更慢。我们可以用数组存储这255个数的结果值，使用O(1)的时间就可以得到我们要的 结果（空间换时间）
给定两个正整数A和B，把A换成B需要改变多少位bit？
A和B异或，结果值计算1的个数。
不要被阶乘吓倒
得到N的阶乘十进制表示中末尾0的个数，我们可以将所有数都进行质数分解，发现只有2和5相乘才能让结果末尾有0，而2的幂次肯定比5的幂次多，所以末尾0的个数等于5的幂次。解法一便是让所有数各自去计算有5这个因子的个数，再求和就是结果了。解法二是让N这个值除以5，商就是表示有多少个数是5的倍数，再让结果值除以5（也就是原来值除以25，是25倍数的有两个5因子），重复下去，不断相加得到的结果值就是了。
N！的二进制表示中最低位1的个数，其实也就是求2这个因子的个数+1（每乘以一个2，全部数左移一位）。还是同样的方法，将N不断右移（除以2）即可。另外一种解法是，N！中含有质因数2的个数，等于N减去N的二进制表示中1的数目。
判断一个数是否为2的方幂（n & （n-1） == 0）