2021最新汇总数据结构与算法面试题

1.Java

1.1 哈希

• Java中的HashMap的工作原理是什么？

• 什么是Hashmap?

• 如何构造一致性哈希算法

• hashCode() 和equals() 方法的重要性体现在什么地方？

• Object作为HashMap的key的话，对Object有什么要求吗？

• hashset 存的数是有序的吗？

1.2 二叉树

• 求二叉树的最大深度

• 求二叉树的最小深度

• 求二叉树中节点的个数

• 求二叉树中叶子节点的个数

• 求二叉树中第k层节点的个数

• 判断二叉树是否是平衡二叉树

• 判断二叉树是否是完全二叉树

• 两个二叉树是否完全相同

• 两个二叉树是否互为镜像

• 翻转二叉树or镜像二叉树

• 求两个二叉树的最低公共祖先节点

• 二叉树的前序遍历

• 二叉树的中序遍历

• 二叉树的后序遍历

• 前序遍历和后序遍历构造二叉树

• 在二叉树中插入节点

• 输入一个二叉树和一个整数，打印出二叉树中节点值的和等于输入整数所有的路径

• 二叉树的搜索区间

• 二叉树的层次遍历

• 二叉树内两个节点的最长距离

• 不同的二叉树

• 判断二叉树是否是合法的二叉查找树(BST)

1.3 链表

• 谈一谈，bucket如果⽤链表存储，它的缺点是什么？

• 有一个链表，奇数位升序偶数位降序，如何将链表变成升序？

• 如何反转单链表

• 现在有一个单向链表，谈一谈，如何判断链表中是否出现了环

• 随机链表的复制

1.4 数组

• 写一个算法，可以将一个二维数组顺时针旋转90度

• 一个数组，除一个元素外其它都是两两相等，求那个元素?

• 找出数组中和为S的一对组合，找出一组就行

• 求一个数组中连续子向量的最大和

• 寻找一数组中前K个最大的数

1.5 排序

• 用Java写一·个冒泡排序？

• 排序都有哪几种方法？请列举出来

• 归并排序的原理是什么？

• 堆排序的原理是什么？

• 如何得到一个数据流中的中位数？

• 你知道哪些排序算法，这些算法的时间复杂度分别是多少，解释一下快排？

1.6 堆与栈

• 内存中的栈(stack)、堆(heap) 和静态区(static area) 的用法

• heap和stack有什么区别

• 最小的k个数

• 滑动窗口最大值

• 丑数

• 前K个高频元素

• 有效的括号

• 最小栈

• 柱状图中最大的矩形

1.7 高级算法

• LRU算法的实现原理

• 为什么要设计后缀表达式，有什么好处？

• 设计一个算法，用来压缩一段URL

• id全局唯一且自增，如何实现？

• 最后一个单词的长度

1.8 动态规划

• 斐波那契数列

• 不同路径

• 爬楼梯

• 零钱兑换

• 打家劫舍

• 编辑距离

2.C++

2.1 数组

• Array&List， 数组和链表的区别

• 一组有序数（从小到大排列），有负有正，找出绝对值最小值

• 数组中重复的数字

• 一个长度为N的整形数组，数组中每个元素的取值范围是[0,n-1],判断该数组否有重复的数，请说一下你的思路并手写代码

2.2 排序

• 手写一下快排代码

• 介绍一下各种排序算法及其复杂度

• 稳定排序有哪几种？

• 问求第k大的数的方法以及各自的复杂度是怎样的？当有相同元素时，还可以使用什么不同的方法求第k大的元素？

• 海量数据如何去取最大的k个

• 快排的时间复杂度最差是多少？什么时候时间最差

• 什么是快排算法；以及什么是稳定性排序，快排是稳定性的吗；快排算法最差情况推导公式

2.3 动态规划

• 手写代码：最长公共连续子序列

• 手写代码：求一个字符串最长回文子串

• 手写代码：求最大子序和

2.4 链表

• 手写代码：如何合并两个有序链表

• 手写代码：反转链表

• 判断一个链表是否为回文链表，说出思路并手写代码

• 什么是单链表，如何判断两个单向链表是否相交

2.5 高级算法

• 什么是LRU缓存

• 洗牌算法

2.6 字符串

• 给你一个字符串，找出第一个不重复的字符，如“abbbabcd”，则第一个不重复就是c

• 最长公共前缀

• 有效的字母异位词

3.Golang

3.1 递归&回溯

• 手写代码：两数相加

• 手写代码：括号生成

• 手写代码：验证二叉搜索树

• 二叉树的最大深度

• 二叉树的最近公共祖先

• 全排列

3.2 并查集

• 手写代码：省份数量

• 手写代码：岛屿数量

• 手写代码：最长连续数列

3.3 字符串

• 手写代码：转换成小写字母

• 手写代码：最长公共前缀

• 手写代码：有效的字母异位词