pdd服务端一面面经

面试题目

1. 项目经历：深入挖掘项目细节，要求候选人自行挑选一个项目进行阐述并回答细节问题。
2. Java基础：考察Java常用数据类型，重点询问ArrayList等集合类的底层实现与源码细节。
3. 数学题：计算ArrayList扩容过程中的平均时间复杂度。
4. 算法题：手撕代码“和为0的子数组”。

参考解析

1. ArrayList底层源码：底层基于动态数组实现。扩容逻辑在add方法中，通常通过newCapacity = oldCapacity + (oldCapacity >> 1)（即1.5倍扩容）实现，扩容涉及Arrays.copyOf进行数组拷贝。
2. 扩容平均时间复杂度：扩容是偶尔发生的（O(N)），但大部分操作是O(1)。利用均摊分析法，单个元素添加的平均复杂度为O(1)。
3. 和为0的子数组：利用前缀和（Prefix Sum）+ 哈希表（HashMap）求解。记录前缀和出现的次数，如果某前缀和在哈希表中已存在，说明中间段之和为0。