在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 7082|回复: 23
收起左侧

Google/YouTube onsite 面经

[复制链接] |试试Instant~ |关注本帖
ddvlongren 发表于 2016-2-28 02:44:12 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类General 硕士 全职@Google - 网上海投 - Onsite  | Fail | fresh grad应届毕业生

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

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

x
在YouTube总部San Bruno面的,一共4轮外加1轮午饭。

第一轮:
给一个函数hasObstacle(Point point, Direction direction),告诉你在某个point时往某个direction推一个球可否推动(若推得动,表明前方无障碍,若推不动,表明前方有障碍)。.1point3acres网
然后给一个start point和一个end point,求出把球从start推到end的最少步数。(题干内容就这些,然后自己定义Point和Direction等)

第二轮:
给一颗普通binary tree,求出其中所有的相同的子树,并返回这些子树的根结点。

第三轮:
午饭. 1point3acres

第四轮:. 围观我们@1point 3 acres
给一个log file,里面记录两类函数: start(int processId, int startTime)和finish(int processId, int endTime),分别记录系统调用某个进程的开始时间和结束时间以及该进程的ID。
给了2个条件:(1)时间是递增的,(2)对于每个进程,每一个start总有一个对应的finish。.1point3acres网
问题是:当遇到一个finish(int proc1, int time1)函数时,如果有排在proc1之前还有进程没有结束的话(i.e., 开始时间在proc1之前的进程),就不打印任何内容;否则打印出所有已经结束的进程,并且按照他们的开始时间顺序打印。. 牛人云集,一亩三分地
比如:. more info on 1point3acres
-start(1,1)
. from: 1point3acres -start(2,2)
-start(3,3)
-end(2,4)
-end(3,5)
-end(1,6). 一亩-三分-地,独家发布
遇到end(2,4)和end(3,5)时不打印,因为进程1的开始时间在进程2和进程3之前,直到遇到end(1,6)时,才能打印,打印顺序如下:
1: 1, 6
2: 2, 4
3: 3, 5。
分别是进程ID:开始时间,结束时间。

第五轮:
给一个MxN的board,里面存有一些整数,各整数代表一种颜色,如果是0,则表示该格子没有颜色。相同颜色并且相邻的格子可以组成一个component,求出该board里面最大size的component。题目跟number of islands很类似。

面试题目就4题,每轮一题。面试前几天连续熬夜临时刷提抱佛脚,面试过程中又超级紧张,遇到题目时脑子怎么也转不起来,所以跪地妥妥的。大家在onsite前一定要休息好,这样才能有好状态去面对面试。



评分

4

查看全部评分

本帖被以下淘专辑推荐:

weijinchuan10 发表于 2016-10-31 10:21:53 | 显示全部楼层
weijinchuan10 发表于 2016-10-30 11:24. 一亩-三分-地,独家发布
给一颗普通binary tree,求出其中所有的相同的子树,并返回这些子树的根结点
来源一亩.三分地论坛.
feels should be solved in ...

i understand this problem wrongly at first, following is a modified version.

Assume leaf nodes are not subtrees.

-google 1point3acres
List<Node> findCommonSubtrees(Node root){
    Map<String, List<Node>> map = new HashMap<>();. 留学申请论坛-一亩三分地
    helper(root, map);. 牛人云集,一亩三分地
    List<Node> ans = new LinkedList<>();
    for(String str : map.keySet()){. From 1point 3acres bbs
    if(map.get(str).size() >= 2){
    ans.addAll(map.get(str));
}
}
return ans;
}.留学论坛-一亩-三分地


String helper(Node root, Map<String, List<Node>> map){
    if(root == null) return "#null";
    if(root.left == null && root.right == null) return "#" + Integer.toString(root.val)+"#null#null";
    String leftTree = helper(root.left, map);. 牛人云集,一亩三分地
    String rightTree = helper(root.right, map);
    String ans = "#" + Integer.toString(root.val) + leftTree + rightTree;
    if(!map.containsKey(ans)){
    map.put(ans, new LinkedList<>());
}. 围观我们@1point 3 acres
    map.get(ans).add(root);
    return ans;
}. 牛人云集,一亩三分地
回复 支持 2 反对 0

使用道具 举报

caiqi8877 发表于 2016-5-13 07:14:54 | 显示全部楼层
楼主推球那题如果推一下球,球会一直往前直到碰到障碍吗?
回复 支持 0 反对 1

使用道具 举报

wtcupup 发表于 2016-2-28 03:12:54 | 显示全部楼层
第四轮的思路是什么?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-28 08:18:29 | 显示全部楼层
wtcupup 发表于 2016-2-28 03:12
第四轮的思路是什么?

第四题应该就是stack存吧
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-28 09:08:17 | 显示全部楼层
用两个hash table,一个计数一个缓存 也可以合并成一个
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-29 04:18:46 | 显示全部楼层

lz 这个最优的解法是什么?

第二轮:
给一颗普通binary tree,求出其中所有的相同的子树,并返回这些子树的根结点。
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-29 05:49:00 | 显示全部楼层
Dfs 一遍就行 我没记错的话
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

shuishoubuku 发表于 2016-2-29 14:19:20 | 显示全部楼层
写了个伪代码过来,可能有bug,想赚点大米
回复 支持 反对

