Fall 18 我的 HCI 申请复盘与策略总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2328|回复: 32
收起左侧

[找工就业] Google 店面 一轮 过了

[复制链接] |试试Instant~ |关注本帖
我的人缘0
CharlesLeeSysu 发表于 2018-3-14 12:57:00 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

2018(1-3月)-[16]CS硕士+fresh grad 无实习/全职 - 内推|BayArea 码农类General全职@Googlefresh grad应届毕业生

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

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

x
店面一轮,题目是给一个double linked list,给一个subset of nodes in this list(白人小哥问我的有没有听过w~linked list,可能是画质原因,没反应过来,问了一句w~what,美国人这口音有毒)
double linked list: 1,2,3,4,5
subset : {1,2,5}
问这个subset的点能构成几个group(相连为一个group)
.本文原创自1point3acres论坛
解法在回答里面,求加米,没权限看不了面经很难过



评分

参与人数 14大米 +68 收起 理由
letranger + 1 给你点个赞!
tenpoint + 5 很有用的信息!
forgarden + 3 很有用的信息!
bambu + 3 给你点个赞!
sonofspring + 3 很有用的信息!
ScarlettQQ + 3 给你点个赞!
yiliaobailiao + 3 给你点个赞!
idatascience + 3 很有用的信息!
水浅王八多 + 3 给你点个赞!
Victor vshbd + 20 很有用的信息!
eejchen + 3 给你点个赞!
nooblike + 3 很有用的信息!
安如画 + 10 很有用的信息!
guolei329 + 5 zuidajiushiwudian

查看全部评分


上一篇:求问现在Oath (Yahoo) 怎么样?
下一篇:美国小厂remote实习 vs 国内大厂实习
我的人缘0
zyy_123 发表于 2018-3-14 15:11:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
为何要额外set 直接随便选一个然后在linkedlist里左右延伸 边延伸边删除set里元素 直到两头都不在set里 然后重复操作直到set为空
回复 支持 2 反对 0

使用道具 举报

我的人缘0
BigShaun 发表于 2018-3-15 05:16:03 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
就是hash table的题吧。遍历一个节点的时候把他前后节点的计数+1,遍历之后的节点时如果有对应的key已经在表中,我们减去对应的value。

public int numberOfGroup(Set<DLinkedNode> set){
        Map<DLinkedNode, Integer> map = new HashMap<>();
        . From 1point 3acres bbs
        int count = 0;
        for(DLinkedNode node : set){
            count++;
             来源一亩.三分地论坛.
            int sameGroup= map.getOrDefault(node, 0);
            count -= sameGroup;
            
            if(node.pre!=null)
                map.put(node.pre, map.getOrDefault(node.pre, 0)+1);
            if(node.post!=null). visit 1point3acres for more.
                map.put(node.post, map.getOrDefault(node.post, 0)+1);. 牛人云集,一亩三分地
        }
       
        return count;.1point3acres网
    }
回复 支持 2 反对 0

使用道具 举报

我的人缘0
yzkst06100 发表于 2018-3-14 23:56:49 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
没给head 那就这样,不知道这个list里面有没有环

public int groupList(Set<Node> set) {. visit 1point3acres for more.
                Set<Node> visited = new HashSet<>();
                int res = 0;.1point3acres网
                for (Node i : set) {. From 1point 3acres bbs
                        if (visited.contains(i)) continue;
                        res ++;
                        visited.add(i);
                        left(i,visited,set);. 留学申请论坛-一亩三分地
                        right(i,visited,set);. Waral 博客有更多文章,
                }
                return res;
        }
        private void left(Node temp, Set<Node> visited , Set<Node> set) {
                if (temp == null || temp.left == null) return;
                if (!set.contains(temp.left) || visited.contains(temp.left)) {
                        return;
                       
                }else {
                        visited.add(temp.left);
                        left(temp.left , visited , set);-google 1point3acres
                }
                return;
        }
回复 支持 1 反对 0

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-14 13:04:22 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
解法一
. 一亩-三分-地,独家发布union-find, google很喜欢union find和分组的题啊,要求良好基本功才能在20分钟写出来,然而我没有. Waral 博客有更多文章,

解法二:. from: 1point3acres
思路来源于2 sum,merge interval, k-empty slot(oa 题)
用两个set保存所有group的左右边界(exclusive)节点
比如 group{2}, left存1,right存3。
等到遍历到3,存在于right中,删除掉3,把3.next(4)放入right,count 不变
同理对于left。.本文原创自1point3acres论坛
当一个节点同时,在left和right中,说明可以concatenate两个group,group count--,update left and right
不在left,right就新开一个group,add its prev and next separately to left and right.
O(n) time and space. 留学申请论坛-一亩三分地

评分

参与人数 1大米 +3 收起 理由
forgarden + 3 给你点个赞!

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
yzkst06100 发表于 2018-3-14 23:22:17 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
zyy_123 发表于 2018-3-14 15:11
为何要额外set 直接随便选一个然后在linkedlist里左右延伸 边延伸边删除set里元素 直到两头都不在set里 然 ...

