初中打红警的时候有个地图叫『德州，奥斯汀』，还大概记得这是个双人小地图。没想到十年过去了真的来到了这个地图，哦不是这个城市，哦也不对，这个城乡结合部。由于已经接到了挂了的消息，可能这座城市比我描述的要繁华一些。但没啥用，面试就一次，抠就一个字。Indeed安排的住处是个双人间，意味着面试前一晚要随机的和另外一个人睡一个屋子（据说提前和HR说只要单间的话可能会被分配单间）。我运气很好遇到了个不错的来自哥大的中国人，晚上还聊了聊面经。如果遇上来自另一个国家的人，不仅面经没法看，要是对你有点儿想法，那一晚上别睡了，咖喱GayGay吧。
因为1月12号这一波面试，一共17，18个人。3个印度人，其他都是中国人。在面试前一天晚上indeed会邀请所有人去酒店旁边的一家饭店去吃饭。在饭桌上会派几个工程师和大家聊天，根据观察，聊天虽然对面试毫无影响，但是建议大家多聊聊，因为饭实在是难吃，不吃饭不聊天的话那只能干瞪眼了，或者去吃那个面包，能噎的你瞪眼。不吃面包？我保证其他东西更不适合被当成食物，除了给的两块儿披萨，其中一块儿放的太远够不着，但是我看同桌的印度女生就咬了一口就放下了，有勇士可以去试试。
为了让更多的人去吃这些饲料，indeed宣称你自己在外面吃的话是不给报销的。吃完之后HR会发你一个条，说第二天去公司的时候可以和室友一起打yellow cab去公司，把条给司机就可以了。
面试当天，早上大家自发拼车去公司，HR非常热情的带大家晃了一圈儿一楼的食堂，说大家敞开了随便吃。hua，大家纷纷敞开了，端了一盘子水果和面包。还没等着吃HR又说我们面试马上就要开始了你们没吃完的可以端上去吃。幸好我是被领着参观的时候一边走一边抓面包吃，至少我看到的大家都不好意思端盘子上楼，早饭就这么被废了。上楼之后，随机分成两组，一组去白板，一组上午就讲座+上机题。
抽中了上午上机，然后先听了四轮讲座，感觉自己像机一样被上了。内容无非是工作搜索上面Indeed强无敌，其他都是战五渣，一言不合全打趴。还自我标榜是职业版的Google，我就问了，都是做搜索，人家Google进中国叫谷歌，Yahoo进中国叫雅虎，Bing进中国叫必应，你丫敢进中国么？
然后就开始上机。Hackerrank的，还装模作样的显示是5道题，其实4道题都是文字叙述做法。之前已经押题是Resume version。就是一个简历系统（Profile system），实现update和query。我的办法是建个Profile class，里面成员变量有一个Profile id，和一个List，List里面是Map，因为它query的时候要根据版本号（version number），所以用list里面的index对应。每次更新的时候就把最新的map复制出来，修改再塞回List里面去。case一共是20个，超时了9个。而且近期应该都不会变了，连安排面试的人手都不够怎么可能去换上机题。
中午在早上的餐厅吃了顿午饭，也是随便吃。如果上午是白板的话那中午真的能敞开了吃。indeed也派了个工程师带我们进餐厅。其实说穿了我们只需要一张员工卡能出入餐厅就好了，大家都很勉强的尬聊。带我们的小伙子来自Ohio，看得出他对我很无奈，每次看向我想说点儿什么的时候都发现我嘴里塞着吃的对着他点头yes摇头no。时间一到就把我们送回大厅头也不回的走了。
下午白板，我突然意识到我可能被坑了。因为HR把我带到了4楼的一个讨论室，屋子里面没有白板，只有几支笔，而且办公区域都是recruiter，没有SDE，难怪每次面试官都会迟到很久。最坑的是没有白板，HR让我在玻璃上面写。。。写到这里的时候很想问一句其他人都是有白板的吧？
第一轮job id storage，一个和我年龄差不多的美国小伙迟到了10分钟。先问了问我的实习经历，刚好是我精心捏造的，对答如流，他还说自己没搞过iOS很好奇。但是我会读心术，他问我iOS开发中把Google map加载到软件上的东西叫什么，我回答SDK的那一瞬间从他眼睛里面看出他是在考我。问过之后上题。说有一堆job id，类型是long，一开始都是有效的，随着时间的推移，不断的expire，实现expire和isExpire两个方法。我内心暗爽，果然是面经。装模作样的说我们可以用set啊，立起来这个靶子之后马上自我反驳说这个方法空间太浪费了，我之前还练习了memory consumption这个词组。换bitset，用一个bit来存一个long，效果非常拔群。面试官在纸上还很认真的记录我的想法。容我讲清楚bit的方法之后，非常潇洒的看了一眼时间，刚刚过去10分钟左右。这时候面试官说，你这方法不错，但还得继续压缩。
！
鼠躯一震。
我知道这一问没有在面经上提过，那些面经只有『比较open的讨论』，『最重要的是怎么节省空间』，这不废话么。马上开始穷举，先强调了一下说bit这方法已经很压缩了，读他想法发现他是有其他办法的。然后继续说用trie吧，他居然假装和我热情讨论，只能被迫浪费一些时间聊了一下空间消耗然后发现trie不行。然后继续提出用bloom filter，这个会大幅减少空间消耗但是会出现一定程度上的错误，我又看出来这方法也跪了。心中暗叹一句卧槽，继续提出用范围来存，比如1，2，3，就存成1-3，但我紧接着提出这个是字符串类型内存消耗更大。这时候他提示如果一个job id失效了不需要准确的存这个id。我一想，那只能用范围了，但范围方法内存更大。继续提如果要继续压缩空间，那在时间上肯定会相应的慢。
时间来到还有10多分钟，他终于提出那个范围法可行，但是不能用字符串来存，要另外写一个结构。我终于懂他意思了，说可以写个Interval，但是worst case是一半的job id互相没有连接，那消耗极大。他说不考虑那种情况，行吧您都是对的。提出平均情况下会很节约空间，我立刻吹捧说这个类似快排，最坏情况比较差但是平均下来就更优一些。
所以，job id storage这道题，不是什么open讨论，讨论个球啊，就是藏的很深的一道merge interval。最后剩下10分钟在玻璃上疯狂的写，还写出来个bug，没有考虑到1-2，4-5下来了个3，就变成了1-5，在面试官的提醒下发现，然后立刻改，最后他说思路咱俩都清楚，时间到了也就不用再写了。总之，这题思路非常奇葩，完全是由面试官来决定，我以为已经展示出来各种思路，解释的也很清楚，唯一失策的地方就是讲范围这个思路的时候没有去看他的眼睛，错过了最关键的一次机会。最关键的是这方法比bitset更省内存？
第二轮也是个美国人和一个印度shadow，这时候迟到时间已经累积到15分钟了。面试官是破产版尼古拉斯凯奇。凯奇说他是做爬虫搜索的，还很详细的解释了一番。shadow居然也很有存在感的自我介绍了一番。大哥你是shadow啊，不是当做不存在么。我是光么就把你给照亮了？当时没想那么多，介绍完之后就14点25多一点儿了。凯奇立刻出题，Python validation。终于知道这道题的四个规则是什么了。规则1，第一行的code必须没有缩进，规则2，尾巴是冒号的行一定是control statement，规则3，control statement下面一行一定要有更多的缩进，规则4，同一个block里面的缩进一定要相同。
提出用stack来做，凯奇立刻问我为啥用stack呢，我就简单的讲了一下思路。回来在飞机上复盘的时候感觉失误在没有提出复杂度上优于brute force，只是讲了stack方法的思路可以搞定这道题，尤其是第四个规则。接着就开始写，边写边讲，讲自己每一行的代码都是组撒的，凯奇频频点头。写了三个玻璃之后，还自己跑了一遍test case，凯奇指着出题时候的case说跑一下这个，我像IDE一样逐行跑了一遍。凯奇拿起笔，写了个case说你看这个？
！
鼠躯一震。
先看了一眼时间，14点51。然后debug，凯奇看样子因为时间关系有些坐不住。我就直接照着case检查自己思路，三分钟不到的时间debug成功，把之前思路差错的地方说清楚，凯奇说你还有啥要问我的么。我当时刚刚debug成功，他突然这么一问我只能诚实回答说我刚做完题一下想不出问什么，而且也超时了一些，于是凯奇带着shadow逃窜了。
第三轮，Min Path from Top to Leaf。一位印度工程师迟到5分钟走了进来，还问我要不要休息什么的。脑抽了一下说去个卫生间吧。以为最后一轮像Google一样会放宽时间，然而我想太多了。这位印度大叔，就叫三叔吧，上来问了问我的course project，因为实习经历已经问过了。巧的是撞上了另外一个我静心捏造的项目，继续对答如流，不忘提了一句这个是udacity上面自学的。说我虽然是文科出身但我有很强的自学能力，对CS很有热情。说这句话的时候突然想起《裸婚时代》里面刘易阳求婚时候说『我虽然没车没房没钱，但是我有一颗陪你到老的心』。
可能三叔条件优越，并没有体会到我表达的意思。上题，就是拿到最短路径的面经题。出完题之后我先问了一句，问咱们这轮有延长么，你看这一折腾就半小时过去了，就剩半个小时了，三叔说4点结束。立刻给出DFS解法，后序遍历一遍拿到最短路径。写出了个小bug，及时纠正过来，三叔不以为然。接着问了问复杂度，改成DAG之后，这个方法复杂度是多少。是O(V!)，也是三叔给了点儿提示，不过真的就是一点儿。接下来说改成图之后怎么优化，时间这时候已经快不够了，提出用map来记录，避免重复计算。复杂度是O(V+E)，就被送下楼了。
因为之前团灭，这次去austin的心理压力极大，在德州除去面试时间整个人就说不出话来了。等了快一周接到电话说挂了，准备的还可以，发挥也不是很完美。被公司抠成这样，外加时差和心理压力。不过不管怎么说，必须感谢之前发面经的前辈，你们都是英雄。听说这一轮indeed发了很多offer，难度应该还是不大的，我挂的原因可能是因为本命年吧。
最后传一下之前准备的材料，是准备onsite过程中搜集的。代码比较乱，格式是统一的。挂了之后实在是不想再加工了，大概就那么个意思，我也只能给出来3道题目的清晰版本了。
备注一下，我是内推，还是没有职位的那种内推，刚好被HR捞了出来，然后电话OA电面Onsite一个不少，整个战线很长，叹气，挂掉很可惜，还有机会的战友们加油吧。
补充
第三轮，最短路径道题，面试官默认是所有cost都是正数，然后也没有环。所以N个点，每个都能连N-1，继续连N-2，所以复杂度是N！