一亩三分地论坛

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

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

Indeed onsite面经

[复制链接] |试试Instant~ |关注本帖
谎言之躯 发表于 2015-11-20 06:07:40 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Indeed - 校园招聘会 - Onsite |Failfresh grad应届毕业生

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

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

x
去indeed onsite的男生(特指男生!)不要抱太大希望,这公司每周两场onsite,每场16个人,这公司一共能招多少人?我那一场不乏一堆MIT的本土学生。
第一题git version,从新到旧扫描,就是有向图的BFS,follow up是给出图里的两个源节点,找距离这两个原点的最近的公共节点,分别从这两个节点BFS就行。
第二题,n个非常长的有序数组,找出其中出现了至少k次的数字,用heap,用heap,用heap!重要的事情说三遍。
第三题,linkedelist中的每个节点里存了个固定长度的数组,但是数组未必满。进行插入操作的时候,如果要插入的节点的数组满了,可以考虑新建个节点插当前节点的数组的溢出的元素。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
上机题还是地里说的那个。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

2

查看全部评分

ergee 发表于 2015-11-20 11:13:59 | 显示全部楼层
楼主,我不太明白第二题为什么要用heap,假设有m个数组,每个数组中有n个不同元素,用heap的话,就是那个类似merge k sorted list那题的方法,每个元素都要往数组里插入,时间复杂度是O(mnlog(m))
如果把所有元素无脑往hashmap里放,key是元素,val是次数,那么全部插入的时间复杂度是O(mn),再便利一遍hashmap取出大于k次的元素,时间复杂度仍然是O(mn)
问下我这样的分析对么?谢谢!
回复 支持 0 反对 1

使用道具 举报

yjfox 发表于 2015-11-20 07:41:20 | 显示全部楼层
地里说的那个是什么?上机题

还有,lz觉得跪哪儿?
回复 支持 反对

使用道具 举报

 楼主| 谎言之躯 发表于 2015-11-20 09:10:07 | 显示全部楼层
如果不能在瞬间完美秒杀面试题,就是跪。
回复 支持 反对

使用道具 举报

 楼主| 谎言之躯 发表于 2015-11-20 09:10:56 | 显示全部楼层
yjfox 发表于 2015-11-20 07:41. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
地里说的那个是什么?上机题

还有,lz觉得跪哪儿?

地里说的那个query的上机题。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-11-20 09:38:56 来自手机 | 显示全部楼层
第二题只需要从头扫到尾,检查i+k是不是一样的就行了吧?
回复 支持 反对

使用道具 举报

 楼主| 谎言之躯 发表于 2015-11-20 09:58:05 | 显示全部楼层
bobzhang2004 发表于 2015-11-20 09:38. from: 1point3acres.com/bbs
第二题只需要从头扫到尾,检查i+k是不是一样的就行了吧?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
k次指的是在k个数组中出现。如果在同一个数组中出现多次的数字,只算一次。面试时给的是stream,相当于数组。
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-11-20 11:36:34 | 显示全部楼层
请问lz能不能详细说说第二题怎么做的 谢谢
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-12-9 14:20:49 | 显示全部楼层
楼主第二题怎么做的?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-12-9 15:32:02 | 显示全部楼层
blactangeri 发表于 2015-11-20 11:36
请问lz能不能详细说说第二题怎么做的 谢谢

class Solution {
        class Node {
                int val;
                Iterator<Integer> ite;. Waral 鍗氬鏈夋洿澶氭枃绔,
                public Node(Iterator<Integer> ite) {
                        this.ite = ite;
                        this.val = ite.next();
                }
        }
       
