有100把锁，编号为1,2,3,…,100。一个人先把他们都打开。第二次，把能整除2的锁锁上。第三次，切换能整除3的锁的开闭状态，也就是说，把开着的锁关上，把锁着的锁打开。第四次，切换能整除4的锁的开闭状态。依次类推，操作进行100次。那么，现在问题来了，有多少把锁是开着的？

先分析下，一个锁到底被切换了多少次状态？
比如第15把锁，在第1,3,5,15次操作的时候被切换了状态，第一次打开，第三次关上，第五次又打开，第十五次关上。

什么样的锁是被打开的呢？
如果第X把锁，X有奇数个因数，他就被操作了奇数次，打开，关上，打开…关上，打开。最后的状态时打开的。

什么时候X有奇数个因数呢？
X是完全平方数。因为因数是成对出现的，比如36,1和36,9和4,等等。6和6是一对，但是他们是同一个因数。

1-100有多少个完全平方数呢？
十个。1的平方，2的平方，3的平方，。。。10的平方。

所以，最后有十把锁是开着的。

有一个100层的建筑。如果鸡蛋从第N层或更高掉下来就会碎，低于N层就不会碎。给你两个鸡蛋，找到这个N。要求是使得最坏情况下次数最少。

如何找到答案呢？让第一个鸡蛋去大致试一下楼层，第二个鸡蛋精确的去找到N。比如，第一个鸡蛋从10层扔下去，没碎，但是从15层扔下去碎了，那么N可能是11,12,13,14这四层，第二个鸡蛋必须从最小的开始去找，不然的话，碎了后面就没办法实验了。

我们先尝试一下，假设第一个鸡蛋按照10,20,30这样子扔。第二个鸡蛋从X1,X2,这样子扔，最坏情况下，N是99，那么总共需要19次就能得到结果。看起来，是个不错的结果。

最坏情况下次数最少，还能比19更少了吗？
我们创建这样一种机制：

1. 完美的负载平衡的系统，不管第一个鸡蛋在哪里碎了，总数是一样的
2. 第一个鸡蛋没多扔一次，那么第二个鸡蛋就要少扔一次。比如，第一个鸡蛋10层扔完之后，20层扔完都没有破，这一次尝试，第二个鸡蛋最多要扔9次，那么第一个鸡蛋再次尝试的时候，第二个鸡蛋最多就只能扔8次，也就是第一个鸡蛋去尝试29层。
3. 抽象一些，第一个鸡蛋第一次尝试X层，下一次增长量是X-1层，再然后是X-2层，直到100层。
4. 解出X的值。X + (X - 1) + (X - 2) + … + 1 =100。可以得到X = 14。

这样能保证最多14次，一定能找到N。

其他这样的最优化问题，一个关键思想就是使得最差情况平衡一些，也就是让最坏情况不要变得这么坏。

有一群人在岛上生活。某天，来了一个外地人，他带来一个奇怪的规则：岛上蓝眼睛的人必须尽快离开这个岛。每天有一班飞机离开这里。每一个人都可以看到别人眼睛是什么颜色的，但是不知道自己眼睛是什么颜色的，按照游戏规则，别人也不能告诉他。另外，他们不知道岛上有多少个蓝眼睛的人，只知道至少有一个。多少天之后，蓝眼睛的人会离开这个岛？

这是一个经典的推理题，让我们从最简单的开始着手。假设岛上有c个蓝眼睛的人，由题意可知，c > 0。

最简单的情况，c = 1：
假设所有人都是高智商的，很聪明。那个蓝眼睛的看见别人都不是蓝眼睛，而且知道至少有一个是蓝眼睛，很容易得到结论，自己就是蓝眼睛的，所以他第一天，也就是当天晚上就会离开小岛。

c = 2：
有两个人是蓝眼睛的。但是蓝眼睛的人自己无法判断到底是一个还是二个，因为他们能看见一个蓝色眼睛的人。假设只有一个，回到上一种模式，那么当天晚上蓝眼睛的人会离开这里。到了第二天，第一天没有蓝眼睛的人离开，那么蓝眼睛的人就可以确定，c = 2，自己就会离开小岛。所以，这种情况下，第二天所有的蓝眼睛人会离开小岛。

c = 3：
蓝眼睛的人可以看到两个蓝眼睛的人，但是无法判断是二个还是三个。假设是两个，回到了上一种模式，第二天蓝眼睛的人会离开小岛。到了第三天，蓝眼睛的人就会推断出，人数不是二而是三，所以蓝色眼睛的人会在第三天同时离开小岛。

以此类推，结论就是如果岛上有c个蓝色眼睛的人，在第c天晚上，所有的蓝眼睛人会同时离开小岛。

给你20瓶药，其中19瓶的药是1克重，剩余1瓶里面的药每片重1.1克。给你一个称，只能称一次，找出这瓶重量较大的。

由于只能称一次，那么肯定所有瓶里面的药都要参与进来。

如果每瓶都拿出来一片，显然没有什么意义的，总重量是20.1克。我们必须分别对待每一瓶药。

