一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 2838|回复: 25
收起左侧

狗家阳谷昂赛特

[复制链接] |试试Instant~ |码农类general, 美国面经, google, 面试经验
我的人缘0

分享帖子到朋友圈
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (15)
 
 
0% (0)    👎

2019(7-9月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Fail/Rej | 在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
上个月面的,因为有内推所以recruiter给skip了电面。4轮算法+1轮BQ
1. 两个人玩占领二叉树的游戏,二叉树的node可以往parent,left child,right child走,问如果你是后者开始占领的人,选哪个点获胜的可能性最大。
Follow up:如果你是先走的人,应该选哪一个点开始。
2. 实现澳洲投票制度(偏好投票制),input是2DArray,让输出winner是哪个candidate。
3. Course Schedule根据课程的dependencies问如果每个学期可以想上无限量的课,最快几个学期把所有课上完。
Follow up:如果每学
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
什么时候全部都互相成为好朋友。
5. BQ 主要问做了什么项目,如何跟同事合作的。还问了Accessibility相关的问题,如何让客户更好的使用产品。

评分

参与人数 18大米 +58 收起 理由
KuanCNTF + 3 给你点个赞!
halolk1 + 1 很有用的信息!
pudding0129 + 1 赞一个
水晶月 + 2 赞一个!
zzwzzw435 + 2 给你点个赞!
yunella + 1 赞一个
byte + 1 赞一个
garyatsch + 3 很有用的信息!
hadoopG + 2 欢迎分享你知道的情况,会给更多积分奖励!
StupidCorn + 1 很有用的信息!

查看全部评分


上一篇:SAP OA
下一篇:Scotiabank - Toronro - digital factory - senior dev - OA

本帖被以下淘专辑推荐:

  • · google|主题: 193, 订阅: 112
我的人缘0
zzwzzw435 2019-8-21 02:41:45 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (246)
 
 
0% (0)    👎
本帖最后由 zzwzzw435 于 2019-8-21 03:29 编辑
tianjiayou 发表于 2019-8-20 11:15
我其实没get到。。因为每个课程的indegree和outdegree不一定是1,这样的话,怎么算呢?

感觉还是可以做,和indegree,outdegree并没有太大关系
[Java] 纯文本查看 复制代码
class Solution {
    public int minSemester(int numCourses, int[][] prerequisites,int k) {
        int completedCourses = 0;
        List<Integer>[] nextCourses = new List[numCourses];
        int[] height = new int[numCourses];
        for(int i =0; i<numCourses; i++){
            nextCourses[i] = new ArrayList<>();
        }
        int[] incomingEdgesCount = new int[numCourses];
        for(int[] i:prerequisites){
            incomingEdgesCount[i[0]]++;
            nextCourses[i[1]].add(i[0]);               
        }
        // for(int i : incomingEdgesCount){
        //     System.out.print(i+" ");
        // }
        for(int i = 0; i < height.length; i++){
            if(height[i] == 0)
               height[i] = getHeight(height,nextCourses,i);
        }
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] a, int [] b){
                return b[1] - a[1];
            }
        });
        // Add all nodes that have indegree zero to the BFS queue
        for(int i = 0; i<incomingEdgesCount.length; i++){
            if(incomingEdgesCount[i] == 0){
                pq.offer(new int[]{i,height[i]});
            }
        }
        // Bfs starting with indegree 0  
        int semester = 0;
        while(!pq.isEmpty()){
            semester++;
            int num = pq.size();
            for(int g = 0; g < k && !pq.isEmpty() && g < num; g++){
            int[] course = pq.poll();
            completedCourses++;
            for(int i : nextCourses[course[0]]){
                incomingEdgesCount[i]--; 
                if(incomingEdgesCount[i] == 0){
                    pq.offer(new int[]{i,height[i]});
                }
            }
            }
        }
        //System.out.println(completedCourses);
        return semester;   
    }
    private int getHeight(int[] height,List<Integer>[] nexts,int idx){
        List<Integer> next = nexts[idx];
        if(next.size() == 0){
            return 1;
        }
        if(height[idx] != 0){
            return height[idx];
        }
        int max = 0;
        for(int n : next){
            max = Math.max(max,getHeight(height,nexts,n));
        }
        return max + 1;
    }
}


