第一部分:Shopee新加坡Java社招面经
第一轮:技术面试
Java基础
相关服务:新加坡服务器
-
HashMap底层实现原理,JDK1.8前后的变化
-
原理:基于数组+链表/红黑树的结构,通过键的
hashCode()计算索引,存储键值对。 -
JDK1.8前:数组+链表。哈希冲突时,新元素采用头插法插入链表。在多线程环境下,扩容时可能产生环形链表,导致CPU 100%。
-
JDK1.8后:
-
数据结构:数组+链表/红黑树。当链表长度超过阈值(默认8)且数组容量>=64时,链表转换为红黑树,以提高查询效率(O(n) -> O(log n))。当红黑树节点数小于6时,退化为链表。
-
插入方式:改为尾插法,解决了扩容时的环形链表问题。
-
哈希算法优化:简化了哈希计算,提高了效率。
-
-
-
详细解释ConcurrentHashMap的分段锁机制
-
JDK1.7及之前:采用分段锁(Segment)。整个Hash表被分成多个Segment(默认为16个),每个Segment都是一个独立的哈希表,自带一把锁。读写操作首先定位到Segment,然后对该Segment加锁。这样,不同Segment的操作可以并发进行,实现了锁分离,提高了并发度。
-
JDK1.8及之后:摒弃了分段锁,采用
synchronized+ CAS(Compare-And-Swap) 来保证并发安全。-
CAS:用于无竞争下的节点插入。
-
synchronized:只锁住当前哈希桶(链表的头节点或红黑树的根节点),锁粒度更细,并发性能更高。
-
-
-
JVM内存模型及各区域功能
-
程序计数器:当前线程所执行的字节码的行号指示器。
-
Java虚拟机栈:用于存储栈帧,每个方法调用对应一个栈帧,用于存储局部变量表、操作数栈、动态链接、方法出口等信息。
-
本地方法栈:为Native方法服务。
-
Java堆:所有对象实例和数组内存分配的地方,是垃圾回收的主要区域。可分为新生代(Eden, Survivor0, Survivor1)和老年代。
-
方法区:存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。JDK8后称为“元空间”。
-
运行时常量池:方法区的一部分,存放编译期生成的各种字面量和符号引用。
-
-
垃圾回收算法对比(G1 vs CMS)
-
CMS:以获取最短回收停顿时间为目标。采用“标记-清除”算法,过程分为:初始标记、并发标记、重新标记、并发清除。优点是低停顿,缺点是会产生内存碎片,且对CPU资源敏感。
-
G1:面向服务端应用,将堆划分为多个大小相等的Region。采用“标记-整理”算法。优点:
-
可预测的停顿时间模型。
-
整体上看是“标记-整理”,局部(两个Region之间)是“复制”算法,不会产生内存碎片。
-
能独立管理整个堆,不需要配合其他收集器。
-
-
分布式系统
-
CAP理论的实际应用场景分析
-
C一致性、A可用性、P分区容错性。三者不可兼得,必须牺牲一个。
-
CP(一致性+分区容错性):如ZooKeeper。当网络分区发生时,为保证一致性,它会拒绝客户端的写请求,牺牲了可用性。
-
AP(可用性+分区容错性):如Eureka。当网络分区发生时,节点之间无法同步数据,但仍接受读写请求,可能返回旧数据,牺牲了一致性以保证服务可用。
-
CA(一致性+可用性):在分布式系统中难以实现,因为网络故障是必然的(P必须存在),所以通常在单机数据库中看到。
-
-
分布式事务解决方案(2PC、TCC、SAGA)
-
2PC(两阶段提交):由一个协调者协调多个参与者。
-
阶段一(准备):协调者询问所有参与者是否可以提交,参与者执行事务但不提交,并锁定资源。
-
阶段二(提交/回滚):如果所有参与者都回复“是”,则协调者发送提交命令;否则发送回滚命令。
-
缺点:同步阻塞、单点问题、数据不一致风险。
-
-
TCC(Try-Confirm-Cancel):一个业务逻辑需要拆分为三个操作。
-
Try:尝试执行业务,完成所有业务的检查,并预留必须的资源。
-
Confirm:确认执行业务,真正提交,要求Try成功则Confirm一定能成功。
-
Cancel:取消执行业务,释放Try阶段预留的资源。
-
优点:最终保证一致性,性能较好。缺点:对代码侵入性强,需要为每个事务逻辑设计TCC接口。
-
-
SAGA:将一个长事务拆分为多个本地短事务,每个短事务都有对应的补偿事务。
-
执行方式:顺序执行所有短事务,如果其中某一个失败,则逆向执行之前所有已成功事务的补偿事务。
-
优点:一阶段提交,性能高,无锁。缺点:编程模型复杂,难以调试。
-
-
-
实现分布式锁的几种方式及优劣比较
-
基于数据库:利用数据库的唯一约束或悲观锁。
-
优:实现简单。
-
劣:性能差,对数据库压力大,不具备可重入性。
-
-
基于Redis:使用
SETNX(set if not exist)命令。-
优:性能极高。
-
劣:需要处理锁超时、误删、原子性等问题。可通过Redisson客户端或RedLock算法优化。
-
-
基于ZooKeeper:利用临时顺序节点。
-
优:可靠性高,具备监听机制,可避免惊群效应。
-
劣:性能不如Redis,需要维护ZK集群。
-
-
系统设计
-
设计一个高并发电商秒杀系统
-
流量削峰策略:
-
将静态资源(图片、CSS/JS)推送到CDN。
-
答题/验证码:在秒杀开始时,让用户进行简单交互,分散请求。
-
消息队列异步化:用户请求先进入消息队列,后端服务按自身处理能力消费,超出队列长度的请求直接返回“秒杀失败”。
-
-
库存扣减的原子性保证:
-
Redis原子操作:在Redis中预扣库存,使用
DECR命令,该命令是原子性的。 -
数据库扣减:
UPDATE stock SET count = count - 1 WHERE product_id = ? AND count > 0,利用数据库的行锁和原子更新。 -
最终一致性:Redis扣减成功后,发送消息到MQ,由下游服务完成数据库的最终扣减和订单创建。
-
-
防刷机制设计:
-
限流:网关层对同一用户ID/IP进行频率限制。
-
验证码:防止机器人脚本。
-
活动校验:校验用户身份、参与资格等。
-
-
-
微服务架构下的服务发现与负载均衡实现
-
服务发现:服务实例启动时向服务注册中心(如Nacos, Eureka, Consul)注册自己的网络地址;服务消费者从注册中心拉取服务提供者列表。
-
负载均衡:
-
客户端负载均衡:在消费者端集成负载均衡组件(如Ribbon),消费者自己从服务列表中选择一个实例进行调用。策略有轮询、随机、加权、最小连接数等。
-
服务端负载均衡:通过一个独立的负载均衡服务器(如Nginx, API Gateway)来转发请求。
-
-
第二轮:算法与编码
-
实现LFU缓存淘汰算法(要求O(1)时间复杂度)
-
需要使用两个HashMap和一个双向链表(或多个频次桶)。
-
HashMap<Key, Node>:存储键和节点(节点包含key, value, freq)。 -
HashMap<Freq, DoublyLinkedList>:存储频率和对应的双向链表(头尾是最近和最旧)。 -
核心操作:
-
get(key):通过第一个HashMap找到节点,将其从原freq链表移除,放入freq+1的链表头部。更新最小频率。 -
put(key, value):若存在,同get并更新值。若不存在且缓存已满,则从最小freq的链表尾部移除节点,然后新节点放入freq=1的链表头部。
-
-
-
二叉树层序遍历及之字形打印
-
层序遍历:使用队列。将根节点入队。当队列不为空时,出队一个节点,访问它,然后将其左右子节点(如果存在)入队。
-
之字形打印:使用双端队列(Deque)或两个栈。设定一个标志位
leftToRight。奇数层从左到右,偶数层从右到左。或者,在普通层序遍历后,将偶数层的结果反转。
-
-
动态规划:股票买卖问题变种
-
经典问题框架:定义状态
dp[i][k][0 or 1],表示第i天,最多进行了k笔交易,手上不持有(0) 或持有(1) 股票的最大利润。 -
状态转移方程:
-
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) -
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
-
-
根据具体变种(如冷冻期、手续费、交易次数无限等)调整方程和初始状态。
-
系统问题
-
排查线上CPU100%问题的完整流程
-
1. 定位高CPU进程:
top命令,找到PID。 -
2. 定位高CPU线程:
top -Hp <PID>,找到线程ID(TID)。 -
3. 线程ID转换:将TID转换为16进制:
printf "%x\n" <TID>。 -
4. 分析线程栈:使用
jstack <PID> | grep -A 20 <nid>(nid是16进制的TID)查看该线程的堆栈信息。 -
5. 分析代码:根据堆栈信息定位到问题代码行。常见原因:死循环、频繁GC、计算密集型任务。
-
辅助工具:可以使用
Arthas工具的thread -n命令直接查看最繁忙的线程。
-
-
数据库慢查询优化方案
-
1. 定位慢SQL:开启MySQL慢查询日志,或使用监控工具。
-
2. 使用EXPLAIN分析:查看SQL的执行计划,关注
type(访问类型,至少range级别)、key(使用的索引)、rows(扫描行数)、Extra(Using filesort, Using temporary等)。 -
3. 优化策略:
-
索引优化:为
WHERE、ORDER BY、GROUP BY的字段建立合适的索引。避免索引失效(如函数操作、类型转换、!=、OR等)。 -
SQL语句优化:避免
SELECT *,只取所需字段;优化子查询,改用JOIN;分解大连接查询。 -
表结构优化:选择合适的数据类型,范式/反范式设计。
-
数据库参数调优:调整
buffer_pool_size等。
-
-
第三轮:项目深度
此部分无标准答案,但准备时应遵循 STAR原则:
-
S:项目背景和目标。
-
T:你承担的任务和职责。
-
A:你采取的具体行动和技术方案(对应问题:架构、瓶颈、拆分决策)。
-
R:最终达成的结果(性能提升百分比、稳定性提高、业务增长等)。
准备要点:
-
高并发项目:清晰地画出系统架构图,说明如何通过缓存、消息队列、分库分表等手段支撑高流量。
-
性能瓶颈:准备一个真实案例,描述如何发现(监控)、分析(工具、思路)、解决(优化方案)一个性能瓶颈。
-
微服务拆分:说明拆分的原则(如单一职责、边界上下文)、过程(如何平滑迁移)、带来的价值(团队职责清晰、迭代更快)和挑战(分布式事务、链路追踪)。
第二部分:百度大数据挖掘二面面经
技术考察
机器学习基础
-
逻辑回归推导及正则化作用
-
推导:
-
模型:
h(x) = sigmoid(w^T x) = 1 / (1 + e^(-w^T x)),输出为属于正类的概率。 -
假设数据服从伯努利分布,建立似然函数。
-
取对数,得到对数似然函数
L(w)。 -
使用梯度上升法最大化
L(w),其梯度为∇L(w) = Σ (y_i - h(x_i)) * x_i。通过迭代更新w。
-
-
正则化作用:
-
L1正则化(Lasso):在损失函数中加入权重的L1范数。倾向于产生稀疏权重,即让一部分特征的权重为0,可用于特征选择。
-
L2正则化(Ridge):在损失函数中加入权重的L2范数。使权重平滑,防止过拟合,但不会产生稀疏解。
-
-
-
随机森林与GBDT的异同点分析
-
相同点:都是集成学习算法,由多棵决策树构成。
-
不同点:
-
随机森林:
-
Bagging思想,并行生成树。
-
每棵树独立,通过投票/平均得出结果。
-
引入行采样和列采样,增加多样性。
-
主要减少模型方差。
-
-
GBDT:
-
Boosting思想,串行生成树。
-
后一棵树拟合前一棵树的残差(负梯度)。
-
将所有树的结果累加得出最终结果。
-
主要减少模型偏差。
-
-
-
-
特征工程中的常见处理方法
-
缺失值处理:删除、填充(均值/中位数/众数/模型预测)。
-
异常值处理:箱线图/3σ法则识别,删除或截断。
-
编码:对类别型特征进行独热编码、标签编码。
-
数值缩放:标准化、归一化。
-
特征构造:基于业务知识创造新特征。
-
特征选择:过滤法(卡方检验、相关系数)、包裹法(RFECV)、嵌入法(L1正则化、树模型特征重要性)。
-
大数据技术
-
Spark内存管理机制详解
-
Spark内存分为JVM堆内内存和堆外内存。
-
堆内内存由统一的
MemoryManager管理,分为几个区域:-
Storage Memory:用于缓存RDD、广播变量。
-
Execution Memory:用于Shuffle、Join、Sort等计算过程中的临时数据。
-
User Memory:存储RDD转换操作中用户定义的数据结构。
-
Reserved Memory:系统预留。
-
-
Spark通过动态占用机制,允许Execution和Storage区域在对方空闲时互相借用,提高了内存利用率。
-
-
MapReduce实现join的几种方式
-
Reduce端Join:Mapper为每条数据打上来源标签,通过Join Key进行分区,在Reducer端进行关联。简单但Shuffle数据量大。
-
Map端Join:利用
DistributedCache将小表广播到每个Mapper节点,在Map阶段直接完成关联。无Shuffle,效率高,但要求一张表足够小。 -
SemiJoin:在Map端Join的变种,先对小表去重,再广播,进一步减少网络传输。
-
-
HBase存储架构与读写流程
-
架构:
-
HMaster:负责元数据管理和RegionServer负载均衡。
-
RegionServer:负责处理用户IO请求。
-
Region:表的分片,当表变大时会自动分裂。
-
Store:一个Region中的一个列族。包含一个MemStore(内存写缓存)和多个HFile(磁盘存储文件)。
-
-
写流程:Client -> Zookeeper(找Meta表Region)-> Meta表(找目标Region)-> RegionServer -> 先写WAL(HLog)-> 再写MemStore -> MemStore满后刷写到HFile。
-
读流程:Client -> ... -> RegionServer -> 同时读取BlockCache、MemStore和HFile,合并后返回结果。
-
算法实现
-
手写PageRank算法伪代码
python
# 初始化:每个页面的PR值 = 1/N PR = [1.0 / N] * N for iter in range(max_iters): new_PR = [0.0] * N for i in range(N): # 遍历每个页面i for j in inlinks[i]: # 所有指向i的页面j # 页面j将其当前的PR值平均分配给它的所有出链 new_PR[i] += PR[j] / out_degree[j] # 处理阻尼因子d:用户以概率d按照链接浏览,以概率(1-d)随机跳转 new_PR = [d * value + (1 - d) / N for value in new_PR] # 检查收敛 if convergence(PR, new_PR): break PR = new_PR -
推荐系统中的协同过滤实现
-
UserCF:找和目标用户兴趣相似的用户群体,推荐这个群体喜欢的物品。
-
核心:计算用户相似度(余弦、皮尔逊)。
-
-
ItemCF:找和目标用户历史上喜欢的物品相似的其他物品。
-
核心:计算物品相似度(通常基于共同喜欢两个物品的用户数)。
-
-
实现:在Spark中,通过
RowMatrix.columnSimilarities可以高效计算物品或用户的余弦相似度。
-
-
海量数据TopK问题的多种解决方案对比
-
全局排序:直接排序取前K个。数据量巨大时不可行。
-
局部淘汰法:维护一个大小为K的小顶堆。遍历所有数据,比堆顶大则插入。O(n log K)。
-
分治法:将数据分片,在每个分片上找TopK,再合并所有TopK找最终的TopK。
-
Bitmap法:如果数据是整数且范围有限,可以用位图统计,然后从大到小扫描。

-
项目经验 & 系统设计
此部分与Java项目深度类似,需用STAR原则准备一个完整的数据挖掘案例。
设计一个实时用户行为分析系统
-
数据采集层架构:
-
前端/APP埋点 -> 日志收集Agent(如Filebeat, Flume) -> 消息队列(如Kafka,起到削峰解耦作用)。
-
-
流处理与批处理结合方案(Lambda架构):
-
流处理层:使用Flink或Spark Streaming从Kafka消费数据,进行实时计算(如每分钟PV/UV,异常行为检测),结果写入高速存储(如Redis, HBase)供实时查询。
-
批处理层:同时将Kafka的原始数据导入数据仓库(如Hive),在T+1周期内运行Spark任务进行全量、复杂的ETL和计算,得到更精准的结果,覆盖实时层可能的数据误差。
-
-
可视化展示与预警机制:
-
可视化:使用Grafana、Kibana或自研平台,从高速存储和数据仓库中读取数据,生成实时监控大屏和历史报表。
-
预警:在流处理层或监控系统中设定规则阈值(如5分钟内错误率激增),通过邮件、短信、钉钉/企微机器人触发告警。
-