具体做法就是，第一瓶拿出1片，第二瓶拿出2片，以此类推。假设每片都是1克，那么总共有210片药，共计210克。但是有一瓶里面的药是1.1克重，不妨设是第x瓶比较重，那么比210克就会重出x * 0.1克的重量。(最后重量 - 210 ) / 0.1 = 重的瓶号。比如最后重量为211.3克，那么就是第13瓶药比较重。

其实，若都从0开始计算，第0瓶拿出0片，也能解出来。

给一个数组，其中包含n个整数，要求等概率的从中选取m个整数。

这道题挺简单的，在《编程珠玑》这本书中有讲解，想我两年前找工作的时候，认真的看了这本书的大多数内容，受益颇多。
这本书的作者提到他是从《计算机程序设计艺术》看到的一个解决方法。《计算机程序设计艺术》这本书也是好书，曾经看了第一卷的多数内容，实在太高端，后面想继续看，但是一直没有再去图书馆借，日后有机会，还是多读读。

废话不多说。解题的关键点是，从s个数中，选择r个，那么以概率r/s来选择。整个过程要遍历n个整数，每次都动态的以r/s的概率来要选择当前的这一个。下面是代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static int[] PickM(int[] a, int m)
{
    List<int> result = new List<int>();
    int n = a.Length;
    Random rand = new Random(DateTime.Now.Millisecond);

    for (int i = 0; i < n; i++)
    {
        if (rand.Next(0, n - i) < m)
        {
            result.Add(a[i]);
            m--;
        }
    }

    return result.ToArray();
}

看到这个题，第一直觉是使用位运算。为什么这么说呢？首先，不能使用 + 这个符号，你还能用什么呢；其次，计算机就是使用位运算来计算加法的。

我们需要真的搞明白加法的原理，然后用程序去实现它。

简单起见，我们考虑十进制。
想想我们小时候是如何计算759 + 674的，末位相加，大于10了，然后进一。然后加十位上的数字，还要加上个位的进位。以此类推。计算二进制也是类似的，对每一位相加，如果可能，还要进位。

好了，让我们分离加法操作，分成加和进位两部分。

1. 759 + 674，如果只加不进位，得到323；
2. 只考虑进位，得到1110；
3. 把两部分相加在一起，得到1433。

现在来看看如何进行二进制操作：

1. 只加不进位，相当于位运算里面的异或XOR；
2. 只考虑进位，相当于和操作AND且左移一位；
3. 重复这个过程，直到没有进位为止。
   因为十进制分析那里，第三步相当于用了加。程序上，不能使用加，只好想办法再继续递归下去。没有进位，就是第二个加数为零，那么第一个加数就是要求的和。

下面是代码：

1
2
3
4
5
6
7
8
9
10
11
12

public static int Add(int a, int b)
{
    if (b == 0)
    {
        return a;
    }

    int sum = a ^ b;
    int carry = (a & b) << 1;

    return Add(sum, carry);
}

给你54张牌，写一个洗牌算法，要求等概率的出现54!种不同的排列。

这个一个众所周知的面试题，也是一个众所周知的算法。

算法的思想很简单，就是遍历每一张，让后面（包括当前这张）的牌等概率的出现在这个位置上。比如index从0开始，那么每张牌都等概率的出现在0这个位置上，index等于1时，0位置上的那一张，其余的牌等概率出现在位置1上，以此类推。这样，排列总数就是54!，且每一种是等概率出现的。
下面是代码：

1
2
3
4
5
6
7
8
9
10
11

public static void Shuffle(int[] cards)
{
    Random rand = new Random(DateTime.Now.Ticks);
    for (int i = 0; i < cards.Length; i++)
    {
        int k = rand.Next(i, cards.Length);
        int temp = cards[k];
        cards[k] = cards[i];
        cards[i] = temp;
    }
}

我曾经看过有人在生成随机数的时候，生成(0, length)范围内的随机数，这是不对的。这样子，每个位置上的数字还会从前面已经排好的数字里面取，这样排列总数是54^54，是伪洗牌算法，是错误的。

问题：你正在读一个整数数据流。在读的过程中，你可能需要要知道某个值x在已读数据的排位，实现这个功能。也就是说，你需要实现一个方法track(int x)，每读入一个整数，就会调用一次该方法。实现方法getRankOfNumber(int x)，返回小于等于x的值的数量。

简单的方式，维护一个有序的数组。getRankOfNumber方法很高效，二分查找就好了。但是track方法很慢，插入到合适的地方，可能要移动很多元素。

换种数据结构，二分查找树。track复杂度是log(n)，平均情况，而且我们可以假设数据流是随机的，树大致平衡。getRankOfNumber方法的效率就不高了，需要中序遍历，得到x的排序。
想一想，如果x比某个节点的值还小的话，其实就不用去遍历左边的子树了，因为左边的都比x小。所以，我们往节点里面添加一个值，记录该节点左边有多少个节点。这样就不用遍历左边的子树，直接加上这个值就可以了。

