面试经验总结 一

坐在图书馆，下面一个作业是，拿C语言，实现 malloc 和 free 函数。尽可能的高效，必须安全。
突然觉得有点恶心，现在不想写。
于是开始做一件重要的事，总结面试经验。
的确，一路走来，跪了这么多家，我自己有很多没做好，而这，都是财富。

我下面说的，都是我碰到的实在问题，各个方面。
从Google 说起。

Google： 谷歌前，买了杯咖啡。喝完了。呆了半个小时后去面试地点开始面。
还是小房间。
题目是， 设计题目
建立一个王朝。
王朝只有一个皇帝，
皇帝有很多儿子，每个儿子又可以有很多儿子。
这样，我就想起了一棵多叉树。
然后，每个人都会死去的。

下面实现三个函数。

1. 让这个string代表的人，死去。
die(String curr) {}
2. 让string 代表的parent生下一个孩子。
born(String parent) {}
3. 打印整个皇朝，dfs 的方式。
print(Node root) {}

题意差不多就这个意思。
然后让我从头到尾写出来，实现这个系统。

我记得当时我用了两个hashmap + 一个多叉树
一个hashmap， 存 <name, Node> // 这个名字对应的结点
一个hashmap, 存 <Node, boolean> // 这个结点的人死没死
然后多叉树就是
Node {
String name;
LinkedList<Node> children;
}

然后上面三个操作都可以很简单的做出来。
打印的话就用dfs
死亡的话就把对应结点找出来，标记为true
生的话，就找到parent结点，给他加一个孩子。

于是 follow up来了。才是重点。
这棵树有多深？
depth = logD(N),
那么大概有多少个结点？
D ^ depth
如果有100个朝代，大概N在什么数量级？
D ^ depth
那么print的时间复杂度？
O(D ^ depth)
那应该很大吧？
恩。
优化一下？
然后我发现，其实一个人最多能活个两三个朝代。
对于死去的人，我还是简单地存在树里，只是标记为死亡。这样，他们其实浪费了空间时间，而没有任何意义。

所以不能这么做。要把他们从树里面删除。那他们的孩子呢？
在把他们的孩子，一个个移动到 parent 的 children list里面的前面。
这里，一定是插在这个链表的前面，才能保证dfs的时候顺序不变。
这样100代以后，其实活下来的人，也就只有三层这样，会大大减少复杂度。

这道题目不难，但是要完全的写出来，还是有一定难度。还有许多corner case 需要考虑。比如，老皇帝，root死了，怎么办？所以要有一个虚root结点。

当时感觉发挥的还不错，但是还是没有一下子就考虑清楚，然后就开始动笔。真的不好！
**
所以，当你看到一道题目,觉得自己有把握做出来的话，一定要考虑点时间，想清楚了，任何细节，不想没想清楚就开始写，一边写一边想，往往会出现问题。
**

还有，当时喝了咖啡，面试的时候，特别想上厕所。
这真的也得注意。面试前不要喝太多水。面试一般持续一个半小时到两个小时，期间，如果因为这个而分神，就太可惜了。

然后就是第二面。做了两题。
题目就不具体说了。很难。
我觉得有一些经验。
第一题，应该说是这次面试中的最难题吧。我当时没思路，就开始瞎讲。本来想糊弄过去。但我发现，谷歌的程序员，真的不是傻逼。都很聪明。他们不懂的，都是我逻辑思维里面，自己也不懂的，我含糊其辞的。
所以，我越说越乱。
所以。下次碰到不会的题目，先好好想想，不要2分钟觉得不会就放弃了，就开始瞎讲。
想想，应该用什么数据结构，用最暴力的解法，该怎么做。
然后把 brute force的解法说出来。讨论这个解法，为什么复杂度这么高。他这么慢，肯定有原因的。找出这个原因。
然后，优化他。 dp, hashmap, 等等。
数据结构就是我的刀剑，我要用好他们。
然后第三题目，他给了我很多提示，真的就差那么一点，没想出来。
出来后就想到了。面试的时候，人还是有点蒙。这个很难调整，还是经验不够。

---

下面讲讲昨天的面试。我觉得有很多可以总结。
这是一家 startup。
上来是问简历，问了我JPA，这些。我答的还不错。
然后问我在做的一个project，是不是用xml传送信息的。我说是的。
然后看我简历写过json，就开始让我现场写json
其实这个真不难。放在上学期，我肯定写出来了。
但这学期都在忙着写，php, 普通的java，aws等等，json具体的细节我忘记了。
我只记得，他是一个个的键值对。
{"key", "value"} 结果我忘记了，中间不是逗号，是冒号。

{
  "firstName": "John",
  "lastName": "Smith",
  "isAlive": true,
  "age": 25,
  "address": {
    "streetAddress": "21 2nd Street",
    "city": "New York",
    "state": "NY",
    "postalCode": "10021-3100"
  },
  "phoneNumbers": [
    {
      "type": "home",
      "number": "212 555-1234"
    },
    {
      "type": "office",
      "number": "646 555-4567"
    }
  ],
  "children": [],
  "spouse": null
}

https://en.wikipedia.org/wiki/JSON

我当时心里很冤枉。再重说下过程。
他问我写过json吗？我说我简历第二个project就是写json的，我
很熟悉！
然后他就开始让我写了。当时我整个人就慌了。。。
后来写出来，细节错了。
说实话，心里很委屈。
我真的写过。真的写过，写了也很多很多。
但是最近这几个月，我没有再碰json，所以具体的语法结构，我忘记了，但这个，真的这么重要吗？你给我2分钟，看下格式，我就立马可以记起来，给你写出来。
but， 还是，我的错。对简历，没有百分百的熟悉。
所以，还有好好看看github自己写的代码，真的，会有人问，让你重写的。
下面的问题，我已经慌了。
然后接着问了一个MVC，恰恰也是我第二个project采用的思想。
我也说，我用过。

给我一个string
"Dehua Liu, 101 Guandong Road, 12034, Coke"
firstname, lastname, address, postcode, favouriate drink
然后扫描这个字符串，形成这样一个结构。
这很简单，我就写了这么一个类，然后在构造函数里面，实现这些。

当时他就接着问了，
先问我 MVC的基本概念。
https://en.wikipedia.org/wiki/Model–view–controller
https://developer.chrome.com/apps/app_frameworks
(记住， controller 同时还需要负责将用户数据写入db)
问我这个是 model 还是 controller
我当时还没有从json的余波里解放出来，人很失落，脑子短路，想错了，说是 controller
哎，怎么可能是controller 呢。。。
他问我确定吗，我说确定。
然后他跟我说，你在controller里面检查输入输出吧。
我说是的。
然后后来我想了下，改成了model。这的确是model啊。一个人的model。
controller 从view拿来数据，string，传给model
为什么我会答错。
然后我改了。
他说你又觉得他是model了啊。
估计觉得我是傻逼吧。。。水比。
然后问我，为什么在model里面要检查输入。

不想再回忆了。整个过程，我太痛苦了。对面主要是一个阿三在提问，虽然题目没有太难。但真的，细节东西我忘了。我最近写的占据了我的大脑。那些json细节，都记不清了。
还是我，不够了解自己的简历吧。
还有，MVC，我的理解还不够深刻。
这次要好好补习下。
再好好面对下次。

最近找实习，真的感觉跟找全职差不多了。。。

总结先到此为止。
加油。

Anyway, Good luck, Richardo!