当前位置:首页 >> 制度/规范 >>

25道常见算法面试题

最新资料,word 文档,可以自由编辑! ! 精 品 文 档 下 载 【本页是封面,下载后可以删除!】 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) 假设 src 是一 长串字符,token 存有若干分隔符,只要 src 的字符是 token 中的任何一个,就 进行分割,最终将 src 按照 token 分割成若干单词。找出一种 O(n)算法? 提示:查表的方法,将所有的字符串存储在长度为 128 的数组中,并将作为分 隔符的字符位置 1, 这样即可用常数时间判断字符是否为分隔符, 通过 n 次扫描, 将 src 分割成单词。 Problem 13: 一个排好序的数组 A, 长度为 n, 现在将数组 A 从位置 m(m<n, m 未知)分开, 并将两部分互换位置, 假设新数组记为 B, 找到时间复杂度为 O(lgn) 的算法查找给定的数 x 是否存在数组 B 中? 提示:同样采用二分查找。核心思想就是确定所查找数所在的范围。通过比较 3 个数(头,尾,中间)和所查找数之间的关系,可以确定下次查找的范围。 Problem 14: 一个排好序的数组 A, 长度为 n, 现在将数组 A 从位置 m(m<n, m 已知)分开,并将两部分互换位置,设计一个 O(n)的算法实现这样的倒置,只 允许使用一个额外空间。(循环移位的效率不高) 提示:(A’B’)’ =BA Problem 15:给出 Vector 的一个更好实现。(STL 的 vector 内存的倍增的, 但是每次倍增需要拷贝已存元素,平均每个元素需要拷贝一次,效率不高) 提示:可使用 2^n 的固定长度作为每次分配的最小单位,并有序的记录每个块 的首地址。这中结构同样可以实现线性查找,并且拷贝代价很低(仅有指针) Problem 16:给出已排序数组 A,B,长度分别为 n,m,请找出一个时间复 杂度为(lgn)的算法,找到排在第 k 位置的数。 提示:二分查找。 Problem 17:给出任意数组 A,B,长度分别为 n,m,请找出一个时间复杂 度为(lgn)的算法,找到排在第 k 位置的数。 提示:通过最小堆记录 k 个数,不断更新,扫描一

相关文章:
25道常见算法面试题.doc
25道常见算法面试题 - Problem 1 : Is it a loop ?
25道Java面试题集合.doc
25道Java面试题集合 - 25 道 Java 面试题集合 4.JAVA 中的
25个最难的面试问题(附答案).doc
25个最难的面试问题(附答案) - 最难的 25面试问题应对策略 1.介绍你自己 这个问题通常是一个面试的开始的第一个问题,要额外的小心不要滔滔不绝。尽可能...
25道shell面试题.doc
25道shell面试题 - 1、 用 sed 修改 test.txt 的 23
25个面试常见问题及回答.pdf
25面试常见问题及回答 - 25面试常见问题及回答 25面试常见问题及回答 事 先准备好的面试问题虽然不一定用得上,但多做一些功课总会让你有备少患,比 如...
25个 面试常见问题及分析.doc
关于面试关于面试隐藏>> 25面试常见问题及回答事先准备好的面试问题虽然不一定...但是无论合适可能的话,在你到面试过程的最后一个阶段之前,少谈论薪水的问 题...
世界500强频率最高25道面试题.doc
面试题(带分析) 世界 500 强频率最高 25 道面试题(带分析)吐血推荐
25道常见算法面试题.doc
25道常见算法面试题 - 最新资料,word 文档,可以自由编辑! ! 精品文档
面试时常见的25个问题.doc
常见面试问题常见面试问题隐藏>> 面试常见25 个问题各位
面试常见25个问题巧回答.doc
面试常见25个问题巧回答 - 1.先容你自己 1.先容你自己 这个题目通常是一个口试的开始的第一个题目,要额外的小心不要滔滔不绝。尽可能的 让你的回答在一分钟,...
面试应该准备的25个问题.doc
面试应该准备的25个问题 - 我曾经在 The Simple Dollar 上提到自己过去曾组织了大量面试工作。虽然我招聘的通常是 技术类职位,但实际问到的问题(因此是有实际价值...
面试25个经典问题回答技巧.doc
面试25经典问题回答技巧 - 面试 25经典问题回答技巧: 1、我们为什么要雇请你呢?有的面试只有这么一个问题。 2、你认为自己最大的弱点是什么?绝对不要自作...
25个让我无从下手的面试题.doc
“每个人都告诉我这个公司处于困境中,有各种样 的麻烦,这就是我来这儿的原因...世界500强频率最高25道面... 4页 1下载券 QTP 25个面试题 含答案 5页...
面试时25个问题.doc
面试时最难的25个问题 ... 3页 免费 面试常见25个问题 6页 1
教你应对!面试时最难回答25个问题.doc
面试时最难回答 25 个问题如果你是一个对目前的...那么就强调你希望创造你的事
面试时最难的25个常见问题.doc
面试时最难的25常见问题 - 1.介绍你自己 介绍你自己 这个问题通常是一个面试的开始的第一个问题?要额外的小心不要滔滔不绝。尽可能的 让你的回答在一分钟?...
25道shell面试题.doc
25道shell面试题 - 1、 用 sed 修改 test.txt 的 23
25个面试常见问题及回答.doc
25面试常见问题及回答事先准备好的面试问题虽然不一定用得上, 但多做一些功课
2019年面试的25个经典问题的面试技巧-精选word文档 (3页).doc
2019年面试25经典问题的面试技巧-精选word文档 (3页)_面试_求职/职场_实用文档。2019 年面试25经典问题的面试技巧-精选 word 文档 本文部分内容来自...
25道总经理秘书面试题 - 百度文库.doc
25道总经理秘书面试题 - 啦泪掉都心伤去死病为因小孵别用法办想就个虎秋送蛋下生