【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 2699|回复: 32
收起左侧

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

[复制链接] |试试Instant~
我的人缘0
CharlesLeeSysu 发表于 2018-3-14 12:57:00 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩

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论坛

解法在回答里面,求加米,没权限看不了面经很难过

. 1point 3acres 论坛
. 围观我们@1point 3 acres

评分

参与人数 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
BigShaun 发表于 2018-3-15 05:16:03 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
就是hash table的题吧。遍历一个节点的时候把他前后节点的计数+1,遍历之后的节点时如果有对应的key已经在表中,我们减去对应的value。

public int numberOfGroup(Set<DLinkedNode> set){.本文原创自1point3acres论坛
        Map<DLinkedNode, Integer> map = new HashMap<>();. 牛人云集,一亩三分地
       
        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)
                map.put(node.post, map.getOrDefault(node.post, 0)+1);
        }
       
        return count;
    }
回复

使用道具 举报

我的人缘0
zyy_123 发表于 2018-3-14 15:11:05 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
为何要额外set 直接随便选一个然后在linkedlist里左右延伸 边延伸边删除set里元素 直到两头都不在set里 然后重复操作直到set为空
回复

使用道具 举报

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

public int groupList(Set<Node> set) {
                Set<Node> visited = new HashSet<>();
                int res = 0;-google 1point3acres
                for (Node i : set) {
                        if (visited.contains(i)) continue;
                        res ++;. more info on 1point3acres
                        visited.add(i);
                        left(i,visited,set);. Waral 博客有更多文章,
                        right(i,visited,set);
                }
                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;
. Waral 博客有更多文章,                       
                }else {
                        visited.add(temp.left);
                        left(temp.left , visited , set);
                }
                return;
. more info on 1point3acres        }
回复

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-14 13:04:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
解法一
union-find, google很喜欢union find和分组的题啊,要求良好基本功才能在20分钟写出来,然而我没有

解法二:
思路来源于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 不变-google 1point3acres
同理对于left。
当一个节点同时,在left和right中,说明可以concatenate两个group,group count--,update left and right. 围观我们@1point 3 acres
不在left,right就新开一个group,add its prev and next separately to left and right.
O(n) time and space

评分

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

查看全部评分

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
yzkst06100 发表于 2018-3-14 23:22:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (55)
 
 
1% (1)  踩
zyy_123 发表于 2018-3-14 15:11
为何要额外set 直接随便选一个然后在linkedlist里左右延伸 边延伸边删除set里元素 直到两头都不在set里 然 ...
. 牛人云集,一亩三分地
我想了一种方法,但是没解决set里面iteration的问题,会报错,但原理应该是对的;不知道有没有办法解决

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)) {
                        left(cur , set);
                }
                if (set.contains(cur.right)) {
                        right(cur , set);
                }
                set.remove(cur);
        }
        return origin - res;
}
private void left(Node temp, Set<Node> s) {
        if (temp == null) return;
        if (s.contains(temp.left)) {
                left(temp.left,s);
                s.remove(temp.left);
        }
        return;
}. 1point3acres
回复

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-14 23:23:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
你的做法对于offline可以,但我写的能online,这是我想的唯一优势。
回复

使用道具 举报

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

Online优势

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
eejchen 发表于 2018-3-15 00:11:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  78% (18)
 
 
21% (5)  踩
这个题目没太看懂。。。就lz举的这个例子来说,构成哪几个group呢?求解答一下
回复

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-15 00:13:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
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 很有用的信息!

查看全部评分

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
yangyuan 发表于 2018-3-15 01:15:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (77)
 
 
9% (8)  踩
这可以看作是个简化的 DBSCAN。用 DBSCAN 可以空间 O(n) 时间 O(n)。
回复

使用道具 举报

我的人缘1
idatascience 发表于 2018-3-15 01:48:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (318)
 
 
14% (54)  踩
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  ...

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

使用道具 举报

我的人缘1
idatascience 发表于 2018-3-15 01:49:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (318)
 
 
14% (54)  踩
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 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (45)
 
 
2% (1)  踩
请问这个double linked list 是线性的还是树形的结构呢? 指向的节点会大于一个吗?
回复

使用道具 举报

我的人缘0
Ramily 发表于 2018-3-15 02:02:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (45)
 
 
2% (1)  踩

什么是offline优势呢
回复

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-15 02:18:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
Ramily 发表于 2018-3-15 02:02
什么是offline优势呢

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

使用道具 举报

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

开头20分钟有一些behavior question
就一题
回复

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-15 02:19:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
idatascience 发表于 2018-3-15 01:49
楼主,你电面45分钟就这一道题么?还是要求一题多解?
. more info on 1point3acres
开头20分钟有一些behavior question.本文原创自1point3acres论坛
就一题
回复

使用道具 举报

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

使用道具 举报

我的人缘0
heroic 发表于 2018-3-15 03:17:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  58% (147)
 
 
41% (106)  踩
我觉得就是一个简化版的求图的连通分量的个数
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-23 01:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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