interview question

单次遍历，带权随机选取问题（一）

问题描述：有一组数量未知的数据，每个元素有非负权重。要求只遍历一次，随机选取其中的一个元素，任何一个元素被选到的概率与其权重成正比。

发表于 2011年9月21日 interview question probability random sample 算法

问题描述：假设我们有一堆数据（可能在一个链表里，也可能在文件里），数量未知。要求只遍历一次这些数据，随机选取其中的一个元素，任何一个元素被选到的概率相等。O(n) 时间，O(1) 辅助空间（n 是数据总数，但事先不知道）。

发表于 2011年9月6日 interview question probability random sample 算法

问题描述：假设有一个数组，包含 n 个元素。现在要重新排列这些数据，要求每个元素被放到任何一个位置的概率都相等（即 1/n），并且直接在数组上重排（in place），不要生成新的数组。用 O(n) 时间、O(1) 辅助空间。

发表于 2011年9月1日 interview question probability 算法

问题描述：给定一个由 n 个各不相等的元素构成的循环有序数组（Circularly Ordinal Array），用 O(log n) 时间、O(1) 辅助空间在其中查找指定的元素。

发表于 2011年8月19日 interview question lookup algorithm 算法

单例模式是设计模式中的一种，它用来保证系统中最多只能存在一个它的实例，其做法是由类自身来创建和持有它的对象实例，把对实例的创建权和管理权都控制在自己手中，以便控制实例数目。本文介绍可以继承的单例类。

发表于 2011年8月12日 interview question c++ design pattern 程序开发

仔细回忆一下 C++ 中的指针常量与常量指针的区别，记录于此。

发表于 2011年8月4日 interview question c++ 程序开发

问题描述：现在有一个叫做 Rand5 的函数，可以生成等概率的 [0, 5) 范围内的随机整数，要求利用此函数写一个 Rand3 函数（除此之外，不能再使用任何能产生随机数的函数或数据源），生成等概率的 [0, 3) 范围内的随机整数。

发表于 2011年8月2日 probability interview question 算法

某人 6 点多从家出发，出门时时针和分针是 110 度角，7 点前回到家，时针和分针还是 110 度角。问这人出门多久？本文以这个简单的问题入手，介绍了利用相对运动解决时针、分针相关问题的方法。

发表于 2011年7月18日 puzzle interview question 数学