智力题

  1. 烧绳子：有若材质一样的干根不均匀绳子，烧完一根需要1h，如何计时得到75min, 15min, 30min?

    既然不均匀，那就代表不能通过长度来直接得到30min，15min

    30min：一根绳子从头烧到尾需要1h，那从两边往中间烧的话只需要30min；

    15min：将绳子1的两头点燃，同时点燃绳子2的左端，当绳子1燃尽的时候过了30min，此时点燃绳子2的右端，并开始计时，当绳子2燃尽的时候就得到了15min；

    75min_1：可以在得到15min之后马上点燃另一根绳子，等该绳子燃尽就可以得到75min；

    75min_2：将绳子1的两头点燃，同时点燃绳子2的左端并计时，当绳子1燃尽的时候过了30min，此时点燃绳子2的右端，当绳子2燃尽的时候就得到了45min；然后再点燃绳子3的两端，当绳子3燃尽的时候就得到了75min；

  2. 老鼠喝毒酒：有1000桶酒,其中1桶有毒.而一旦吃了,毒性会在1周后发作.现在我们用小老鼠做实验,要在1周内找出那桶毒酒,问最少需要多少老鼠?

    首先利用二进制将每桶酒进行编号，1000桶酒就需要2^10才能表示，因此需要10位。

    在确定了如何对每桶酒进行编号之后，我们现在就需要确定毒酒的二进制表示中的每一位是什么。

    如果我们将1000桶酒按照二进制中第k位是否为1进行划分，然后让老鼠k去喝第k位为1的所有酒，如果老鼠k死去，证明毒酒的第k位为1，否则第k位为0.

    由于我们一共用了10位来表示毒酒，因此需要10只老鼠即可判断哪一桶是毒酒。

  3. 猜纸牌：有9张纸牌，分别为1至9。A、B、C、D四人取牌，每人取2张。现已知A取的两张牌之和是10;B取的两张牌之差是1;C取的两张牌之积是24;D取的荫张牌之商是3。请说出他们四人各拿了哪两张纸牌;剩下的一张又是什么牌?

    其实就是有8个变量，其中两两满足一个约束，总体又满足一个约束，如何确定各个变量的值。

    那我们就先把各个约束写出来。其中满足C和D的约束的组合是最少的，那么我们就从这两个人身上下手。

    从满足约束的组合数最少的人开始，遍历其所有可能的取值，然后根据其他约束去判断就可以了。

  4. 数楼层问题：有n层楼，现在你想知道在哪一层楼之下，鸡蛋不会被摔碎，如何分别用1个鸡蛋和2个鸡蛋去判断具体是哪一层楼？

    如果只有1个鸡蛋，那我们只能遍历这n层楼，因此复杂度是O(1)

    如果有2个鸡蛋，那么我们需要做的就是两次循环，假设第一次循环的步长为x，那么需要循环n / x次，即第一次从第x层往下扔，第二次从第2x层往下扔， …，最后从第n层往下扔。假设在第kx层往下扔的时候鸡蛋碎了，那么就从第kx层开始向下遍历，最多遍历x次就可以找到答案。

    那么现在就需要求这个x是多少，总共需要的循环次数是 f(x) = n / x ^ 2 + x， f’(x) = 1 - n / x ^ 2，令f’(x) = 0，得到x = sqrt(n)。也就是先按照根号n的步长遍历，然后再逐层遍历即可。

  5. 一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问最少得比多少场才能知道跑得最快的5匹马。

    首先分析一下，如果用多路归并，那么我们需要5+x次比赛才能确定最快的x匹马，那如果我们要将这个次数减小，就必须在某一次比赛中同时决出2个名次。

    先将25匹马随机划分为5组【A, B, C, D, E】，然后先跑5轮【这里是前5轮】比赛，得到每组的内部顺序。

    然后将这5组里面的第一名【A1, B1, C1, D1, E1】拉出来跑1轮【这里是第6轮】，得到这几匹马的先后顺序。假设这里A1 > B1 > C1 > D1 > E1

    由于我们要找的是所有马中跑的最快的5匹，因此第6轮比赛中跑倒数第一的那匹马所在的组的后4匹马都不能是前5了，而倒数第二的那匹马所在组的后3匹马不能是前5了，其他组同理，因此第6轮比赛之后我们就可以筛掉4+3+2+1+0 = 10匹马，那么现在场内剩下的马还有15匹。也就是说，我们在第6轮比赛中决出了真正的第一名。

    A组： [A1 A2 A3 A4 A5]

    B组： [B1 B2 B3 B4 B5]

    C组： [C1 C2 C3 C4 C5]

    D组： [D1 D2 D3 D4 D5]

    E组： [E1 E2 E3 E4 E5]

    其中加粗的代表已经被淘汰

    现在我们需要从剩下的15匹马中找出第二名。既然A1是第一名，那么第二名就只能从A2和B1中产生，只需要2条跑道就可以了，那剩余的3条跑到能否决出第三名呢？

    假设B1是第二名，那么第三名就出现在A2、B2、C1中

    假设A2是第二名，那么第三名就出现在A3、B1、C1中

    那么就是说如果我们在第7轮比赛中让A2、A3、B1、B2、C1进行比赛，就可以同时决出第二名和第三名

    剩下的分析也是跟刚刚的思路一样。

    总结：25匹马，5个跑道，至少需要9场比赛才能保证找出前5名

    64匹马，8个跑道，至少需要11场才能保证找出前4名

编程题 (注意代码可读性、变量命名)

  1. 最大子数组(滑动窗口)

  2. 环状子数组的最大和(动态规划)

  3. Top K问题(归并)