很搞笑。纯属写实，如有雷同，不胜荣幸。
非常镇定的上完了周二下午的课才慢慢腾腾的坐车回家，然后开去机场。将近8小时的上上下下颠簸，落地在San Jose机场。折腾的租到车的时候已然11点半了。租车的黑人奶奶很瘦扎着一个与年龄的50进制表示比较相符的小辫子，带着一副学生眼睛，慢慢语速跟我说，是不是去面试啊，费用G公司全包了的。我一连黑线，说是。快步离开。专门带着郑宇的GPS来的，来了却发现G公司很发扬风格，在条款里口口声声说没有GPS的车里赫然摆着一个GPS（还是钉上的，真的不是忘记卸了）。
宾馆房间很大，房价数字也很大，床..也很大，真浪费啊。而且还有这么多浴巾。得多洗几次澡。一路还盘算着要不要加钱开网，发现G公司非常发扬风格，网络很快很免费。泡了澡，看了CareerCup上的OO Design/Software Design/Testing三章的Solution，信心大增，然后睡觉。
第二天开车去campus, 10分钟的路程。提前了半个小时到达，没好意思拿着书坐在人家lobby，只好猛看小说。原来的Recruiter没出现。新的recruiter了解之后发现这是今天所有跟我打交道的人里面学历最好的一个。发现了很多轮子作成Chrome样子的自行车，被介绍说是hop来在campus里面穿梭用的。Recruiter送了一个包给我，靠，还是Ogio的。上次买他家包的时候那个咬牙啊。
带进了一间办公室，说technician会来轮你。就在这儿等着就好。一个饭前，三个饭后。好好吃饭，这种事情很费体力。technician 1 迟到了。中国人。后来发现他并不是最后一个中国人，但是是唯一一个正经说英语的。自我介绍和扯淡项目经历之后，开始正题。
Design an in-memory Cache Library, providing APIs to developers, using LRU strategy. Maximum of entry number is provided when constructing.
有了昨晚上的“理论”和上次被Amazon面试时候的推敲，这题目变得很水。class写出来之后他比较满意。之后是实现checkInCache和addEntry。
我一边和他讲一边写，对这个函数他表示满意。另一个函数的第一个实现也很smooth。这时候他指出一个bug，说hashmap没有维护好。
我看了一下，果然.改完之后，那个哥终于漏出了笑泳。
哥说，现在我们extend一下addEntry的功能，你的use case是说没找到的时候才能调用addEntry，但是也许有的时候找到了也可以调用，比如想要update的时候。我说哥你说的对，我设计接口时候怎么没想到呢。于是开始实现新版本的addEntry.顺手把上一个实现也改成return 1;这样可以标记到底是哪一种情况返回的。哥说你这个重复劳动了啊。是不是能并在一起，我想了一下，说是可以的。其实很多代码都一样。
哥的眉头舒展开了。第一个人结束。
回问的东西都忘了。
中午吃饭很搞笑。大叔先跟我说别紧张，我不打分，就是单纯的带你吃饭。领到了最近的中国食堂，一股麻辣烫的味道，靠，那个馋啊！！！！！结果大叔说RSVP，撤退。然后去了另一个西餐的地方。餐不多，但是味道挺好的。绿牌子是low cal/fat的，黄色是mid，红色是high cal/fat的牛肉片，果断红色。
大叔最大的贡献出现在他离开前的最后5秒中。新来的interviewer说（中文），怎么是你，他说，怎么是你。后来解释说之前都是这两个人搭伙吃中午饭，结果现在一个陪我吃了一个接着面我。巨搞。奠定了屋子里面很尴尬的气氛。一个strange的事情是很多时候中国人和中国人之间能一本正经的说一天英文；另一个总是发生的事情是，中国人和中国人一旦开始说中文，就再也收不住了。
这个中文气氛一直持续到我离开Google的那一分钟.
下午的第一个，瘦的，居然是Christine的大学同学。二话不说开始闲扯八卦，刚才的当然是八卦期间八出来的。最后时间快到了，他说，我们写点东西吧。题目是：How to wrap a vector of vector into vector? Assume you do not need to construct it. Reading Order is v[0][0] ... v[0][k]... v[1][0]...v[1][1].... 类似。靠，又是设计，不过是iterator设计。
先list一下wrap之后需要实现的函数：size, empty, begin, end, iterator(++,*,->), clear .....
写到这儿哥急了，这妈一下午也写不完啊。他说那我们就集中精力写难的那个，就begin/end/iterator吧。
我很快就开始写了。哥开始了皱眉头。我也很疑惑，觉得很有问题。但是不得其妙。
最后数秒钟之后他提出问题： 返回出iterator之后如果++了岂不是按照normal iterator的规则来了？这个太对了。我就是一白痴。为什么会返回iterator呢。。。。扫清了思路全擦掉，开始重新实现靠谱版。
看来真是吃饭吃糊涂了。这个看起来总算开始靠谱了。此时，哥终于开心的舒展了眉头。又一个哥，pass了。
第三个interviewer给我的感觉是最好的。整个人有7分像张照宇。说话很温和。唯一的不同是头发有些花，似乎比我们大了有半轮。开场依然很简单，就是八卦。中文扯淡，这个人跟我的圈子倒是没有什么交集，所以扯的都是关于ACM的。有点怯的问我说，这个ACM Asian Site是什么概念，竞争程度怎么样？我讲了下，他表示你们ACM的人让面试官很有压力。
扯了很多其它的关于竞赛的东西。最后掏出一张刚刚打印的纸（后来gtalk上他告诉我这个题目是之前半小时从chefcode那个网站上直接random的一个median难度的题目，还给了我link）让我自己read,题目是这样的：
给一个N*M的int矩阵，一直青蛙以(i,j)作为起点，在以下规则满足的情况下可以跳跃到另一个格子里面：1. 右边的某个格子(i',j)上的值不小于(i,j)上的，可以跳到(i',j)2. 下方的某个格子(i,j')上的值不大于(i,j)上的，可以跳到(i,j')优化目标是，从任选的起点出发，经过最多格子的路径的长度，计数包含两端。讲题的整个过程都是中文。
第一时间就看错了题：误认为只能跳跃到相邻的格子，要给出N*M的算法，没开始说几句就被发现理解有问题。表示不要急，仔细看题。弄清楚状况之后秒出第二个simple解：N*M*(N+M)的解，定义了F[i,j]，顺序从左上开始。
说到这里果断被打断（丢人了），被告诉其实应该从右下开始，我还没反应过来，说应该是一样的，但是想了一会儿就放弃了，的确是从右下开始。
接着让我重述F[i,j]的定义，因为原先的有问题。这时候3方解完成。js想了一下，说，咱们是先实现出来还是先想improvement呢？我一愣，还有improvement啊,js接着讲那就先improve吧。
我继续愣，只有一个地方可能improve，就是(N+M)的地方，但是很无奈，我告诉他在算一个格子的过程中(N+M)个依赖格子都可能存在有意义的value,最终的value=max(values)+1。这个过程从信息的角度来讲(N+M)是下界了。他表示赞同，但是表示有低于线性的解。我想了一会儿，说，O(1)是不可能的，O(logN)是有希望的。唯一的希望在incremental。js立即表示强烈的同意。他“引诱”道：你想想什么ds是有logN的性质的。（我黑线|）我说，树，或者有序array。js立即又表示孺子可教，说就是树。我在他的引诱下冥顽不灵，表示没有能做这种事情的树。
说你先想想这件事情的本质是什么？这个我还是明白的，我说，问题的本质是我有一个pair的数组，我需要知道 key>MyKey的entry中value的最大值。这是一个讨厌的两个关键字的排序。我继续分析给他听，我说一般这种东西的处理办法是sort一维，二分之后去枚举第二维，sort是明显incremental的，后面的最优化目标不好做incremental。（后来发现我的论断还是很准的~）js表示思路很好。继续开始诱导：带有incremental sort性质的树是啥来着？我继续黑线，BST。心里觉得BST是不行的，但是还是顺着他的思路构造了一个包含右子树value最大值作为member的BST。
表示这个树无敌了。我非常之疑虑，但是已经不想找事了。大家谁也不说有问题，权当解出来了。（这个树的updating明显是很困难的。）
之后的过程就顺利了，问了我需要多少棵树，我讲同时keep min(M,N)+1棵在内存里面，总共需要建M+N棵。如何计算新的value，讲如果MyKey == root.key, 最大值 root.rightValueMax; 如果My > root.key, 去右边找； 如果MyKey < root.key, 先用 root.value更新最大值，然后去左边找。
这个过程的确是没问题，但是如何更新就是个大问题了，well，准确的说，是不平衡之后怎么rotate。不过他没有提我也就不管了。
接下来被要求给出之前3方解的code。coding....审视了一遍自以为没问题。告诉我说题目里面说向下必须变小，果然。准备去把 _max < f[i*n+k]+i 的小于号反过来，说没事没事，不用了，我们改题目~ 黑线。。。然后拍照留念。。。不是我，是code，每个code要是不抄下来就要拍下来提交上去。
之后的step是要我把BST的class给定义出来，这个比较简单。随手过关~
最后一个人长的非常像周跃。周跃和李远超的混合体。UNC的学长。所以一上来，恩.....开始八卦认识的人（黑线，每个人都是这样吗....)一阵中文八卦之后，发现半个小时过去了。这时候学长说，这样吧，我们还是得问几个题。
掏出几张大小不一格式不一的明显刚刚打印出来的什么题目。第一个题说按层打印树。队。秒。
第二个题说写一个x^y，x,y自然数，不超int。上黑板秒。他看了一会儿，没反应过来，问我怎么想的。我解释说把y做binary representation，比如 x^5 = x^101 = x^1 * x^ 100; 每次x *= x 的时候可以计算一个x^100...0，用y的二进制可以查到需不需要把这个x^100..0乘进去。那个哥表示不懂，但是让我跑一个x^5给他看。他惊奇的发现，果然是对的。然后还是不信，让我跑一个x^11，果然又是对的。很惊讶，问了复杂度，答O(logy)。对代码拍照留念。
第三题说n个数里面找前k大的数。最小堆，nLogk，秒了。第四题说一个行列都分别排好序的矩阵里面最大值在哪儿（黑线）怎么找一个值在不在矩阵里面。秒了。整个过程6-7分钟左右。该学长无语了。说没想到扯了这么长时间的蛋结果题还是不够用。有点尴尬。
晚上吃了，恩，Rok家的羊排，靠，真TMD的好吃。回去又泡了一次澡，中间专门为了用浴巾擦了一次，最后还专门把没来得及用的浴衣也用了下。终于刚刚好用掉了所有的东西。哦叶。
