新鲜GG onsite挂经

上周的GG onsite,题目不难,但是楼主没做好,上来发发面经攒点人品。

一个image以2D byte array的方式储存(byte[][] image),每个象素点是1个bit(0或1)。现在要求每行的象素点做对称翻转。我的做法是先把每行的byte对称翻转,然后再把每个byte各自翻转。
如其中一行byte[] row = {11010100,00101010} 第一步{00101010,11010100} 第二步{01010100,00101011} 时间复杂度是O(mn8), follow up如何优化时间,应该是在翻转每个byte上把O(8)的复杂度降低,但是不要求使用复杂的位运算。
2. game of life变形,一个2D matrix只有0或1,要求把所有上下左右被1包围的1变成0。先给了个space O(n^2)暴力解,然后让优化空间,就说了用两个bit存放前后state的方法,space变O(1),但面试官说假设每个格子只有一个bit空间怎么办?答三行三行做,他说行。
3. 面经题,设计一个interface实现有timestamp的hashmap,即(key,value,time),写出get和 put方法。过期的key value pair不能被get。
4. 面经题,给一个国王家的family tree (n-ary tree),王位继承是先传国王最年长的儿子,假如最年长儿子死了,就传给死儿子最年长的儿子。。。如果这些人都不存在,再考虑国王次年长的儿子,以此类推。要求设计这样一棵树,死掉的人不要求删除,实现birth()和输出王位继承顺序的method(死掉的人不在继承顺序结果里)。

楼主送HC 了吗

HR没提,估计没有。

楼主低调啊,我觉得答得很好,offer在路上。

HR已经打电话把我拒了

为何会这样…哪里出了问题

都是面筋啊,楼主没好好准备

没太理解对称翻转,楼主能clarify一下对称翻转的第一步和第二步分别是如何得到的么?

就是每行的像素点(一串0和1)相对于它们的中点对换,比如原来是11110000,翻转后是00001111

补充内容 (2018-4-25 08:11):
因为每行的表示是一个byte array,所以第一步是把所有的byte做上述翻转,翻转后的byte array再对每个byte(包含8个像素点)做同样的操作,这样你就把一行的像素点都对称翻转过来了。

你说的对,我被问到的时候都知道是面筋题,可惜的是准备的时候没仔细把每道写一遍,所以当场容易出小bug,被面试官揪出来了