一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2783|回复: 23
收起左侧

Linkedin实习两轮电面

[复制链接] |试试Instant~ |关注本帖
chopinzwz 发表于 2015-12-5 05:16:30 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Linkedin - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
第一轮面了两道LeetCode原题。第一题是Repeated DNA Sequence,貌似面试官一定要最优解法,也就是必须encoding,并且是1-A, 2-C, 3-G, 4-T这样,顺便考了下bit操作。他还反复的问为什么要用HashMap不用array,HashMap会不会blow up,以及一些基本概念比如Java int的范围等等。第二题就是level order traversal,正着反着都写了一遍。
两天后通知进入第二轮,然后就是噩梦的开始。第二轮是一个印度大姐,上来直接开始做题,她出了一道好像是她自己刚刚想出的题... 设计一个generic class,要求支持add(T), remove(T), randomRemove(T)三个操作,并且必须保证都是O(1)。比如说add(cat), add(dog), add(pig), add(cat), remove(cat), remove(dog)等等,她还特意说必须要考虑重复,也就是说删掉一个cat后另一个cat必须还在,而且randomRemove()必须保证所有元素被删掉的概率均等。

我当时觉得这个有点像LeetCode上的LRU cache,就说准备用HashMap + Double linked list。HashMap存(element + arrayList of the double linked list node),之所以arrayList是因为要考虑重复,要double linked list是要保证单位时间能删除。她让我解释为什么这样做,然后说你可以开始写了。我把add和delete写好,期间被她各种challenge,最后等到写randomRemove()的时候,我突然意识到好像并不能保证O(1)了...因为生成一个随机数,也没办法单位时间定位到该元素,除非再加一个HashMap。

这时候大姐开始放大招了,说你已经用了两个data structure,不能用第三个了。我说can you give me a hint?她说you should think about why you want to use linked list in the first place, that’s my hint… 我心想这不等于没说?然后她说I’m actually questioning your whole data structure design…我汗。我想了下说是要用两个HashMap?她说对。可是这时候就剩不到十分钟了。我赶紧跟她说应该怎么做,边说边写,但是也还是没写完就到时间了。所以这题应该是用第一个HashMap放index + 元素内容,重复的元素要分开放,第二个HashMap放元素内容+arrayList of indexes,把重复元素的indexes放在一起。所以上面的例子就应该是HashMap1 : (1, cat), (2, dog), (3, pig), (4, cat), HashMap2: (cat, (1, 4)), (dog, 2), (pig, 3)这样。add, remove很容易O(1),randomRemove()时生成一个1-4的随机数,比如2,然后从第一个map里找2对应的是dog,然后从第二个HashMap里找到dog,把dog删掉。但有一个小问题我觉得她自己也没想清楚,就是如果有很多dog,那么dog的list很长,并不能保证O(1)找到要删的那个dog的index吧?。。另外还有一个trick,就是删掉dog后,要用第一个map中的最后一个元素去填补中间的gap,否则下次如果再生成随机数2,就找不到元素了。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
果然两天后被拒了,毕竟代码都没写完。。祝版上的朋友们好运!

评分

2

查看全部评分

本帖被以下淘专辑推荐:

alphard 发表于 2015-12-7 21:29:22 | 显示全部楼层
这个题好难 楼主面的是system track。。。吧。。。。
回复 支持 1 反对 0

使用道具 举报

nemoleoliu 发表于 2015-12-6 12:18:31 | 显示全部楼层
第二轮 为啥要用两个HashMap? 一个String数组加上一个<String, LinkedList<Integer>> 的map不就够了
add操作:数组添加, 然后map添加 O(1)
remove操作: map获取到linkedlist的head index 然后 将这个index和数组当前最后一个element swap一下位置,并且更新一下最后一个元素在map中的index信息
randomremove操作: 随机数生成,先从数组找到label,然后去map找到linkedlist 同样是取head index 因为取哪一个都一样,所以不需要一定是要随机数的那个 然后和remove操作一样.1point3acres缃

关于如何更新swap过后元素的index数值,没想到特别好的方法,只有顺序查找
回复 支持 1 反对 0

使用道具 举报

2015fallcser 发表于 2015-12-5 13:18:41 | 显示全部楼层
patpat楼主  大姐有点凶猛
最后他和你讨论了么?. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

 楼主| chopinzwz 发表于 2015-12-6 12:31:53 | 显示全部楼层
