25道常见算法面试题.docxVIP

-- ---- 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 亿条 url ，每条 url 各占用 64 字 节，内存限制是 4G ，让你找出 a、b 文件共同的 url 。 法 1 ：使用 hash 表。使用 a 中元素创建 hash 表， hash 控制在适当规模。在 hash 中查找 b 的元素，找不到的 url 先存在新文件中，下次查找。如果找到， 则将相应的 hash 表项删除，当 hash 表项少于某个阈值时，将 a 中新元素重新 hash 。再次循环。 法 2 ：对于 hash 表项增加一项记录属于的文件 a，b 。只要不存在的表项即放入 hash 表中，一致的项则删除。注意：可能存在很多重复项，引起插入，删除频 繁。 Problem 6 ：给你一个单词 a，如果通过交换单词中字母的顺序可以得到另外的 单词 b ，那么定义 b 是 a 的兄弟单词。现在给你一个字典，用户输入一个单词， 让你根据字典找出这个单词有多少个兄弟单词。 提示：将每个的单词按照字母排序， 则兄弟单词拥有一致的字母排序 （作为单词 签名）。使用单词签名来查找兄弟单词。 Problem 7 ：五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一 次找出那桶不正常的球。 Problem 8 ：给两个烧杯， 容积分别是 m 和 n 升（ m!=n ），还有用不完的水， 用这两个烧杯能量出什么容积的水？ m, n, m+n, m-n 以及线性叠加的组合 Problem 9 ：写出一个算法，对给定的 n 个数的序列，返回序列中的最大和最 小的数。 Problem 10 ：你能设计出一个算法，只需要执行 1.5n 次比较就能找到序列中 最大和最小的数吗？能否再少？ 提示：先通过两两比较，区分大小放入“大”，“小”两个数组中。从而最大数 在“大”数组中，最小数在“小”数组中。 Problem 11 ：给你一个由 n-1 个整数组成的未排序的序列，其元素都是  1 到  n 中的不同的整数。请写出一个寻找序列中缺失整数的线性 - 时间算法。 提示：累加求和 Problem 12 ：void strton(const char* src, const char*token) 长串字符， token 存有若干分隔符， 只要 src 的字符是 token 进行分割，最终将 src 按照 token 分割成若干单词。找出一种  假设 src 是一 中的任何一个， 就 O(n) 算法？ 提示：查表的方法，将所有的字符串存储在长度为 128 的数组中，并将作为分 隔符的字符位置 1，这样即可用常数时间判断字符是否为分隔符， 通过 n 次扫描， 将 src 分割成单词。 Problem 13 ：一个排好序的数组 A，长度为 n，现在将数组 A 从位置 m(mn ， m 未知 )分开，并将两部分互换位置，假设新数组记为 B，找到时间复杂度为 O(lgn) 的算法查找给定的数 x 是否存在数组 B 中？ 提示：同样采用二分查找。核心思想就是确定所查找数所在的范围。通过比较 3 个数（头，尾，中间）和所查找数之