        public List<Integer> findMoreThanKTimes(List<List<Integer>> list, int k) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                List<Integer> res = new ArrayList<>();
                PriorityQueue<Node> minHeap = new PriorityQueue<>(new Comparator<Node>(){
                        public int compare(Node a, Node b) {
                                return a.val - b.val;
                        }
                });
                for (int i = 0; i < list.size(); i++) {
                        Iterator<Integer> ite = list.get(i).iterator();.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        if (ite.hasNext()) {
                                minHeap.add(new Node(ite));
                        }
.1point3acres缃                }. 1point3acres.com/bbs
                if (minHeap.isEmpty()) {
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷                        return res;
                }
                Node cur = minHeap.poll();.1point3acres缃
                int curVal = cur.val, cnt = 1;-google 1point3acres
                while (cur.ite.hasNext()) {
                        int val = cur.ite.next();
                        if (val == curVal) {
                                continue;
. From 1point 3acres bbs                        }
                        cur.val = val;. 1point3acres.com/bbs
                        minHeap.add(cur);. From 1point 3acres bbs
                        break;
                }
                while (!minHeap.isEmpty()) {
                        cur = minHeap.peek();
                        if (cur.val == curVal) {
                                cnt++;. From 1point 3acres bbs
                        }
                        else {
                                if (cnt >= k) {
                                        res.add(curVal);
                                }
                                if (minHeap.size() < k) {
                                        break;
                                }
                                curVal = cur.val;
                                cnt = 1;
                        }
                        cur = minHeap.poll();
                        while (cur.ite.hasNext()) {
                                int val = cur.ite.next();
                                if (val == curVal) {. 1point 3acres 璁哄潧
                                        continue;
                                }
                                cur.val = val;
                                minHeap.add(cur);
                                break;.1point3acres缃
                        }
                }
                if (cnt >= k) {. 1point3acres.com/bbs
                        res.add(curVal);
                }
                return res;
        }
}
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-12-9 22:28:38 | 显示全部楼层
hj867955629 发表于 2015-12-9 15:32
class Solution {. From 1point 3acres bbs
        class Node {
                int val;

厉害。。。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-12-10 10:58:12 | 显示全部楼层

if (minHeap.size() < k) {
        break;
}
if (cnt >= k) {
        res.add(curVal);
}

没有啦,有个bug,如果提前结束的话,必须要交换这两个语句,否则最后一个数字重复了。。
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-12-10 12:22:24 | 显示全部楼层
hj867955629 发表于 2015-12-10 10:58. more info on 1point3acres.com
if (minHeap.size() < k) {
        break;
. visit 1point3acres.com for more.}

为什么重复
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-12-10 21:35:35 | 显示全部楼层
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
因为如果minheap size小于k,这个地方add了一次,最后又add了一次。。。最后add一次是因为只有当新的value出现时才去比较cnt,所以最后需要加一下add
回复 支持 反对

使用道具 举报

faye_roll 发表于 2015-12-30 12:46:55 | 显示全部楼层
请问第三题,插入的是value么? 还有,如果插入的节点的数组满了,是遍历他的next的节点上的数组并且插入到这个数组里,还是新建一个新的节点,然后指向这个新的节点?

补充内容 (2015-12-30 00:48):
就是说,如果满了,就沿着这个linkedlist 找后续的节点,如果后续节点的array没有满,就插入这个value
回复 支持 反对

使用道具 举报

 楼主| 谎言之躯 发表于 2015-12-30 23:36:32 | 显示全部楼层
faye_roll 发表于 2015-12-30 12:46
请问第三题,插入的是value么? 还有,如果插入的节点的数组满了,是遍历他的next的节点上的数组并且插入到 ...

新建个节点要好一些,这是当时面试官的建议。
回复 支持 反对

使用道具 举报

shawn.chris 发表于 2016-1-1 07:32:38 | 显示全部楼层
我去,这些题确实有难度……
回复 支持 反对

使用道具 举报

haoxuango 发表于 2016-1-4 11:01:58 | 显示全部楼层
为啥特指男生、。。。。。。。。。。。。
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-2-11 04:29:27 | 显示全部楼层
请问楼主第一题,node的数据结构有parent吗,谢谢
回复 支持 反对

使用道具 举报

 楼主| 谎言之躯 发表于 2016-2-11 09:22:54 | 显示全部楼层
ninacc 发表于 2016-2-11 04:29
请问楼主第一题,node的数据结构有parent吗,谢谢

没有。就是一个普通的图。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 09:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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