25道常见算法面试题

Problem 1 : Is it a loop ? （判断链表是否有环？） Assume that wehave a head pointer to a link-list. Also assumethat we know the list is single-linked. Can you come up an algorithm to checkwhether this link list includes a loop by using O(n) time and O(1) space wheren is the length of the list? Furthermore, can you do so with O(n) time and onlyone register? 方法：使用两个指针，从头开始，一个一次前进一个节点，一个前进 2 个节点，则最多 2N，后两个指针可以重合；如果无环，则正常停止。 同样的，可以找到链表的中间节点。同上。 Problem 2：设计一个复杂度为 n 的算法找到链表倒数第 m 个元素。最后一个元素假定是倒数第 0 个。 提示：双指针查找 Problem 3：用最简单的方法判断一个 LONG 整形的数 A 是 2^n（2 的 n 次方） 提示：x&(x-1) Problem 4：两个烧杯，一个放糖一个放盐，用勺子舀一勺糖到盐，搅拌均匀，然后舀一勺混合物会放糖的烧杯，问你两个烧杯哪个杂质多？ 提示：相同。假设杂质不等，那么将杂质放回原杯中，则杯中物体重量必变化，不合理。 Problem 5：给你 a、b 两个文件，各存放 50 亿条 u rl，每条 u rl 各占用 64 字节，内存限制是 4G，让你找出 a、b 文件共同的 u rl。 法 1：使用 hash 表。使用 a 中元素创建 hash 表，hash 控制在适当规模。在hash 中查找 b 的元素，找不到的 u rl 先存在新文件中，下次查找。如果找到，则将相应的 hash 表项删除，当 hash 表项少于某个阈值时，将 a 中新元素重新hash。再次循环。 法 2：对于 hash 表项增加一项记录属于的文件 a，b。只要不存在的表项即放入hash 表中，一致的项则删除。注意：可能存在很多重复项，引起插入，删除频繁。 Problem 6：给你一个单词 a，如果通过交换单词中字母的顺序可以得到另外的单词 b，那么定义 b 是 a 的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。 提示：将每个的单词按照字母排序，则兄弟单词拥有一致的字母排序（作为单词签名）。使用单词签名来查找兄弟单词。 Problem 7：五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球。 Problem 8：给两个烧杯，容积分别是 m 和 n...