专栏首页小小挖掘机盘点互联网公司最常见的面试编程题

盘点互联网公司最常见的面试编程题

1 突破编程题

互联网公司面试,笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说,败在了编程题上,去不了自己心仪的公司,拿不到想要的待遇。

确实,很遗憾。目前不光在国内,在北美等知名互联网公司,没有一家不做编程题的,可能比我们还要残酷,他们一般是做三道,可能挂掉一道就没有机会进入下一面。

所以,无论我们下一站通往哪里,具有良好的编程基本功,理解并掌握常用的计算机算法思想,都是必要的。好消息是,在短短的1个小时现场编程环节,公司所考的这些题目,往往有迹可循,难度适中,不会涉及技巧淫技(trick)。

这样的话,我们完全可以经过充分的准备,很稳地通过这一关,为下一环节争取更好的面试印象。

Leetcode是比较专业的训练编程题的平台,目前也有中文leetcode网站,https://leetcode-cn.com 称它为"力扣",在这里已经总结了如何高效使用Leetcode编程题,下面结合自身做题经历,再总结下。

2 开胃小菜

力扣介绍互联网公司最常考的面试算法题时,首先亮出了5道开胃小菜,我们首先分析下为什么是这5道。

这5道题的一个基本归类:

只出现一次的数字在题库编号为 136, 难度为简单级别,考察位运算;

求众数,编号169, 难度为简单,考察位运算,分治思想;

搜索二维矩阵II,编号240,难度中等,考察二分查找,分治思想;

合并两个有序数组,编号88,难度简单,考察双指针;

鸡蛋掉落,编号887,难度为难,考察队列,决策树;

也就说这5道题目,包括简单,中等,难度都有,考察的大都也是常用的,不是偏题、怪题,平时多加训练,除了有难度的鸡蛋掉落外,可能其他都能从容应对。

但是如果平时没有有意训练,可能第一道在O(n)时间,O(1)空间下都不太容易想得出来。因此,根据题目标签,有方法体系地慢慢训练吧,不光对面试有帮助,还能培养我们的算法思维,考虑问题更加缜密,写出来的代码更高效。

3 练习方法

力扣官网进一步介绍了训练和准备面试算法题的方法,首先理清楚问题的类型,其次,掌握常用的算法和数据结构。

对于问题类型,力扣给出了下面这幅图,这幅图还是比较笼统,下面我补充一些愚见。本篇我们讨论问题的范围是面试算法题,那么问题的类型,大家的预期应该是常考算法题的一些标签、归类等。

常用的数据结构:

1) 数组,应用广泛,可以灵活结合各种算法思想使用;

2) 堆,最常用的大小堆,堆排序等;

3) 队列,先进先出的数组,二叉树的遍历可以使用队列实现

4) 栈,先进后出的数组,二叉树的遍历用栈也可实现

5) 树,比较常考,常见的比如二叉树遍历,求高度、深度,是否对称等等

6) 图,图的深度和广度优先遍历等,Dij, Flody最短路、prim 最小生成树、网络流等;

除了上图中所总结的还包括一个重要的、常考的数据结构:链表,比如链表的增删,反转,子环,拼接等,不妨多练习,很容易出错。

常用的一些算法思想或类别:

1) 动态规划,常考,重要的是找到初始条件,状态迭代方程,比如机器人不同的行走路线个数等;还有背包问题、最长子序列等等,题目相当灵活;

2) 字符串:判断是否为回文字符串,子串,共有子串等;

3) 数字考察,比如求sqrt(2),判断数字是否为幸福数等;

4) 二分查找:sqrt(2)求法,使用它的前提一般是要求数组有序;

5) 深度优先搜索:一般可结合回溯求解很多有意思的问题,比如1234的全排列等,搜索过程往往还还会涉及剪枝技巧等;

6) 回溯:类似枚举,但超越枚举的带有智能退回到回溯点的搜索方法,常见的八皇后问题;

7) 双指针,组合使用两个指针解决问题,定好初始状态,比如止于会和处,常见的快速排序其实就有这类味道;

8) 广度优先搜索,不同于深度优先的另一种搜索机制;

9) 分治:归并排序就是分治的最典型例子

10) 位运算:文章开头说的只出现一次的数,就是一个最典型的例子,还有两个数的和分解为位运算问题。

11) 递归:递归让代码变得更精炼,二叉树的遍历就是最有代表性的例子,递归代码只有5行以内;

12) 贪心:贪心有时可以得到最优解,有时只能得到可行解。

4 必备题目

下面参考力扣列出的一些经典题目,按照标签分类统计。

数组

152. 乘积最大子序列

169. 求众数

189. 旋转数组

217. 存在重复元素

