2024滴滴校招面试真题汇总及其讲解(一)
1.【基础题】集合、List和Set、HashMap、concurrentHashMap
集合
集合是 Java 中用来存储对象的一种容器。集合可以分为有序和无序两种。有序集合指的是集合中的元素有一定的顺序,而无序集合指的是集合中的元素没有一定的顺序。
List
List 是 Java 中一种有序集合,它可以存储重复的元素。List 接口有以下几个常用的实现类:
ArrayList:使用数组实现的 List,具有随机访问的优势,但插入和删除元素的效率较低。LinkedList:使用链表实现的 List,具有插入和删除元素效率高的优势,但随机访问的效率较低。Vector:使用数组实现的 List,具有线程安全的优势,但效率较低。Set
Set 是 Java 中一种无序集合,它不能存储重复的元素。Set 接口有以下几个常用的实现类:
HashSet:使用哈希表实现的 Set,具有插入和删除元素效率高的优势。TreeSet:使用二叉树实现的 Set,具有元素有序的优势。LinkedHashSet:使用链表实现的 Set,具有元素有序且插入和删除元素效率较高的优势。HashMap
HashMap 是 Java 中一种键值对映射的集合,它可以存储键值对(key-value)类型的对象。HashMap 使用哈希表来存储键值对,具有插入和删除元素效率高的优势。
ConcurrentHashMap
ConcurrentHashMap 是 Java 中一种线程安全的 HashMap,它使用分段锁来保证线程安全。ConcurrentHashMap 具有 HashMap 的所有优势,并且还具有线程安全的特性。
总结
集合类型 有序 重复 实现类List 是 是 ArrayList、LinkedList、VectorSet 否 否 HashSet、TreeSet、LinkedHashSetMap 否 否 HashMap、ConcurrentHashMap示例
Java
import java.util.ArrayList; import java.util.HashSet; import java.util.HashMap; import java.util.concurrent.ConcurrentHashMap; public class CollectionsExample { public static void main(String[] args) { // List 示例 ArrayList<String> list = new ArrayList<>(); list.add("a"); list.add("b"); list.add("c"); System.out.println(list); // [a, b, c] // Set 示例 HashSet<String> set = new HashSet<>(); set.add("a"); set.add("b"); set.add("c"); System.out.println(set); // [a, b, c] // Map 示例 HashMap<String, Integer> map = new HashMap<>(); map.put("a", 1); map.put("b", 2); map.put("c", 3); System.out.println(map); // {a=1, b=2, c=3} // ConcurrentHashMap 示例 ConcurrentHashMap<String, Integer> concurrentHashMap = new ConcurrentHashMap<>(); concurrentHashMap.put("a", 1); concurrentHashMap.put("b", 2); concurrentHashMap.put("c", 3); System.out.println(concurrentHashMap); // {a=1, b=2, c=3} } }
Java 中的集合提供了多种类型的集合,可以满足不同的需求。在使用集合时,应根据具体的需求选择合适的集合类型。
2.【基础题】JVM 内存区域、垃圾回收
JVM 内存区域
JVM 将 Java 程序的内存划分为以下几个区域:
- 程序计数器:存储当前线程正在执行的字节码指令地址。
- 虚拟机栈:存储方法的局部变量、操作数栈、动态链接、方法出口等信息。
- 本地方法栈:存储本地方法的相关信息。
- 堆:存储对象实例和数组。
- 方法区:存储类的元数据、常量、静态变量、即时编译器编译后的代码等。
垃圾回收
垃圾回收是 Java 虚拟机自动进行的,不需要程序员手动管理。垃圾回收器会在内存不足时,扫描堆内存中不再被使用的对象,并将其回收。
垃圾回收算法
垃圾回收算法可以分为以下几种:
- 引用计数法:为每个对象维护一个引用计数器,当有其他对象引用该对象时,引用计数器加 1,当引用失效时,引用计数器减 1。当引用计数器为 0 时,该对象可以被回收。
- 标记-清除法:首先标记出所有存活对象,然后将未标记的对象清除。
- 复制算法:将堆内存分为新生代和老年代,每次垃圾回收只回收新生代中的对象,并将存活对象复制到老年代。
- 标记-整理法:将堆内存分为两部分,每次垃圾回收将存活对象整理到同一端,然后将空闲的空间整理到另一端。
垃圾回收优化
为了提高垃圾回收效率,可以采取以下措施:
- 避免创建过多短期存活对象。
- 尽量使用不可变对象。
- 使用弱引用或虚引用。
- 使用大对象池。
3.【算法题】合并区间
题目
以数组 intervals
表示若干个区间的集合,其中单个区间为 intervals[i] = [start
i
, end
i
]
。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
解题思路:
首先将区间集合按照左端点升序排序。然后依次遍历区间集合,如果当前区间和上一个区间有交集,则将两个区间的右端点取最大值作为合并后的区间的右端点。否则,将当前区间加入结果集合中。Java 代码:
Java
class Solution { public int[][] merge(int[][] intervals) { // 按照左端点升序排序 Arrays.sort(intervals, (a, b) -> a[0] - b[0]); List<int[]> result = new ArrayList<>(); int[] prev = intervals[0]; for (int i = 1; i < intervals.length; i++) { int[] curr = intervals[i]; if (curr[0] <= prev[1]) { prev[1] = Math.max(prev[1], curr[1]); } else { result.add(prev); prev = curr; } } result.add(prev); return result.toArray(new int[result.size()][]); } }
时间复杂度: O(n log n),其中 n 是区间集合的大小。排序需要 O(n log n) 的时间复杂度,遍历需要 O(n) 的时间复杂度。
空间复杂度: O(n),其中 n 是区间集合的大小。需要额外的空间存储结果集合。
#24届软开秋招面试经验大赏#
腾讯,字节跳动,阿里巴巴,百度,美团,快手,有赞,理想,蔚来,小鹏等大厂校招笔试真题,面试真题讲解。目标100家公司