我想了一种方法,但是没解决set里面iteration的问题,会报错,但原理应该是对的;不知道有没有办法解决.本文原创自1point3acres论坛

public int groupList(ListNode head , Set<Node> set) {
        int origin = count(head);//count the num of nodes
        int res = 0;
        for (Node cur : set) {
                res ++;
                if (set.contains(cur.left)) {. Waral 博客有更多文章,
                        left(cur , set);
                }. From 1point 3acres bbs
                if (set.contains(cur.right)) {
                        right(cur , set);
                }
                set.remove(cur);
        }
        return origin - res;. 围观我们@1point 3 acres
}.本文原创自1point3acres论坛
private void left(Node temp, Set<Node> s) {
        if (temp == null) return;. 1point 3acres 论坛
        if (s.contains(temp.left)) {
                left(temp.left,s);
                s.remove(temp.left);
        } 来源一亩.三分地论坛.
        return;
}
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-14 23:23:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
你的做法对于offline可以,但我写的能online,这是我想的唯一优势。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-14 23:24:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zyy_123 发表于 2018-3-14 15:11
为何要额外set 直接随便选一个然后在linkedlist里左右延伸 边延伸边删除set里元素 直到两头都不在set里 然 ...

Online优势
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-14 23:28:46 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
yzkst06100 发表于 2018-3-14 23:22
我想了一种方法,但是没解决set里面iteration的问题,会报错,但原理应该是对的;不知道有没有办法解决
...

没给head 忘了说
再有要同时考虑left right都包含cur,否则left right更新错误
回复 支持 反对

使用道具 举报

我的人缘0
eejchen 发表于 2018-3-15 00:11:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这个题目没太看懂。。。就lz举的这个例子来说,构成哪几个group呢?求解答一下
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-15 00:13:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
double linked list: 1,2,3,4,5
subset : {1,2,5}
{1,2,5}能构成2个group(相连为一个group); 1,2 一个,5一个

评分

参与人数 1大米 +3 收起 理由
forgarden + 3 很有用的信息!

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
yangyuan 发表于 2018-3-15 01:15:37 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
这可以看作是个简化的 DBSCAN。用 DBSCAN 可以空间 O(n) 时间 O(n)。
回复 支持 反对

使用道具 举报

我的人缘0
idatascience 发表于 2018-3-15 01:48:51 | 显示全部楼层
  此人我要顶:
 
76% (16) 【我投】
  此人我要踩:
 
24% (5) 【我投】
CharlesLeeSysu 发表于 2018-3-15 00:13. 1point 3acres 论坛
double linked list: 1,2,3,4,5. 1point3acres
subset : {1,2,5}
{1,2,5}能构成2个group(相连为一个group); 1,2  ...

哦,所以必须是直接相连的nodes才算一个group,比如如果subset里是1,2, 3,就只算一个group,是这样么?这样的话,可以从subset里选一个node出来,建左队列和右队列,每个队列都while,如果下一个在hashset里,继续,并删除已经visited过的nodes,如果不是break。两个都break之后,就是一个group,count+1,直到最后subset为空为止。
回复 支持 反对

使用道具 举报

我的人缘0
idatascience 发表于 2018-3-15 01:49:38 | 显示全部楼层
  此人我要顶:
 
76% (16) 【我投】
  此人我要踩:
 
24% (5) 【我投】
CharlesLeeSysu 发表于 2018-3-15 00:13.留学论坛-一亩-三分地
double linked list: 1,2,3,4,5
subset : {1,2,5}
{1,2,5}能构成2个group(相连为一个group); 1,2  ...
来源一亩.三分地论坛.
楼主,你电面45分钟就这一道题么?还是要求一题多解?
回复 支持 反对

使用道具 举报

我的人缘0
Ramily 发表于 2018-3-15 01:57:24 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
请问这个double linked list 是线性的还是树形的结构呢? 指向的节点会大于一个吗?
回复 支持 反对

使用道具 举报

我的人缘0
Ramily 发表于 2018-3-15 02:02:03 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
. 留学申请论坛-一亩三分地
什么是offline优势呢
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-15 02:18:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Ramily 发表于 2018-3-15 02:02
什么是offline优势呢

可以依次取出节点 算法不依赖后面的节点
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-15 02:19:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
idatascience 发表于 2018-3-15 01:49
楼主,你电面45分钟就这一道题么?还是要求一题多解?

开头20分钟有一些behavior question
就一题
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-15 02:19:22 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
idatascience 发表于 2018-3-15 01:49.留学论坛-一亩-三分地
楼主,你电面45分钟就这一道题么?还是要求一题多解?

开头20分钟有一些behavior question
就一题
回复 支持 反对

使用道具 举报

我的人缘0
ScarlettQQ 发表于 2018-3-15 02:57:39 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
请问一下楼主bq问了什么呀~
回复 支持 反对

使用道具 举报

我的人缘0
heroic 发表于 2018-3-15 03:17:18 | 显示全部楼层
  此人我要顶:
 
100% (5) 【我投】
  此人我要踩:
 
0% (0) 【我投】
我觉得就是一个简化版的求图的连通分量的个数
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-20 17:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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