下面是完整的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

private static RankNode root = null;

public static void Track(int number)
{
    if (root == null)
    {
        root = new RankNode(number);
    }
    else
    {
        root.Insert(number);
    }
}

public static int GetRankOfNumber(int number)
{
    return root.GetRank(number);
}

class RankNode
{
    public int LeftSize { get; set; }
    public RankNode Left { get; set; }
    public RankNode Right { get; set; }
    public int Data { get; set; }

    public RankNode(int d)
    {
        this.Data = d;
    }


    public int GetRank(int d)
    {
        if (d == this.Data)
        {
            return this.LeftSize;
        }
        else if (d < this.Data)
        {
            if (this.Left == null)
            {
                return -1;
            }
            else
            {
                return this.Left.GetRank(d);
            }
        }
        else
        {
            int rightRank = this.Right == null ? -1 : this.Right.GetRank(d);
            if (rightRank == -1)
            {
                return -1;
            }
            else
            {
                return this.LeftSize + 1 + rightRank;
            }
        }
    }

    public void Insert(int d)
    {
        if (d <= this.Data)
        {
            if (this.Left == null)
            {
                this.Left = new RankNode(d);
            }
            else
            {
                this.Left.Insert(d);
            }

            this.LeftSize++;
        }
        else
        {
            if (this.Right == null)
            {
                this.Right = new RankNode(d);
            }
            else
            {
                this.Right.Insert(d);
            }
        }
    }
}

原题链接
问题描述：
数字145有一个著名的性质：其所有位上数字的阶乘和等于它本身。
1! + 4! + 5! = 1 + 24 + 120 = 145
169不像145那么有名，但是169可以产生最长的能够连接回它自己的数字链。事实证明一共有三条这样的链：
169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872
不难证明每一个数字最终都将陷入一个循环。例如：
69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)
从69开始可以产生一条有5个不重复元素的链，但是以一百万以下的数开始，能够产生的最长的不重复链包含60个项。
一共有多少条以一百万以下的数开始的链包含60个不重复项？

我想，这个题几乎没有什么难度吧。我的做法是把每个数字和它对应的下一个值放到一个字典里面。然后从3开始遍历到100万，统计链的长度。
下面是相关的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

int count = 0;

Dictionary<int, int> nexts = new Dictionary<int, int>();
for (int i = 1; i < 1000000; i++)
{
    int key = i;
    int value = GetNext(i);
    nexts.Add(key, value);

    while (value > 1000000)
    {
        key = value;
        value = GetNext(key);
        nexts[key] = value;
    }
}

for (int i = 3; i < 1000000; i++)
{
    HashSet<int> numbers = new HashSet<int>();
    int cur = i;
    while (!numbers.Contains(cur))
    {
        numbers.Add(cur);
        cur = nexts[cur];
    }

    if (numbers.Count == 60)
    {
        count++;
    }
}

return count;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

private static int GetNext(int i)
{
    int value = i.ToString().Select(c =>
    {
        int m = int.Parse(c.ToString());
        int product = 1;
        for (int j = 2; j <= m; j++)
        {
            product *= j;
        }
        return product;
    }).Sum();

    return value;
}

在一台很弱的虚拟机里面，大概6秒就能得到结果。

其实，我试了一下暴力的算法，大概1分钟就能得到结果。

假定给你100亿条URL，如何去除重复文档呢？这里重复的意思是指URL一样。

首先，我们估算下100亿条数据的体积。假设每个URL有100个字符，每个字符使用2个字节，那么存储这100亿条数据，需要2T的空间。我们或许没办法把所有的数据都放到内存里面。

我们先做一个简单的题目，假设URL条数很少，内存能放下，该如何去重呢。我们可以建立一个哈希表，把URL做哈希运算放到这个哈希表中。如果key，哈希之后的值，已经在哈希表中了，那么这条URL已经存在了。如果考虑到哈希碰撞的话，比较下两个字符串就好，也不是什么大事。另外可选的方案是排序去重，这花费的时间更多，而且没有太多额外的好处。

回到题目，2T的数据，怎么办呢？
方案1：
假设所有数据都在一台机器上。首先，我们可以把这2T的数据划分成2000块，这样每块就是1G的大小了。一个容易的划分方式是Hash(URL) % 2000，这样，URL一样的话肯定会被放入同一个文件中。从概率上说，不会每块都是1G大小，如果是随机数据的话，假定满足正态分布或者泊松分布，超过2G的概率就很小了。再说，现代机器能够使用的内存很大，这都不是事。这样，我们每块都能放入内存中了，采用之前说的方案进行去重。

方案2：
假设把数据在多台机器上。处理的方式基本上是一致的。放到某个文件变成了发送URL到某台机器上。

多台机器的优势：速度快，2000台机器可以并行计算。
多台机器的劣势：我们要依赖于不同的机器的稳定性，如果数据更大，机器也会更多，处理错误也更复杂。也就是说，增加了整个系统的复杂性。