评分

参与人数 3大米 +5 收起 理由
pflugchristian + 1 给你点个赞!
水晶月 + 2 赞一个!
zmrs + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
zzwzzw435 2019-8-21 03:25:17 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (246)
 
 
0% (0)    👎
tianjiayou 发表于 2019-8-21 02:56
我觉得还是有问题,这种做法我想过;
看下我这个例子;这里2是7的parent(实在是不好画 lol)1是2,3,4,5 ...

没有问题啊,345的height都是3,而2的height是2,所以先入345,再入2,6。下面是我跑的结果
0
243
15
6
total:4

评分

参与人数 2大米 +4 收起 理由
水晶月 + 2 赞一个!
zmrs + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
jobsjobs 2019-8-20 14:03:06 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (10)
 
 
0% (0)    👎
第一个问题是 Leetcode 1145 新题
https://leetcode.com/problems/binary-tree-coloring-game/

评分

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

查看全部评分

回复

使用道具 举报

我的人缘0
zzwzzw435 2019-8-20 10:37:16 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (246)
 
 
0% (0)    👎
tianjiayou 发表于 2019-8-20 06:02
求问楼主course schedule的follow up怎么回答的?

我的思路是用priorityQueue每次pop剩余课程最多的课程串,比如1->2->3->4, 5->6, 7->8,三个课程序列,k=2的时候,上课顺序1,5 -> 2, 7 - > 3,6 -> 4,8 这样

评分

参与人数 3大米 +5 收起 理由
pflugchristian + 1 给你点个赞!
zmrs + 2 给你点个赞!
水晶月 + 2 赞一个!

查看全部评分

回复

使用道具 举报

我的人缘0
wujiandaoxy 2019-8-19 11:59:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (9)
 
 
0% (0)    👎
支持下楼主分享,很有参考意义
回复

使用道具 举报

我的人缘0
dengzeyu147 2019-8-19 14:14:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (149)
 
 
10% (18)    👎
请问第二题是那个投票面经题?如果不是,能请楼主解释一下?已加米
回复

使用道具 举报

我的人缘0
crlyw 2019-8-19 21:40:15 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   87% (56)
 
 
12% (8)    👎
请问第一题的那个获胜条件是什么?
回复

使用道具 举报

我的人缘0
我奋斗我无悔 2019-8-20 02:29:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (176)
 
 
1% (2)    👎
请问,第一题,对方经过的已经占领的点,我还可以经过吗 或者我只能经过那些未被占领的点?
回复

使用道具 举报

我的人缘0
tianjiayou 2019-8-20 06:02:26 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (44)
 
 
0% (0)    👎
求问楼主course schedule的follow up怎么回答的?
回复

使用道具 举报

我的人缘0
luoyu 2019-8-20 10:56:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
支持楼主分享
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (44)
 
 
0% (0)    👎
zzwzzw435 发表于 2019/08/20 10:37:16


我的思路是用priorityQueue每次pop剩余课程最多的课程串,比如1->2->3->4, 5->6, 7->8,三个课程序列,k=2的时候,上课顺序1,5 -> 2, 7 - > 3,6 ...

我其实没get到。。因为每个课程的indegree和outdegree不一定是1,这样的话,怎么算呢?
回复

使用道具 举报

我的人缘0
 楼主| michelletsao9 2019-8-20 11:57:34 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (15)
 
 
0% (0)    👎
crlyw 发表于 2019-8-19 21:40
请问第一题的那个获胜条件是什么?

获胜条件是最后能占领最多的Nodes
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-2-25 13:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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