12/03 Zillow onsite 面经

原帖地址:一亩三分地

昨天面的Zillow onsite,12点半开始面到4点半,连着四轮下来最后大脑基本死机了,完全思考不动。
Zillow的办公环境没得说,一共八层,在20多到30,各种海景玻璃幕墙,一进公司目光就被窗外美景死死勾住。

废话不多说,直接上题。面试官明确跟我说有题库,让我看到见过的题要讲= =。

第一轮:亚洲人,第一题写个AnagramsServer类,实现init(String[] dict)和getAnagrams(String s)两个方法。基本就是让你在init里面把字典里的词都存好,然后getAnagrams的时候可以把和s是anagram的都输出。init调用一次,get调用多次。第二题是写扫雷的OnClick方法,不用考虑UI相关的东西,输入是一个已经把雷埋好数字标好的board。他说主要想看的是你点了一个数字为0的格子时候如何把周围一圈都reveal然后如何继续把是0的格子给处理下去。
第二轮:美国人,第一题是要求用递归的方式来求一个string的长度,不允许用任何求length相关的libary method。我用substring的方式做出来了。写完后follow up是说我substring复杂度太高,因为要把所有char都copy一遍,所以要我想一个O(n)的。想死都没想出来最后他说你可以用exception的try-catch呀- -我当时就听醉了。第二题是给你一个graph每一个node都是一个facebook的user,然后找出这个user的两度关系以内所有和他last name一样的人的email address。= =这一题很简单但是我当时状态不是很好,BFS写出了两个很傻逼的bug,还都被他抓出来了,所以最后要挂估计就是挂这里了。
第三轮:美国人,第一题是给一个string找第一个unique character,我扫两次做的。follow up,给你的是一个iterator,只能顺着这个iterator走一遍,不允许存下来从头扫。我用linkedHashSet做的= =,估计他不懂这是什么鬼,现场去查了下发现确实可以,然后follow up就变成了让我讲讲怎么实现一个linkedHashSet。第二题就是leetcode的那个reverse word in string,我嘴贱说可以用split 然后倒着加,他就把input 换成了char[] 然后让我in-place做,然后说如果两个单词中有3个空格,也要reverse到另一边去。无论如何最后是顺利做出来了= =
第四轮:亚洲人,比较实际的数据处理题,给你一个log file,每一行都有一条记录,包括三个数据:访问时间,user id,访问的page id。然后让你找出访问次数最多的10组3个连续访问page。就是如果user A访问了page 1 2 3,这样 1 2 3 就算被访问了一次。不用考虑时间间隔所以我昨天访问1,今天2,后天3,也能算作连续访问page。我的做法是先用map统计了所有用户的按时间顺序排列好的访问page,然后三个三个加到另一个map里面去count,最后用minHeap找出前10个。follow up是如何优化空间,我那个时候大脑已经跪了,想了二十分钟想不出来就投降要hint了,然后经过提示就用大小为3的queue来存那连续三个page id,count完之后就扔掉第一个然后读第三个就好,不占用空间。

总体感觉就是题都很简单,但是连续面4个小时真的很吃力,状态一差就容易出低级bug。。。

有帮到的同学记得帮我加米哟~