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

一面

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

项目

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

基础

并发

• 条件变量内部有锁，为什么在wait条件变量时，最外层还需要加锁（跪）
• 除了notify，wait还有什么情况下可能被唤醒（跪）

书到用时方恨少，题到问时才知浅。并发复习的太少，这部分完全忘却了。

算法

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

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

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

• 假设不包含重复值
• 给出明确的BST的定义：
  1. l 是BST
  2. r 是BST
  3. 满足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。

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是怎么启动的

说的比较糙：

1. NM收到指令
2. 创建Container状态机、初始化资源等
3. ContainerLaucher服务收到LAUNCH_CONTAINER事件
4. 创建launch_container脚本
5. 创建container_executor脚本，该脚本里会启动该java进程

container运行需要下载一些资源，了解这个过程吗

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

系统设计

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

• 挂载表配置在客户端，所以修改挂载表后，客户端也必须作出同步的修改，无法做到用户无感知或低感知
• Federation的在扩展NameNode的同时也有负载均衡的目的，但是客户端挂载相当于人工维护负载均衡，流量发生任何变化都无法维持均衡

只想出来这两点。待完善。

不使用挂载表，如何实现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相等。

总结如下：

1. 如果equals相等，那么hashCode也必须相等
2. 对同一个对象，将其插入HashMap前后，hashCode不可变

工程代码

按需求实现新的hash表（跪）

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

interface SimpleMap<K, V> {
 K get(K key);
 V put(K key, V value);
 V remove(K key);
}

要求：

• 尽量提高空间利用率
• 可以牺牲部分性能

当即想到了线性探测、rehash等方法，觉得so easy，确认可以用线性探测后，就开始打草稿了，然后誊抄。需要注意的是del方法，我采取的思路是删除后将tail节点填充到被删除的位置。啪啪啪一顿写，结果交了答案——我又意识到了大bug，思路就错了；还发现了一个put方法中的一个死循环。不过这两点都属于我基本思路上的问题，就不秀错误代码了。

回来自己想，现在补充正确代码，未实现的非核心代码参照HashMap：

public class LinearProbingHashMap<K, V> implements SimpleMap<K, V> {

  @Override
  public V get(Object key) {
    if (key == null) {
      return null;
    }

    int pos = indexFor(hash(key));
    for (int i = 0;
         i < table.length && table[pos] != null;
         i++, pos = (pos + 1) % table.length) {
      if (table[pos] == Entry.DELETED_ENTRY) {
        continue;
      }
      if (table[pos].keyHash == key.hashCode()
          && (table[pos].key == key || table[pos].key.equals(key))) {
        return table[pos].value;
      }
    }
    return null;
  }

  @Override
  public V put(K key, V value) {
    if (key == null) {
      return null;
    }

    int pos = indexFor(hash(key));
    int lastEmptyPos = -1;
    for (int i = 0;
         i < table.length && table[pos] != null;
         i++, pos = (pos + 1) % table.length) {
      if (table[pos] == Entry.DELETED_ENTRY) {
        lastEmptyPos = pos;
      }
      if (table[pos].keyHash == key.hashCode()
          && (table[pos].key == key || table[pos].key.equals(key))) {
        V oldValee = table[pos].value;
        table[pos].value = value;
        return oldValee;
      }
    }

    if (size + 1 < threshold) {
      if (lastEmptyPos == -1) {
        // assert table[pos] == null;
        lastEmptyPos = pos;
      }
      table[lastEmptyPos] = new Entry<>(key, value);
      size++;
      return null;
    }

    LinearProbingHashMap<K, V> newMap = new LinearProbingHashMap<>(table.length * 2);
    for (Entry<K, V> entry : table) {
      // TODO: 2017/8/31 remove extra cost on copy entry
      if (entry != null && entry != Entry.DELETED_ENTRY) {
        newMap.put(entry.key, entry.value);
      }
    }
    init(newMap); // update table, size, loadFactor, threshold, and etc.
    put(key, value);

    return null;
  }

  @Override
  public V remove(Object key) {
    if (key == null) {
      return null;
    }

    int pos = indexFor(hash(key));
    for (int i = 0;
         i < table.length && table[pos] != null;
         i++, pos = (pos + 1) % table.length) {
      if (table[pos] == Entry.DELETED_ENTRY) {
        continue;
      }
      if (table[pos].keyHash == key.hashCode()
          && (table[pos].key == key || table[pos].key.equals(key))) {
        V oldValue = table[pos].value;
        table[pos] = (Entry<K, V>) Entry.DELETED_ENTRY;
        size--;
        return oldValue;
      }
    }

    return null;
  }
}

提问

• 如果有幸加入，入职后可能负责的工作内容
• 总共几轮面试
• 面试评价

恩，我以为到提问环节就是最后一轮技术面呢，问了问题1，面试官表示这是三面才会聊的。总共有三轮面试，一面二面水平差不多，三面是技术leader。

正面评价：

• 整体表现不错
• 代码风格挺好

负面评价：

• 最后一道题有死循环是大问题（也就是思路可以原谅，但是死循环不能原谅）
• 这道题看起来简单，但我面试的人没有一个能写的没有问题。以后应该想好再动手
• 你要搞分布式的话，并发是基础。本来最后一道题也想考你并发，但是说并发掌握的不好，就没考你

三面（HR面）

等了三面的面试官很久都没有来，我实在憋不住就写了个纸条，把门开着去上厕所了。。。结果回来——握草女面试官！再看正脸，握草化妆了！怎么看都不像是技术leader，一问才知道是HR。HR表示，技术leader在开会，刚才跟他碰了一下，他说看前面两面面试官评价都不错，他不需要面了，所以直接跳到了HR面。

给我整的分不清是好消息还是坏消息。听说这个leader是90年的，天大本科毕业就工作了，带着一群80、90后，非常屌，本来想借着面试瞻仰一下，真是可惜。后面就是正常的HR面，不过感觉头条的HR问的真多啊，各种兴趣爱好，评价，家庭什么的。第一次经历这阵仗，学到了学到了。

最后问我有没有拿到其他offer，老实回答了。我个人觉得，面试是个相互选择的过程，希望公司和面试者都能坦诚相待。

总结

面试完，又分别跟大学同学（头条暑期实习）和涛神聊了聊，两个人都反应，头条的压力非常大，但是同时也主动表示食堂好。看来只要公司愿意给高价，什么加班什么压力大都可以放一边。学到了学到了。

上次阿里面试官简历的面试三原则非常管用，这次沟通明显顺畅了许多。头条面试有一个好处，要不要你都会给通知，，，but，拒信和offer都要等好几天啊，，，HR姐姐说尽量本周五之前给通知，希望一切顺利！！

给自己的建议：

• bug free！bug free！bug free！
• 耐心学习分布式系统的理论知识，研究更多分布式系统的优秀案例
• 很多看起来简单的问题，还是不要掉以轻心，耐心想想再动笔
• 学过的东西不要丢下，原来看书虽然快，但很难吸收；这段时间建议少看书，多通过实践把知识固化。特别是并发部分，这是搞分布式的基本功，必须吃到肚子里！

本文链接：【面经】头条-2017年8月30日，散招实习生
作者：猴子007
出处：https://monkeysayhi.github.io
本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布，欢迎转载，演绎或用于商业目的，但是必须保留本文的署名及链接。