返回 登录
0

今日头条面经分享

头条是这批次面试中的一个理想公司,基础架构部。从两轮面试的情况来看,面试官的素质非常高,面试经验也比较丰富。一方面提问抓的准,不会在你明确表示准备不足的方面硬扣;一方面深度广度、代码风格均有涉及。不过总共只让我写了两道代码题,希望不是放水。

一面
一面应该还问了其他内容,但是两次面试问的太多,想不起来了。

项目

两个项目都是简单介绍,没有深入问。

基础

并发

条件变量内部有锁,为什么在wait条件变量时,最外层还需要加锁(跪)
除了notify,wait还有什么情况下可能被唤醒(跪)
书到用时方恨少,题到问时才知浅。并发复习的太少,这部分完全忘却了。
算法

判断二叉树是否是二叉搜索树

题目很熟悉了,倒是也写过。

我有点记不清二叉搜索树(BST)的定义,于是先跟面试官简单确认了下。接下来,向面试官明确题目:

假设不包含重复值
给出明确的BST的定义:
l 是BST
r 是BST
满足l < root < r
向面试官表示用分治法,然后开始写代码。写到一半,面试官又跟我说可以考虑二叉树的先序、中序、后续遍历这些。我反应过来可以直接中序遍历,遍历的同时判断序列是否递增。说了下思路,询问面试官是否可以先写我原来的解法,这样就不用换思路了,省的出错。面试官统一后我才继续写:

private class Result {
public boolean isBST;
public int min;
public int max;
public Result(boolean isBST, int min, int max) {
this.isBST = isBST;
this.min = min;
this.max = max;
}
}

public isBST(TreeNode root) {
if (root == null) {
return true;
}

Result result = dc(root);
return result.isBST;
}

