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] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 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 是区间集合的大小。需要额外的空间存储结果集合。