面试题整理 | Eurce's Blog
1. 一个大小为n的数组，元素有正有负，求将所有负数放在正数前面的稳定的算法。
解：考虑归并排序的思路，每次将两个子段合并整理成一长段的过程，即为[负][正][负][正]，转换成[负][正]的形式。时间复杂度是O(NlgN)的。
2. 有n个囚犯排成一列，每个人头上有帽子，帽子是黑色或者白色。每个人只能看到自己前面的人的帽子，看不到自己和自己后面人的帽子。从后往前，每个人需要报出自己帽子的颜色，如果错了就被处决，否则就被释放。前面的人能听到后面的人报的是黑还是白。求一个确定的策略，使得尽可能多的囚犯被释放。
解：最优解只牺牲最后面的一个人。把黑帽子视作0，把白帽子视作1，每个人求他前面所有人帽子颜色值的异或值。最后面的人报出异或值后，从倒数第二个人开始，每个人都能根据他后面人的帽子颜色来计算出自己头上帽子是什么颜色。
3. 有100个囚徒，每人在不同的房间。另有一个大厅，大厅里有一盏灯，初始是关的。每天会有一个囚徒被从房间叫出到大厅，并能开、关灯。也即每个囚徒能知道的信息包括：1. 当前是第几天；2. 如果被叫到大厅了，灯是开着的还是关着的。每个囚犯到大厅时，都可以选择告诉警官“所有人都至少来过大厅一次了”，如果确实如此，那么所有囚徒都会被释放，不过只有一次机会尝试。问一个确定的方案，使得这些囚徒能够重获自由。并且需要分析该方案完成的期望天数。
解：考虑选第一天出到大厅的囚徒为master，只有master有权力关灯，其他囚徒会且仅会开一次灯，那么当master关了99次灯之后，就知道所有人都至少出来过一次了。期望天数是1 + 100/99 + 100/1 + 100/98 + 100/1 + … + 100/1 + 100/1。
4. 有一个线段，线段上有两点A、B，有两个机器人分别在这两个点上。初始A、B点位置不确定，线段无限长。你需要为这两个机器人写一段相同的程序，使得他们可以相遇。指令集是给定的，包括4种指令：
1. move left 向左移动（耗时1）
2. move right 向右移动（耗时1）
3. if at A点或B点
4. goto 某行
1. move left 向左移动（耗时1）
2. move right 向右移动（耗时1）
3. if at A点或B点
4. goto 某行
解：考虑使两个机器人同时向右走，一开始都是慢走，其中一个机器人一定会遇到另一个机器人出发的起点（A或B），那么将其转换成快走模式，追赶慢走的机器人。
1: move right
2: move left
3: move right
4: if at A点或B点
5: goto 7:
6: goto 1:
7: move right
8: goto 7:
1: move right
2: move left
3: move right
4: if at A点或B点
5: goto 7:
6: goto 1:
7: move right
8: goto 7:
5. 求一个完全二叉树的结点总数。
解：完全二叉树有这样的性质：对于树上任意的一个结点，其左子树或右子树中至少有一个是满二叉树。可以通过探测最左和最右结点的深度来判断这棵树是不是满二叉树，时间复杂度是O(lgN)的。因此，依次从最高层向下，每层判断是否满二叉树后最多只沿其中一个子树继续向下，这里时间复杂度是O(lgN)+O(lg(N/2))+…+O(lg(N/N)) = O((lgN)^2)的。
6. 有100层楼，以及这样一种鸡蛋：该鸡蛋从某层以上的楼层往下丢会摔碎，而从该层以下往下丢则是怎么摔都不会碎。给你两个鸡蛋，要求通过最少的尝试次数试出这个鸡蛋从哪层开始会碎。扩展：有N层楼和M个鸡蛋的情况。
解：第一个鸡蛋用来大致试探，第二个鸡蛋需要逐层试探。第一个鸡蛋试探的楼层间隔即是第二个鸡蛋最多要尝试的上限。那么第一个鸡蛋划分出的间隔应该是逐渐递减的，这样才能使总尝试次数最小。例如，第一个鸡蛋分别从x、x+(x-1)、x+(x-1)+(x-2)、…开始往下丢，第二鸡蛋分别需要尝试x-1、x-2、x-3…次，那么最坏情况下总是需要x次尝试就能试出楼层数了。这里需要使得x(x+1)/2 >= 100-1，解得x>=14。这里是100-1是因为，如果刚好x(x+1)/2==99还没碎，那么肯定是第100层楼才会碎的，也就不用额外去试了。
扩展的情况下，考虑3个鸡蛋，若设最多尝试次数为x，那么第一个鸡蛋划分出的区间之间的间隔应该是使得两个鸡蛋的总尝试次数递减的，也即需要满足sum{x(x-1)/2} >= M-2。4个鸡蛋的情况就是sum{sum{x(x-1)/2}} >= M-3，依此类推。
扩展的情况下，考虑3个鸡蛋，若设最多尝试次数为x，那么第一个鸡蛋划分出的区间之间的间隔应该是使得两个鸡蛋的总尝试次数递减的，也即需要满足sum{x(x-1)/2} >= M-2。4个鸡蛋的情况就是sum{sum{x(x-1)/2}} >= M-3，依此类推。
有节点数为n的一棵树，每个节点i有一个权值w[i]，节点i到节点j的距离d[i][j]定义为在树上节点i和节点j之间有多少条边。定义f(i) = sum{w[j] * d[i][j] | -1 < j < n}，求min{f(i) | -1 < i < n}。 题源来自qoshi。
基本思路还是树型DP，希望能根据相邻节点的f值计算出当前节点的f值。具体的思路是，如果指定了深搜的起点为0，那么每个节点都会将树上的其他节点分为两个部分，一部分是离0点近的（设为A类节点），一部分是离0点远的（设为B类节点）。
具体的状态转移，包括4个矩阵：lw[i]，记录的是某个节点划分出的属于A类节点的权值和；rw[i]记录属于B类节点的权值和；lws[i]记录的是sum{ w[j] * d[i][j] | j属于i划分出的A类节点}；rws[i]记录的是sum{ w[j] * d[i][j] | j属于i划分出的B类节点}。由此f(i) = lws[i] + rws[i]。使用这4个矩阵是因为，沿着某条边走一步后，某个节点的这4个值可以根据相邻节点的信息O(1)地得到。
其中rws[i]，需要从自底向上的构造，也就是用了深搜遍历完所有孩子节点后，再计算父节点的值；而lws[i]，则是自顶向下的计算。
int n, w[M], lw[M], lws[M], rw[M], rws[M], hd[M], el;
int ansi, ans;
struct E {
int v, p;
}e[M*2];
void adde(int u, int v) {
e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
e[el].v=u; e[el].p=hd[v]; hd[v]=el++;
}
void init() {
int i, j, k, l;
el=0;
memset(hd, -1, sizeof hd);
for(i=0; i<n; i++) scanf("%d", w+i);
for(i=1; i<n ;i++) {
scanf("%d%d", &j, &k);
adde(j, k);
}
ans=0x7fffffff;
}
void dfsr(int i, int f) {
int j, k, l;
rw[i]=rws[i]=0;
for(l=hd[i]; l!=-1; l=e[l].p) {
j=e[l].v;
if(j==f) continue;
dfsr(j, i);
rw[i]+=rw[j]+w[j];
rws[i]+=rws[j]+rw[j]+w[j];
}
}
void dfsl(int i, int f) {
int j, k, l;
if(f==-1) {
lw[i]=lws[i]=0;
} else {
lw[i]=rw[f]+lw[f]-rw[i]-w[i]+w[f];
lws[i]=rws[f]+lws[f]-rws[i]-rw[i]-w[i]+lw[i];
}
for(l=hd[i]; l!=-1; l=e[l].p) {
j=e[l].v;
if(j==f) continue;
dfsl(j, i);
}
}
void solve() {
int i;
dfsr(0, -1);
dfsl(0, -1);
for(i=0; i<n; i++) {
printf("%d: %d + %d = %d\n", i, lws[i], rws[i], lws[i]+rws[i]);
if(lws[i]+rws[i]<ans) {
ans=lws[i]+rws[i];
ansi=i;
}
}
printf("%d %d\n", ansi, ans);
}
int main () {
while(~scanf("%d", &n)) {
init();
solve();
}
return 0;
}
Read full article from 面试题整理 | Eurce's Blog