[八我司] 半导体公司工作5年以上谈谈感想

一亩三分地论坛

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

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
锦晖律师事务所
12月16日
H1B讲座通知
查看: 3380|回复: 32
收起左侧

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

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

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



评分

参与人数 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)   【踩】
全局: 顶  96% (24)
 
 
4% (1)  踩
就是hash table的题吧。遍历一个节点的时候把他前后节点的计数+1,遍历之后的节点时如果有对应的key已经在表中,我们减去对应的value。

public int numberOfGroup(Set<DLinkedNode> set){
        Map<DLinkedNode, Integer> map = new HashMap<>();
       
        int count = 0;. From 1point 3acres bbs
        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% (40)
 
 
0% (0)  踩
为何要额外set 直接随便选一个然后在linkedlist里左右延伸 边延伸边删除set里元素 直到两头都不在set里 然后重复操作直到set为空
回复

使用道具 举报

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

public int groupList(Set<Node> set) {
                Set<Node> visited = new HashSet<>();
                int res = 0;
                for (Node i : set) {
                        if (visited.contains(i)) continue;
                        res ++;
                        visited.add(i);
                        left(i,visited,set);
                        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;
                       
                }else {
                        visited.add(temp.left);
                        left(temp.left , visited , set);
                }
                return;
        }
回复

使用道具 举报

我的人缘0
 楼主| CharlesLeeSysu 发表于 2018-3-14 13:04:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (40)
 
 
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 不变
同理对于left。
当一个节点同时,在left和right中,说明可以concatenate两个group,group count--,update left and right-baidu 1point3acres
不在left,right就新开一个group,add its prev and next separately to left and right.. From 1point 3acres bbs
O(n) time and space

评分

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

查看全部评分

回复

使用道具 举报

我的人缘0
yzkst06100 发表于 2018-3-14 23:22:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
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-baidu 1point3acres
        int res = 0;
        for (Node cur : set) {
                res ++;
                if (set.contains(cur.left)) {. From 1point 3acres bbs
                        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;
}
回复

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

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

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


回复

使用道具 举报

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

使用道具 举报

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

查看全部评分

回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

手机版|小黑屋|一亩三分地留学网

GMT+8, 2018-12-15 03:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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