Interview Experience Part 1

http://www.jianshu.com/p/3b7887f6a3c9
题目是， 设计题目
建立一个王朝。
王朝只有一个皇帝，
皇帝有很多儿子，每个儿子又可以有很多儿子。
这样，我就想起了一棵多叉树。
然后，每个人都会死去的。
下面实现三个函数。

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, 等等。
数据结构就是我的刀剑，我要用好他们

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

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

http://altynai.me/2014/06/google-interview/

开场问了些简历里面的东西，以之前做过什么？，某个项目中遇到的最大难题是什么？怎么解决的？等类似方向的问题为主，之前也有为这个做些准备，不过感觉没回答好，主要还是表达能力上的问题。

然后就直接在doc里做题了，这轮面了两题，第一题是TC Div.2 250pt级别的题，一个简单的char array[]处理，从右往左线性的扫描就够了。但是由于当时太紧张了，挂了电话之后才发现把面试官给的一个题目条件忘记了，回想到面试官在提示的时候自己愣是在找bug，而不是重新审视题目的本意。

第二题是实现一个迭代器，前序遍历一个二叉树。一开始扯了一个暴力且最简单的方法，直接遍历树，存结果，再线性扫描。然后面试官当然不满意，提示优化，所以扯了一个手动栈模拟递归的方法，由于时间紧，也来不及写代码，只是大致说了一下思路，不过感觉自己当时也不是表达的很好。具体思路和代码可以参考http://coolshell.cn/articles/9886.html。

第一题是给定一个字符集S，有一个映射函数f(x)=y x,y属于S，让你实现一个函数g(y)=x x,y属于S。首先给了一个暴力枚举的做法：对于每个y，枚举集合S，找到一个f(x)=y即可。然后提醒优化，就加开了一个数组，做查询时候的cache。

第二题是个循序渐进的题目，一开始要求实现一个10进制->n进制(2<=n<=16)的转化函数，然后实现一个n进制->10进制(2<=n<=16)的转化函数，最后结合以上两个函数，整合成一个n进制->m进制(2<=n,m<=16)的综合函数，写完之后讨论了一些细节问题，之后就算是结束了这轮面试。