283. 移动零

384. 打乱数组

350. 两个数组的交集II

334. 递增的三元字序列

240. 搜索二维矩阵II

238. 除自身以外数组的乘积

链表

138.复制带随机指针的链表

141. 环形链表

148. 排序链表

160. 相交链表

206. 反转链表

234. 回文链表

237. 删除链表中的节点

328. 奇偶链表

155. 最小堆

215. 数组中的第K个最大元素

295. 数据流的中位数

378. 有序矩阵中的第K小的元素

347. 前K个高频元素

150. 逆波兰表达式求值

227. 基本计算器II

341. 扁平化嵌套李彪迭代器

哈希

171. Excel表序列号

454. 四数相加II

380. 常数时间插入、删除和获取随机元素

队列

滑动窗口最大值

二叉树

230. 二叉搜索树中的第K小的元素

236. 二叉树的最近公共祖先

297. 二叉树的序列话与反序列化

线段树

218. 天际线问题

排序

179. 最大数

324. 摆动排序II

二分检索

162. 寻找峰值

287. 寻找重复数

315. 计算右侧小于当前元素的个数

滑动窗口

395. 至少有K个重复字符的最长子串

动态规划

124. 二叉树中的最大路径和

128. 最长连续序列

198. 打家劫舍

279. 完全平方数

300. 最长上升子序列

322. 零钱兑换

329. 矩阵中的最长递增路径

图论

127. 单词接龙

200. 岛屿的个数

207. 课程表

210. 课程表II

字符串

125. 验证回文串

131. 分割回文串

139. 单词拆分

140. 单词拆分II

208. 实现前缀树

212. 单词搜索II

242. 有效的字母异位词

387. 字符串中的第一个唯一字符

344. 反转字符串

作为补充,还有一类题目常考,并且如果平时不训练,考场上不太容易快速想出来,就是一类深度优先搜索和回溯相结合的题目,在leetcode题库中这类相似的有好几道:

如何求 1~n 这连续 n 个数的全排列

集合内元素都不相同,求子集

集合内元素可能相同,求子集

求集合的不同组合序列

各个分割字符串都是回文数:

文章参考:

https://leetcode-cn.com/explore/interview/card/top-interview-quesitons-in-2018/

https://www.zhihu.com/question/24964987/answer/200681301

http://www.sohu.com/a/311462244_473283

本文分享自微信公众号 - 小小挖掘机(wAIsjwj)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 推荐三款机器学习论文搜索利器

    简单介绍:arXiv是个提交论文预印本(preprint)的平台,里面的论文都没有经过同行评审(peer review),所以文章质量参差不齐,但却会比较新颖,...

    石晓文
  • 经验分享|AI领域:如何做优秀研究并写高水平论文?

    每个人从本科到硕士,再到博士、博士后,甚至工作以后,都会遇到做研究、写论文这个差事。论文通常是对现有工作的一个总结和展示,特别对于博士和做研究的人来说,论文则显...

    石晓文
  • 算法面试太难?反手就是一波面经

    八月参加了一些提前批的面试,包括阿里、百度、头条、贝壳、一点资讯等。整理了一些面试题,分享给大家。

    石晓文
  • 盘点互联网公司最常见的面试编程题

    互联网公司面试,笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说,败在了编程题上,去不了自己心仪的公司,拿不到想要的待遇。

    不可言诉的深渊
  • 盘点互联网公司最常见的面试编程题

    互联网公司面试,笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说,败在了编程题上,去不了自己心仪的公司,拿不到想要的待遇。

    double
  • Linux下smokeping网络监控环境部署记录

    smokeping是一款监控网络状态和稳定性的开源软件(它是rrdtool的作者开发的),通过它可以监控到公司IDC的网络状况,如延时,丢包率,是否BGP多线等...

    洗尽了浮华
  • Django -- 视图是啥?模板是何物?

    在Django的官方文档中是这么定义视图的: "一类具有相同功能和模板的网页的集合",概念比较抽象,我们直接 拿比较简单常见论坛网站来举例,可能要求创建以下视图...

    cctester
  • 『中级篇』如何在window上安装docker(六)

    IT故事会
  • 基于Docker UI 配置ceph集群

    前一篇介绍了docker在命令行下面进行的ceph部署,本篇用docker的UI进行ceph的部署,目前来说市面上还没有一款能够比较简单就能直接在OS上面去部署...

    用户2772802
  • 为什么0.1+0.2不等于0.3?原来编程语言是这么算的……

    从小我们就知道 0.1 + 0.2=0.3。但是,在光怪陆离的计算世界中,运算方式却大相径庭。

    机器之心

扫码关注云+社区

领取腾讯云代金券