使用道具 举报

shuishoubuku 发表于 2016-2-29 14:19:52 | 显示全部楼层
Class Point{. visit 1point3acres for more.

        Int id; . 留学申请论坛-一亩三分地
       
        Int start;
       
        Int end;
       
        Public Point(int start){
               
                This.start= start; 来源一亩.三分地论坛.
        }

}. 围观我们@1point 3 acres

static class PointSort implements Comparator<Point> {
 . 1point 3acres 论坛
                public int compare(Point one, Point two) {
                        return two.start - one.start;. 1point 3acres 论坛
                }.本文原创自1point3acres论坛
        }
. 1point 3acres 论坛


Print(Pair[] starts, Pair[]ends){
        . 留学申请论坛-一亩三分地
       
        Queue<Point> mainQueue= new PriorityQueue<Point>(PointSort);
        . 围观我们@1point 3 acres
        Queue<Point> backUpQueue= new PriorityQueue<Point>(PointSort);. from: 1point3acres
       
       
        Map<Intger, Point> map= new HashMap<Integer, Point>();. 1point 3acres 论坛
       
        For(int i=0;i<start.length;i++){
       
                Point p= new Point(starts[i].first,starts[i].second)
       
                mainQueue.add(p);
               
                map.add(start[i],p);
               
       
        }
       
        For(int i=0;i<end.length;i++){
       
                If(mainQueue.peek()==end[i].first){
                       
                        Int start= map.get(end[i].first).start;. 1point 3acres 论坛
                        System.out.println(end[i].first,map.get(end[i].first).start,end[i].second);. 围观我们@1point 3 acres
                        .1point3acres网
                        mainQueue.poll();
                        -google 1point3acres
                        If(!backUpQueue.isEmpty()){. From 1point 3acres bbs
                       
                       
                        Point candidate= backUpQueue.peek();
                        While(mainQueue.peek()== candidate.start){ 来源一亩.三分地论坛.
                        -google 1point3acres
                        System.out.println(mainQueue.peek().id,mainQueue.peek().start,mainQueue.end() );
                       
                       
                                backUpQueue.poll();
                                mainQueue.poll();
                        }
                       
                }
                Else{
                        Point p =map.get(end[i].first).start;. 1point 3acres 论坛
                        p.end =end[i].second;
                       
                        backUpQueue.add(p);
                }
        . 围观我们@1point 3 acres
       
       
        }

. 1point 3acres 论坛



}. 1point 3acres 论坛

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

echo33 发表于 2016-3-1 13:47:04 | 显示全部楼层
第二题不容易啊,要比较任意俩没有父子(including grandparent-grandchildren relation)关系的节点下的subtree是否相同啊?对普通的tree,可以做一个inorder&preorder traversa并标记null节点 来判断是否相同,但是这里对substring怎么对应啊?

搜了一下说对任意一个节点可以hash? f(左子树hash值, node value, 右字数hash值) 这里要有一个好的hash function
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-3-1 14:27:57 | 显示全部楼层
你把我弄晕了。这题说相同的子树是指该子树所有节点值相同还是其它意思?
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-3-1 15:06:38 | 显示全部楼层
bobzhang2004 发表于 2016-2-28 08:18
第四题应该就是stack存吧

为什么不是用queue呢?不是应该先进先出吗?用一个hashset记录完成的process。
回复 支持 反对

使用道具 举报

Sendoh2015 发表于 2016-3-1 15:16:38 | 显示全部楼层
第三轮没问技术吗
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-3 01:57:37 | 显示全部楼层
Log File 这题大家有什么好方法吗?
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-18 00:47:12 | 显示全部楼层
4.  觉得两个queue+hashmap可以, 一个queue管start, 一个queue管end, map<id, <startTime, endTime>>
2. 到底哪种解法是面试官想要的?
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-5 13:02:02 | 显示全部楼层
tigercode 发表于 2016-9-18 00:47
4.  觉得两个queue+hashmap可以, 一个queue管start, 一个queue管end, map
2. 到底哪种解法是面试官想要的 ...

请问能具体讲讲第四题两个QUEUE+HASHMAP要怎么做吗?
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-5 13:02:57 | 显示全部楼层
求问第一题和第二题思路,第二题相同的树是啥意思?
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-10 10:52:13 | 显示全部楼层
tigercode 发表于 2016-9-18 00:47
4.  觉得两个queue+hashmap可以, 一个queue管start, 一个queue管end, map. 留学申请论坛-一亩三分地
2. 到底哪种解法是面试官想要的 ...

感觉两个QUEUE就够了啊,每次比较START和END的QUEUE头是不是一样,不是一样的,把前面都POLL出来,然后OFFER到队列尾,找到和START一样的输出,只是不知道复杂度是不是有点高,因为最坏的CASE是O(N^2)
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-10 10:53:03 | 显示全部楼层
如果直接要用MAP的话是不是可以就过一遍LOG FILE,把开始时间,结束时间记录,然后顺序输出?
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-10 10:54:41 | 显示全部楼层
echo33 发表于 2016-3-1 13:47
第二题不容易啊,要比较任意俩没有父子(including grandparent-grandchildren relation)关系的节点下的subt ...

如果标记NULL的话就PREORDER就可以了吧,然后看有没有字串相同的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-23 13:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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