面试会出哪些经典算法题?

知识库 kira ⋅ 于 3个月前 ⋅ 1271 阅读

来源:知乎@力扣(LeetCode)


首先,让我们回顾几个有意思的经典互联网公司的面试题目,热热身。

1、给你一个长度为 n 的数组,其中只有一个数字出现了奇数次,其他均出现偶数次,问如何使用优秀的时空复杂度快速找到这个数字。

136. 只出现一次的数字

2、给你一个长度为 n 的数组,其中只有一个数字出现了大于等于 n/2 次,问如何使用优秀的 时空复杂度快速找到这个数字。

169. 求众数

3、给你一个 n*m 的二维数组,每行元素保证递增,每列元素保证递增,试问如何使用优秀的时间复杂度找到某个数字(或者判断不存在)。

240. 搜索二维矩阵 II

4、给你两颗二叉搜索树,如何使用线性的时间复杂度,将它们合并成一颗二叉搜索树。

88. 合并两个有序数组

5、假设有 100 层的高楼,给你两个完全一样的鸡蛋。请你设计一种方法,能够试出来从第几层楼开始往下扔鸡蛋,鸡蛋会碎。 当然,这个问题还有推广版本,有兴趣的同学可以思考一下。 假设有 n 层楼,给你 k 个完全一样的鸡蛋,请问最坏情况下,至少需要试验多少次才能知道从第几层楼开始往下扔鸡蛋,鸡蛋会碎。

887. 鸡蛋掉落


接下来,再认真回答一下这个问题。先划重点:面试算法题。作为在电话 / 现场面试中短短不到一个小时时间内,提供给面试者白板编程解决的算法题目,它与笔试上机、编程竞赛中的题目在难度与形式上还是有一些不同的。

这里有一张互联网公司面试中经常考察的问题类型总结的思维导图,我们可以结合图片中的信息分析一下。file

可以明确的一点是,面试算法题目在难度上(尤其是代码难度上)会略低一些,倾向于考察一些基础数据结构与算法,对于高级算法和奇技淫巧一般不作考察。

代码题主要考察编程语言的应用是否熟练,基础是否扎实,一般来会让面试者写出代码完成一些简单的需求或者使用递归实现某些功能,而数学题倾向于考察概率相关的问题。以上这两类问题,出现的频率不会很高,即使出现了也应该是面试中的简单部分,相信一定难不倒在座的给位同学们。

算法与数据结构是面试考察的重中之重,也是同学们日后刷题时需要着重训练的部分。简单的总结一下,大约有这些内容:

算法 - Algorithms

  1. 排序算法:快速排序、归并排序、计数排序
  2. 搜索算法:回溯、递归、剪枝技巧
  3. 图论:最短路、最小生成树、网络流建模
  4. 动态规划:背包问题、最长子序列、计数问题
  5. 基础技巧:分治、倍增、二分、贪心

数据结构 - Data Structures

  1. 数组与链表:单 / 双向链表、跳舞链
  2. 栈与队列
  3. 树与图:最近公共祖先、并查集
  4. 哈希表
  5. 堆:大 / 小根堆、可并堆
  6. 字符串:字典树、后缀树

Last But Not Least! 干货预警!

力扣将 Top Interview Questions 里比较新的题目按照类别进行了整理,以供大家按模块练习。

模拟

数组

链表

哈希 / Map

队列

线段树

排序

二分检索

滑动窗口

动态规划

图论

数学 & 位运算

字符串

本帖已被设为精华帖!
本帖由 你找不到我 于 3周前 加精
回复数量: 0
暂无回复~
您需要登陆以后才能留下评论!