算术

C++语言的特性：常数函数表达式

deanjiang — Wed, 22 Aug 2007 00:54:34 +0800

C++在很多地方允许使用常数表达式，比如在常数变量进行初始化时，定义数组时，或者在对模板进行特化时。语言规范要求常数表达式中不能使调用函数，哪怕是非常简单的函数也不行。但表达式相对复杂一点的时候，这个限制使得程序的书写很不方便。比如：

const int n = -17;
int array[ n>0 ? n : -n ];

其实目的是为了求n的绝对值，然后声明大小适当的数组。为了方便我们可以定义一个宏：

ABS(X) ((X)>0 ? n: -n)
const int n = -17;
int array[ ABS(X)];

我们都知道宏的缺点是没有类型检查，如果表达式比较复杂难以调试。一个新的C++建议允许将特定的一类函数在常数表达式中使用，形式如下

return_type functionname(parameters){
return constant_express;
}

可以看出来，这个建议实际上就是将只有一个返回语句的简单函数自动扩展为对应的表达式。这一过程和内联很相似。详细内容参见Generalized Constant Expressions (N1521)

收藏到：Del.icio.us

博客大巴，你的个人传媒早班车

大文件随机抽样

deanjiang — Thu, 16 Aug 2007 15:51:09 +0800

一个很古老的问题。有一个非常大的文本文件，比如说300G，你无法读入内存再进行处理。文件中每一行包含一个单词或短语，但是长度不定。请设计一个算法，可以完全随机的从中选择一个单词或短语。选择每一个单词或短语的概率必须严格相同。

收藏到：Del.icio.us

博客大巴，你的个人传媒早班车

复合栈

deanjiang — Wed, 15 Aug 2007 13:14:41 +0800

地球人都知道栈最有效率的实现方式就是数组了。如果要求两个栈共享一个数组，为了充分利用空间，我们通常会一个栈放在底部向上生长，另一个放在顶部项下生长。现在，请设计一个算法，最有效率的在一个数组中实现三个栈。这里主要是指空间利用率。

收藏到：Del.icio.us

博客大巴，你的个人传媒早班车

Yahoo!的面试

deanjiang — Sun, 12 Aug 2007 22:28:34 +0800

前一阵子也参加了一个Yahoo的面试，因为方向特殊，没有经过HR的面试，直接就跑了过去，问的全是概率相关的问题。这里我想说的是最后一个开放式的问题。其实这已经不是面试题了，而是他们当时正在考虑的项目，说出来挺有意思的。谁叫没让我签保密合同呢。

Yahoo!自己有一个照片分享网站，就是flickr。flickr有两个功能，一个是可以给每个照片加标签，以便於搜索，另一个就是每个照片可以关联到地图上的一个位置上。想象一下大家都给照片加什么样的标签呢？最多的恐怕就是照片里的人物和拍摄的地点了。于是雅虎开始考虑能不能用用户输入的标签和图片的地理位置信息给Yahoo!地图作标注。好比在yahoo地图上用户正在显示某个区域，我们可以用算法来计算出一个最恰当的名字。比如，你正在看北京海淀区附近的地图，那么它应该显示这里是海淀，而不要说北京或是中国，也不能是海淀里面的某个镇某个村。怎么做这个算法呢？

我的解答详见内文

收藏到：Del.icio.us

博客大巴，你的个人传媒早班车

分布式词频统计

deanjiang — Sat, 11 Aug 2007 00:49:56 +0800

有一个规模庞大的多语言语料库，已经经过预处理，分成了12个文件，每个文件存放在一台服务器中。每个文件中包含800亿个单词，每个单词占一行，平均每个单词40字节。假设服务器都已经联网，每台服务器有双CPU和4G的内存，4×400GB的硬盘，换句话说，每台服务器就是一个高配置的PC机。请设计一个方案，找出出现频率最高的一百万个单词。

收藏到：Del.icio.us

博客大巴，你的个人传媒早班车

Xbox的最佳摔法

deanjiang — Fri, 10 Aug 2007 23:10:53 +0800

在网上多次看见相似的题目，有人给出了正确的答案，但没能够合理的说明为什么结果是最优的。所以我也出来伸展一下。题目如下：

你在一幢100层的办公楼里上班，现在给你两台Xbox，要求你用尽可能少的实验，确定把Xbox扔下而摔不坏的最高楼层。比方说，从30层丢下来没问题，但从31层丢下来就坏了，那么30层就是最高楼层。假设只要没超过这个最高楼层，Xbox摔几次都不会坏。允许把两台xbox都砸烂的情况下，最少要做多少次实验(把Xbox从楼上摔下多少次)才能保证找到这个最高楼层？请给出实验的方案。

收藏到：Del.icio.us

博客大巴，你的个人传媒早班车

选择算法

deanjiang — Fri, 10 Aug 2007 20:08:57 +0800

设计一个选择算法从一组N个数字中找出最大或最小的M个数字。M通常远远小于N。

类似的问题往往是和缓存的使用有关。比如搜索引擎对常用搜索结果需要进行缓存，以避免反复的重复查询。比较简单的策略可以是对最后的M个不同的搜索进行缓存。这样的性能并非最优的，因为最后的M个搜索并不一定是最频繁的搜索。比较好的方案是对所有搜索计算出现的频率，然后选出最频率最高的M个进行缓存。当然这一过程并不需要是实时的，比如每天做一次就差不多了。两种方案如果能结合以下，量增缓存的效果可能会更好。

收藏到：Del.icio.us

博客大巴，你的个人传媒早班车

正态分布数据的排序

deanjiang — Fri, 10 Aug 2007 19:49:50 +0800

已知数组中的数据大致符合正态分布，哪种排序算法的效率最高？

收藏到：Del.icio.us

博客大巴，你的个人传媒早班车

多级索引

deanjiang — Wed, 08 Aug 2007 21:35:18 +0800

有一套40G的数据，其中的每条数据都是一个键值对，所有的键都是唯一的。给你一台计算机，只有1G的内存，请设计一个方案如何才能有效的通过键来访问对应的值。请最小化内存的页面失效请求。

收藏到：Del.icio.us

博客大巴，你的个人传媒早班车

中间值

deanjiang — Wed, 08 Aug 2007 19:46:34 +0800

给你O(N)台联网的计算机，每台计算机上保存了O(N)个整数。假设由于内存的限制每台计算机最多能购处理O(N)个整数，请设计一个算法找出这O(N×N)个整数的中间值(Median)。

提示：可以假设有一台或几台计算机上没有保存数据（协调人），用来协调其他计算机的工作。

如果你不记得什么是中间值的话，这里有一个例子

1, 2, 3, 4, 5, 16, 17, 18, 19, 20 这里5和16都是中间值

1, 2, 3, 4, 5, 17, 18, 19, 20 这里5是中间值

收藏到：Del.icio.us

博客大巴，你的个人传媒早班车