2015fallcser 发表于 2015-12-5 13:18
patpat楼主  大姐有点凶猛
最后他和你讨论了么?

没讨论什么... 就是让我写了几个test cases
回复 支持 反对

使用道具 举报

 楼主| chopinzwz 发表于 2015-12-6 12:34:50 | 显示全部楼层
nemoleoliu 发表于 2015-12-6 12:18
第二轮 为啥要用两个HashMap? 一个String数组加上一个 的map不就够了
add操作:数组添加, 然后map添加 O ...

不用数组是因为预先不知道有多少元素啊,不过如果dynamic allocation然后amortized cost还是O(1),我觉得可以但不知道面试官怎么想...
回复 支持 反对

使用道具 举报

tiger0572 发表于 2015-12-6 12:35:42 | 显示全部楼层
楼主碰到的怎么都是这么奇怪的题。。。
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-12-6 13:40:25 | 显示全部楼层
nemoleoliu 发表于 2015-12-6 12:18
第二轮 为啥要用两个HashMap? 一个String数组加上一个 的map不就够了. from: 1point3acres.com/bbs
add操作:数组添加, 然后map添加 O ...
. more info on 1point3acres.com
感觉只需要一个普通的list去存所有元素的index
你现在这样并不能保证randomremove对所有的元素等概率 只能保证distinct的元素等概率
回复 支持 反对

使用道具 举报

beefcurtain5 发表于 2015-12-6 14:15:09 | 显示全部楼层
2015fallcser 发表于 2015-12-6 13:40
感觉只需要一个普通的list去存所有元素的index
你现在这样并不能保证randomremove对所有的元素等概率 只 ...
. from: 1point3acres.com/bbs
http://stackoverflow.com/questio ... m-element-all-at-o1

LZ的答案是getrandom from the total number of elements。。 所以试对所有elements
回复 支持 反对

使用道具 举报

nemoleoliu 发表于 2015-12-7 01:11:52 | 显示全部楼层
2015fallcser 发表于 2015-12-6 13:40. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
感觉只需要一个普通的list去存所有元素的index
你现在这样并不能保证randomremove对所有的元素等概率 只 ...

randomremove对所有元素是等概率的 因为取得随机数范围是0-总的元素个数 , 那么我当我知道要删除的元素后 我只要删除的是这个元素 删除第几个是没有影响的
回复 支持 反对

使用道具 举报

alphard 发表于 2015-12-7 23:41:33 | 显示全部楼层
关于楼主最后说的说的removeRandom,十分好奇这样如何实现O(1)delete(T)删除. 1point 3acres 璁哄潧
没有双向链表这两者好像没法同时O(1)实现

补充内容 (2015-12-7 23:44):
噫 看错了 当我没说。。。。。。
回复 支持 反对

使用道具 举报

wait4it 发表于 2015-12-8 05:32:48 | 显示全部楼层
楼主这题好像面经里面也出现过啊。你去搜搜看应该找得到原题,
回复 支持 反对

使用道具 举报

 楼主| chopinzwz 发表于 2015-12-8 08:49:58 | 显示全部楼层
alphard 发表于 2015-12-7 21:29. from: 1point3acres.com/bbs
这个题好难 楼主面的是system track。。。吧。。。。

不是。。就是software engineer intern
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2015-12-9 11:22:29 | 显示全部楼层
nemoleoliu 发表于 2015-12-6 12:18
第二轮 为啥要用两个HashMap? 一个String数组加上一个 的map不就够了.1point3acres缃
add操作:数组添加, 然后map添加 O ...

我想到的是Map<String, HashSet<Integer>> 这样remove random element的index:用Math.random() * array.length()拿到random的index,然后从map的HashSet里remove是O(1)的操作,如果map的value是LinkedList<Integer> 的话,因为LinkedList的inner implementation是doubly linked list,你还是要traverse才能找到你想要删除的index

my two cents.
回复 支持 反对

使用道具 举报

minniedisney 发表于 2016-1-8 10:17:49 | 显示全部楼层
楼主两个hashmap的方法remove的时候怎么实现O(1)的呢?
remove了之后也要更新两个map里面的信息吧,比如删掉dog, 应该把第一个map里最后一个元素cat更新为(2, cat), 第二个map里cat对应的arraylist变为(1,2),不然randomremove会出问题的吧。
回复 支持 反对

