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

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道常见算法面试题.doc
25道常见算法面试题 - 最新资料,word 文档,可以自由编辑! ! 精品文档
算法及逻辑类的面试题目大全.doc
算法及逻辑类的面试题目大全 - 算法及逻辑类的面试题目大全 1、A、B 两人分别
面试25个经典问题回答技巧.doc
面试25经典问题回答技巧 - 面试 25经典问题回答技巧: 1、我们为什么要雇请你呢?有的面试只有这么一个问题。 2、你认为自己最大的弱点是什么?绝对不要自作...
25道总经理秘书面试题 - 百度文库.doc
25道总经理秘书面试题 - 啦泪掉都心伤去死病为因小孵别用法办想就个虎秋送蛋下生
教师资格证面试结构化真题解析思路综合分析类(25道题).doc
教师资格证面试结构化真题解析思路综合分析类(25道题)_从业资格考试_资格考试/认证_教育专区。教师资格证面试结构化真题解析思路综合分析类(25 道题) 1 ...
面试的25个经典问题的面试技巧【可编辑版】.doc
面试25经典问题的面试技巧【可编辑版】_面试_...要闯过 面试 这道关,对于求职者来说,不仅 要有...把对求职者的真正需求 巧妙地隐藏在面试试题后面,...
经典面试题60道.txt
经典面试题60道_财会/金融考试_资格考试/认证_教育...请写一个高精度算法 29、有A、B、C、D四个人,...所有人都至少解答出一道题目,总共有25人。在没有...
25个让我无从下手的面试题.doc
“每个人都告诉我这个公司处于困境中,有各种样 的麻烦,这就是我来这儿的原因...世界500强频率最高25道面... 4页 1下载券 QTP 25个面试题 含答案 5页...
2019年面试的25个经典问题的面试技巧-精选word文档 (3页).doc
2019年面试25经典问题的面试技巧-精选word文档 (3页)_面试_求职/职场_实用文档。2019 年面试25经典问题的面试技巧-精选 word 文档 本文部分内容来自...
25个经典的Spring面试问答.doc
25经典的Spring面试问答 - 25经典的 Spring 面试问答 2
25道shell面试题.doc
25道shell面试题 - 1、 用 sed 修改 test.txt 的 23
25个最难的面试问题(附答案).doc
面试最难答的25个问题 5页 2财富值喜欢此文档的还喜欢 109个常见英文面试问题(附... 27页 免费 外企面试英文自我介绍 24页 免费 Oracle面试题-NEW 24页 免费...
面试时最难的25个问题.doc
面试时最难的25个问题_面试_求职/职场_实用文档。1.介绍你自己 这个问题通常...面试常见的100道问题及... 18页 1下载券 面试试题大全 17页 1下载券 ...
python面试常见的25个问题.doc
? Python 让困难的事情变得容易, 因此程序员可以专注于算法和数据结 构的设计,...面试时常见的100道问题及... 18页 1下载券 Python面试题 11页 1下载券 ...
QTP 25个面试题.doc
QTP 25面试题 - 1.QTP10.0 的特点和优点是什么? 2.如何使用
25个经典的Spring面试问答.pdf
25经典的Spring面试问答_面试_求职/职场_实用文档。25经典的 Spring 面试...对于本文中未提及的 Spring 其他模块,我会单独分享面试的问 题和答案。 欢迎...