处女面@CDK Global
666022
今天迎来了处女面，Java老师给推的 SE and Data Science Intern。公司不太了解，好像是专门给汽车dealer写网站的，零几年刚上市，员工万把人的不大不小公司。不过他们西雅图分部的地理位置真不错，窗外就是港湾和SeaHawks体育场，加上大晴天，给我看呆了。
之前有两位同学已经面过，问的都是list和tree相关的题，难度不大，我就把leetcode上list和tree的都刷了两遍就去了。面试一开始什么behavior问题也没问，拿了我的简历看了一遍说：哦，你学过Data Structure啊？我说没上过课，都是自学的。“Well, let's design some structures”，当时一下就蒙圈了，说好的算法题呢，说好的leetcode原题呢。。硬着头皮做吧。。{:4_105:}
第一问简单，用list存1milllion个customer信息，根据customerID查的话复杂度是1million/2，如何优化，答的是设计hashmap，key是0到99,999，value是list，每次用ID%100,000，找相应的key，再进list查，复杂度1million/100,000。
第二问是客户不知道ID，要用名字查，怎么办？答得是建一个数组，存A到Z，每一个字母对应着另一个数组A到Z，这样复杂度是log。
第三问是客户输入名字检索信息时不按规矩来，比如Joe Smith，他有可能输入Jo，或者Smi，甚至oeSmi，如果不考虑空间，怎么使时间最优？想了半天没憋出来，就简化了一下，规定每次只能输入三个连续字符，像Joe, Smi, oeS，答建一个数组，内容是AAA到ZZZ，这样要查所有可能结果复杂度为1，但是当时感觉这题没答好，就主动改进，说可以把AAA到ZZZ按照26进制转换成数字，这样比存字符要好一些。
第四问要求动态，比如客户输入J，你得显示一共有100000个结果，再输入Jo，你得显示有50000结果，类似的，直到找到结果。而且客户不会都从头输入，有可能从m开始输。。当时懵了3分钟，问了一句说没太理解问题，能不能详细点，结果面试官可能听错了，说“You mean use Set? That's great!"，给我下了一跳。。赶紧接着说set。。其实现在也不太明白他那问题怎么解决，但是他好像很开心。。看来英语口语不好也有好处啊。。。{:4_113:}
总之处女面感觉略失败，刷的题也没用上，也看出来自己还是比较菜，还得加油啊！
补充内容 (2015-12-6 02:11):
忘了说了，全程没写代码，一直在白板上画结构图，各种设计，应该算是非主流的一次面试吧。。
之前有两位同学已经面过，问的都是list和tree相关的题，难度不大，我就把leetcode上list和tree的都刷了两遍就去了。面试一开始什么behavior问题也没问，拿了我的简历看了一遍说：哦，你学过Data Structure啊？我说没上过课，都是自学的。“Well, let's design some structures”，当时一下就蒙圈了，说好的算法题呢，说好的leetcode原题呢。。硬着头皮做吧。。{:4_105:}
第一问简单，用list存1milllion个customer信息，根据customerID查的话复杂度是1million/2，如何优化，答的是设计hashmap，key是0到99,999，value是list，每次用ID%100,000，找相应的key，再进list查，复杂度1million/100,000。
第二问是客户不知道ID，要用名字查，怎么办？答得是建一个数组，存A到Z，每一个字母对应着另一个数组A到Z，这样复杂度是log。
第三问是客户输入名字检索信息时不按规矩来，比如Joe Smith，他有可能输入Jo，或者Smi，甚至oeSmi，如果不考虑空间，怎么使时间最优？想了半天没憋出来，就简化了一下，规定每次只能输入三个连续字符，像Joe, Smi, oeS，答建一个数组，内容是AAA到ZZZ，这样要查所有可能结果复杂度为1，但是当时感觉这题没答好，就主动改进，说可以把AAA到ZZZ按照26进制转换成数字，这样比存字符要好一些。
第四问要求动态，比如客户输入J，你得显示一共有100000个结果，再输入Jo，你得显示有50000结果，类似的，直到找到结果。而且客户不会都从头输入，有可能从m开始输。。当时懵了3分钟，问了一句说没太理解问题，能不能详细点，结果面试官可能听错了，说“You mean use Set? That's great!"，给我下了一跳。。赶紧接着说set。。其实现在也不太明白他那问题怎么解决，但是他好像很开心。。看来英语口语不好也有好处啊。。。{:4_113:}
总之处女面感觉略失败，刷的题也没用上，也看出来自己还是比较菜，还得加油啊！
补充内容 (2015-12-6 02:11):
忘了说了，全程没写代码，一直在白板上画结构图，各种设计，应该算是非主流的一次面试吧。。
- 3