一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3706|回复: 23
收起左侧

Google/YouTube onsite 面经

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

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

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

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

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

第一轮:
给一个函数hasObstacle(Point point, Direction direction),告诉你在某个point时往某个direction推一个球可否推动(若推得动,表明前方无障碍,若推不动,表明前方有障碍)。
然后给一个start point和一个end point,求出把球从start推到end的最少步数。(题干内容就这些,然后自己定义Point和Direction等)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二轮:
给一颗普通binary tree,求出其中所有的相同的子树,并返回这些子树的根结点。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第三轮:
午饭
. 1point 3acres 璁哄潧
第四轮:
给一个log file,里面记录两类函数: start(int processId, int startTime)和finish(int processId, int endTime),分别记录系统调用某个进程的开始时间和结束时间以及该进程的ID。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
给了2个条件:(1)时间是递增的,(2)对于每个进程,每一个start总有一个对应的finish。
问题是:当遇到一个finish(int proc1, int time1)函数时,如果有排在proc1之前还有进程没有结束的话(i.e., 开始时间在proc1之前的进程),就不打印任何内容;否则打印出所有已经结束的进程,并且按照他们的开始时间顺序打印。
比如:.鏈枃鍘熷垱鑷1point3acres璁哄潧
-start(1,1). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
-start(2,2).1point3acres缃
-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前一定要休息好,这样才能有好状态去面对面试。

.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

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.
. more info on 1point3acres.com
Assume leaf nodes are not subtrees.


List<Node> findCommonSubtrees(Node root){
    Map<String, List<Node>> map = new HashMap<>();
    helper(root, map);
    List<Node> ans = new LinkedList<>();. Waral 鍗氬鏈夋洿澶氭枃绔,
    for(String str : map.keySet()){
    if(map.get(str).size() >= 2){
    ans.addAll(map.get(str));
}
}
return ans;
}. 鍥磋鎴戜滑@1point 3 acres


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;. more info on 1point3acres.com
    if(!map.containsKey(ans)){
    map.put(ans, new LinkedList<>());. From 1point 3acres bbs
}
    map.get(ans).add(root);
    return ans;
}
回复 支持 1 反对 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
第四轮的思路是什么?

. From 1point 3acres bbs第四题应该就是stack存吧
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

lz 这个最优的解法是什么?
. 1point 3acres 璁哄潧
第二轮:.1point3acres缃
给一颗普通binary tree,求出其中所有的相同的子树,并返回这些子树的根结点。
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

shuishoubuku 发表于 2016-2-29 14:19:52 | 显示全部楼层
Class Point{
. 1point3acres.com/bbs
        Int id;
       
        Int start;
       
        Int end;
       
        Public Point(int start){
               
                This.start= start;
        }

}
. Waral 鍗氬鏈夋洿澶氭枃绔,
static class PointSort implements Comparator<Point> {
 
                public int compare(Point one, Point two) {
                        return two.start - one.start;
                }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }



Print(Pair[] starts, Pair[]ends){
       
       
        Queue<Point> mainQueue= new PriorityQueue<Point>(PointSort); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
       
        Queue<Point> backUpQueue= new PriorityQueue<Point>(PointSort);
        . 鍥磋鎴戜滑@1point 3 acres
       
        Map<Intger, Point> map= new HashMap<Integer, Point>();
       
        For(int i=0;i<start.length;i++){
       
                Point p= new Point(starts[i].first,starts[i].second)
       
                mainQueue.add(p);. From 1point 3acres bbs
                .鏈枃鍘熷垱鑷1point3acres璁哄潧
                map.add(start[i],p);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                . 鍥磋鎴戜滑@1point 3 acres
       
        }
       
        For(int i=0;i<end.length;i++){
       
                If(mainQueue.peek()==end[i].first){
                       
                        Int start= map.get(end[i].first).start;
                        System.out.println(end[i].first,map.get(end[i].first).start,end[i].second);
                        . 鍥磋鎴戜滑@1point 3 acres
                        mainQueue.poll();
                       
                        If(!backUpQueue.isEmpty()){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                       
                       
                        Point candidate= backUpQueue.peek();
                        While(mainQueue.peek()== candidate.start){
                       
                        System.out.println(mainQueue.peek().id,mainQueue.peek().start,mainQueue.end() );
                       
                       
                                backUpQueue.poll();
                                mainQueue.poll();
                        }
                       
                }.1point3acres缃
                Else{
                        Point p =map.get(end[i].first).start;
                        p.end =end[i].second;. 鍥磋鎴戜滑@1point 3 acres
                       
                        backUpQueue.add(p);
                }.1point3acres缃
       
       
        -google 1point3acres
        }
.鏈枃鍘熷垱鑷1point3acres璁哄潧




. From 1point 3acres bbs}

评分

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. visit 1point3acres.com for more.
第四题应该就是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>>. From 1point 3acres bbs
2. 到底哪种解法是面试官想要的?
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-5 13:02:02 | 显示全部楼层
tigercode 发表于 2016-9-18 00:47. more info on 1point3acres.com
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.1point3acres缃
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就可以了吧,然后看有没有字串相同的
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 10:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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