程序员必须掌握哪些算法?附“互联网公司最常见的算法面试题”

2019年04月09日 676点热度 0人点赞 0条评论

01 算法与数据结构

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

算法 - Algorithms

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

数据结构 - Data Structures

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

02 经典面试题目

此外,我们还为大家整理了一些互联网公司面试常见的 算法题目 :

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

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

136. 只出现一次的数字

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

169. 求众数

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

240. 搜索二维矩阵 II

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

88.合并两个有序数组

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

887. 鸡蛋掉落

 

Horry

一个专门收集Android面试题的网站

文章评论

您需要 登录 之后才可以评论