interview question

从大量整数中选取最小 / 大的若干个

问题描述：现在有非常大量的一堆对象，比如有几十亿甚至上百亿个。对象本身是什么可以忽略，每个对象都有唯一标识符和一个正整数属性值，属性值范围有限（不大于一亿）。在单核机器上，内存和磁盘空间充足，用什么方法可以最快地输出属性值最小的若干（如一万）个对象，要求输出结果按照属性值排序。

发表于 2012年4月17日 interview question selection algorithm 算法

程序基本功之遍历二叉树

最近工作忙，没时间思考复杂的问题了。正好要招人就得有面试的嘛，自己也温习一下，要不然怎么去问别人。今天复习一下二叉树的遍历，前序（pre-order，NLR）、中序（in-order，LNR）、后序（post-order，LRN）、层序（level-order），用和不用递归。

发表于 2012年4月4日 interview question data structure binary tree 算法

条件概率：两个都是男孩的概率

这个问题其实不难，只是很多时候，尤其在没有任何提示的时候，容易想错。条件概率的题目一定要看清楚条件信息。问题描述：老王有两个孩子，已知至少有一个孩子是在星期二出生的男孩。问：两个孩子都是男孩的概率是多大？【假设生男生女的概率相等】

发表于 2011年12月30日 interview question probability 数学

计算斐波纳契数，分析算法复杂度

问题描述：Fibonacci 数（Fibonacci Number）的定义是：F(n) = F(n - 1) + F(n - 2)，并且 F(0) = 0，F(1) = 1。对于任意指定的整数 n（n >= 0），计算 F(n)，并分析算法的时间、空间复杂度。

发表于 2011年11月22日 interview question algorithm complexity fibonacci 算法

求内积最大的子数组

问题描述：有两个长度均为 n 的整数数组 A 和 B，现在要从这两个数组中各抽出 s 个数字，分别构成两个新的数组 C 和 D，要求数组 C 和 D 的内积最大。

发表于 2011年10月29日 interview question 算法

求二叉树中两结点的最小公共祖先

据说这是微软的一道面试题，谁知道呢。问题描述：找出二叉树上任意两个指定结点的最近共同父结点（LCA，Least Common Ancestor）。

发表于 2011年10月21日 interview question data structure binary tree 算法

任务调度问题：资源占用与释放

问题描述：有 n 个任务，第 i 个任务运行时需要使用 R[i] 的资源，运行完毕后需要占用 O[i] 的资源（O[i] <= R[i]），假设现在我们总共有 s 的资源，要求设计一个调度算法，能保证所有任务能顺利执行；如果无法执行完，需要说明理由。

发表于 2011年10月15日 interview question task schedule greedy algorithm 算法

检测单向链表是否存在环

问题描述：在单向链表中，每个结点都包含一个指向下一个结点的指针，最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点，就会形成一个环，在顺序遍历链表的时候，程序就会陷入死循环。我们的问题就是，如何检测一个链表中是否有环，如果检测到环，如何确定环的入口点（即求出环长，环前面的链长）。

发表于 2011年10月14日 interview question data structure linked list 算法

利用不均匀硬币产生等概率

问题描述：有一枚不均匀的硬币，已知抛出此硬币后，正面向上的概率为 p（0 < p < 1）。请利用这枚硬币产生出概率相等的两个事件。

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

random-selection

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

本文介绍一个有趣的算法，用来解决带权随机选取问题：有一组数量未知的数据，每个元素有非负权重。要求只遍历一次，随机选取其中的一个元素，任何一个元素被选到的概率与其权重成正比。

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