private Result dc(TreeNode root) {
if (root == null) {
return null;
}
if (root.left == null && root.right == null) {
return new Result(true, root.val, root.val);
}

Result lResult = dc(root.left);
Result rResult = dc(root.right);
if (lResult != null && (!lResult.isBST || lResult.max >= root.val) {
return new Result(false, 0, 0);
}
if (rResult != null && (!rResult.isBST || rResult.min >= root.val)) {
return new Result(false, 0, 0);
}

// 忘记了这里的check,no face, no bug free
int min = root.val;
int max = root.val;
if (lResult != null) {
min = lResult.min;
}
if (rResult != null) {
max = rResult.max;
}
return new Result(true, min, max);
}
分治法代码写出来有点长,不过多长也得坚持编码风格和bug free。java学习干货面试经验,不定期分享,需要加个人q:3300863615。

but,我第一次写的还是有bug,刚把纸交给面试官我就想起来了——最后一句return没有检查空指针,,,妈的真是蠢。还好面试官没有介意,感谢感谢。

中序遍历的话,简单做可以完全保存下序列,再去check,但是浪费空间;复杂做就得一边遍历一边检查,我还没想清楚足够简洁的写法。(待补充)

二面
项目

冷数据压缩与存储——vulture

可能是我讲的越来越能抓住key point了?这是我唯一一次把vulture中的两个难点都讲了。特别是异常恢复,把压缩过程抽象成状态机还是有点讲头的。

为什么要依赖外部配置,而没有跟HDFS整合在一起
我表示也考虑过这种方案,但当时的需求是尽量简单的搞定压缩,如果跟HDFS整合的话,可能需要将冷热温的生存期、温度等都写进FileStatus,而改动这种基础类的影响太大了。

Hadoop集群监控——hawk

表示项目本身很简单,难在如何确定所监控指标的准确含义。

话说一半,意在引导面试官提问指标相关的内容,秀源码。
准确含义指什么
我把ContainerExitStatus=137时的case讲了一下。

源码

HDFS里的Federation怎么实现的

客户端挂载,如何映射 balabala。

一般Federation里还要使用HA,讲一下HA的原理

Zookeeper保障唯一时刻只有至多一个active节点;唯一的active向journalNode写数据,其他standby从journalNode读数据。

HA中两个节点同步哪些内容(跪)

开始以为跟SecondaryNameNode机制一样,后来仔细一想:standby既然能从journalNode读数据,也就不需要像SecondaryNameNode那样从active拉取editlog,自然也不需要在stanby上合并日志并同步回active。

所以,坦白自己没看过这一块内容,也没什么想法。

Yarn的源码你比较了解哪块

状态机、事件调度

container是怎么启动的

说的比较糙:

NM收到指令
创建Container状态机、初始化资源等
ContainerLaucher服务收到LAUNCH_CONTAINER事件
创建launch_container脚本
创建container_executor脚本,该脚本里会启动该java进程
container运行需要下载一些资源,了解这个过程吗

先讲三个资源等级,假设最简单的场景,刚说到ResourceLocalizer状态机,面试官就表示,“好,不用说了,我知道你看过这块”。

系统设计

用客户端挂载实现Federation的缺点

挂载表配置在客户端,所以修改挂载表后,客户端也必须作出同步的修改,无法做到用户无感知或低感知
Federation的在扩展NameNode的同时也有负载均衡的目的,但是客户端挂载相当于人工维护负载均衡,流量发生任何变化都无法维持均衡
只想出来这两点。待完善。java学习干货面试经验,不定期分享,需要加个人q:3300863615。

不使用挂载表,如何实现Federation(半跪)

我不了解这方面的内容,尝试以客户端挂载方案为baseline进行改进。

Federation的核心是目录到NameNode的映射关系。而客户端挂载的本质缺点在于将映射关系保存在客户端,因此所有功能都依赖于客户端完成。所以优化的第一步是,将映射关系保存在服务端。下面给出两种方案:

将映射保存在服务端。进一步的,如想访问/logdata目录,就创建/logdata文件,文件中保存/logdata目录映射的NameNode。每次客户端都先访问/logdata文件,获取映射的NameNode,再到该NameNode上访问/logdata目录。效果相当于把客户端挂载移到了服务端。
在NameNode前架设Proxy服务,由Proxy在内存中维护映射关系。甚至可基于Proxy实现新的均衡器和自动化挂载,实现不同标准(跨NameNode、同NameNode)的数据均衡和流量均衡。
我回答的不完全是面试官想要的——面试官问我看过Hdaoop 3.0的源码吗,我表示完全没看过,面试官表示没看过的话应该答不上来。

如果用Proxy的方案,估计一下qps

1w个节点,每个节点都是 40核+256G,全部跑MR,每个container1核+2G。估计Proxy需要承受的qps。
假设就跑了一个AM,它申请了集群所有的container,全部跑mapper,可忽略该AM。假设每个mapper在1min(60s)内需要访问5次NameNode,则至少需要访问5次Proxy(获取映射)。则:

qps = (10E4 * 40 / 1) * 5次/60s = 3.67 * 10E4 次/s
面试官问我这么大的规模单机扛得住吗,,,我表示现在的技术扛万级qps不是很轻松吗。恩,,可能我还是没有get到考点吧。

基础

并发(半跪)

我一面中并发答的很差,就主动跟二面面试官表示并发这块复习的不好。面试官心领神会,也没有出很难的题目。万谢万谢。

Java中可以通过哪些方式使用锁
synchronized、ReentrantLock、用AQS裸写一个锁。

这里我本来也写了Condition、CountDownLatch那些并发工具,后来觉得这更属于同步,所以又把它们删了。这种属于偏概念的套路题,需要刷面经才能知道套路答案。
如何让锁实现“可重入”(半跪)
我一开始觉得先不用说重入次数,就只回答了需要在锁内部记录owner。结果面试官提醒多重入的场景我才说还要记录重入次数,搞得好像面试官提醒我才想到。

所以说下次不能耍小聪明,能想到的点尽量说出来。如果面试官不拦着你,你就由简到难,一直说下去,说到一个完整且你说不下去的地方为止。
讲一个你熟悉的并发的内容
对比讲了HashTable和ConcurrentHashMap。

估计面试官问我这个问题只是想看看我是不是并发一点都不会,毕竟我前面并发答的那么差。
问个简单的,Object类中有哪些方法(半跪)

wait, notify, notifyAll
toString
hashCode, equals
然后就说不上来了。

现补充如下:

public class Object {
private static native void registerNatives();
static {
registerNatives();
}

public final native Class<?> getClass();

public native int hashCode();
public boolean equals(Object obj) {
    return (this == obj);
}

protected native Object clone() throws CloneNotSupportedException;

public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
}

public final native void notify();
public final native void notifyAll();
public final native void wait(long timeout) throws InterruptedException;
public final void wait(long timeout, int nanos) throws InterruptedException {...}
public final void wait() throws InterruptedException {
    wait(0);
}
protected void finalize() throws Throwable { }

}
主要漏答的是clone, getClass。finalize, registerNatives也尽量记住。

覆写hashCode时有什么需要注意的

主要是需要判断相等的时候,比如HashMap的get方法,对hashCode和equals的调用顺序有要求:

if (table[pos].key.hashCode() == key.hashCode
&& (table[pos].key == key || table[pos].equals(key))) {
return table[pos];
}
只有hashCode相等的时候,equals才有可能相等,即,“覆写后,如果equals相等,那么hashCode也必须相等”。

同时,对于HashMap还要保证插入前后,key的hashCode相等。

总结如下:

如果equals相等,那么hashCode也必须相等
对同一个对象,将其插入HashMap前后,hashCode不可变
工程代码

按需求实现新的hash表(跪)

我们知道NameNode中保存了BlockId到BlockInfo的映射,以满足快速查找的目的。如果直接用HashMap实现(当然,实际用的也不是HashMap,用的Google的LightWeightGSet),由于HashMap内部用拉链发实现,每个节点都有最有两个指针,假设每个指针占2字节,那么1亿个Block最少要占用4亿字节,假设造成很大的空间浪费。你需要实现一个新的hash表,接口定义:
interface SimpleMap

评论