使用道具 举报

minniedisney 发表于 2016-1-8 14:29:39 | 显示全部楼层
minniedisney 发表于 2016-1-8 10:17
楼主两个hashmap的方法remove的时候怎么实现O(1)的呢?
remove了之后也要更新两个map里面的信息吧,比如删 ...

嗷。。。好像可以O(1), randomremove也可以,因为没必要删特定index的,只要删掉最后一个dog就好。。。
回复 支持 反对

使用道具 举报

minniedisney 发表于 2016-1-8 14:40:53 | 显示全部楼层
minniedisney 发表于 2016-1-8 14:29
嗷。。。好像可以O(1), randomremove也可以,因为没必要删特定index的,只要删掉最后一个dog就好。。。

lookup确实不能达到O(1),我想她说的意思应该是average是O(1)吧。。。。
回复 支持 反对

使用道具 举报

huoshankou 发表于 2016-1-10 09:39:42 | 显示全部楼层
有一个问题不理解。比如我add 了,cat, dog, cat, dog,cat, sheep. remove(cat)是要remove最后那个cat吗, 还是可以随机remove 任何一个cat
回复 支持 反对

使用道具 举报

zhenggao1986 发表于 2016-6-5 14:23:27 | 显示全部楼层
class MyRandomMap<T> {
        private HashMap<T, ArrayList<Integer>> hashMap = new HashMap<T, ArrayList<Integer>>();
        private ArrayList<T> array;
       
        public void add(T data) { // O(1)
                array.add(data);
                ArrayList<Integer> indices;
                if (!hashMap.containsKey(data)) indices = new ArrayList<Integer>();
                else indices = hashMap.get(data);
                indices.add(array.size() - 1);
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        public void remove(T data) { // O(1)
                if (!hashMap.containsKey(data)) return;
                ArrayList<Integer> indices = hashMap.get(data);
                int index = indices.get(indices.size() - 1);
                if (indices.size() == 1) hashMap.remove(data);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                else indices.remove(indices.size() - 1); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                array.set(index, array.get(array.size() - 1));.1point3acres缃
                array.remove(array.size() - 1);
        }

        public T getRandomData() { // O(1)
                int rand = new Random().nextInt(array.size());
                return array.get(rand);
        }
}

补充内容 (2016-6-5 14:29):
class MyRandomMap<T> {
        private HashMap<T, ArrayList<Integer>> hashMap = new HashMap<T, ArrayList<Integer>>();
        private ArrayList<T> array = new ArrayList<T>();-google 1point3acres
       
        public void add(T data) { // O(1)...
回复 支持 反对

使用道具 举报

zhenggao1986 发表于 2016-6-5 14:29:43 | 显示全部楼层
zhenggao1986 发表于 2016-6-5 14:23.鐣欏璁哄潧-涓浜-涓夊垎鍦
class MyRandomMap {
        private HashMap hashMap = new HashMap();
        private ArrayList array;

class MyRandomMap<T> {
        private HashMap<T, ArrayList<Integer>> hashMap = new HashMap<T, ArrayList<Integer>>();
        private ArrayList<T> array = new ArrayList<T>();. 1point 3acres 璁哄潧
       
        public void add(T data) { // O(1)
                array.add(data);
                ArrayList<Integer> indices;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                if (!hashMap.containsKey(data)) indices = new ArrayList<Integer>();
                else indices = hashMap.get(data);
                indices.add(array.size() - 1);
        }

        public void remove(T data) { // O(1)
                if (!hashMap.containsKey(data)) return;
                ArrayList<Integer> indices = hashMap.get(data);
                int index = indices.get(indices.size() - 1);.1point3acres缃
                if (indices.size() == 1) hashMap.remove(data);
                else indices.remove(indices.size() - 1);
                T tmp = array.get(array.size() - 1);
                indices = hashMap.get(tmp);
                indices.remove(indice.size() - 1);
                indices.add(index); // 这里好像还是不对,第二次再删掉tmp就不对了
                array.set(index, tmp);
                array.remove(array.size() - 1);.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }.鐣欏璁哄潧-涓浜-涓夊垎鍦

        public T getRandomData() { // O(1)
                int rand = new Random().nextInt(array.size());
                return array.get(rand);.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
}
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 20:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表