一亩三分地论坛

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

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

9/3 Google MTV onsite

[复制链接] |试试Instant~ |关注本帖
laurie洁 发表于 2015-9-4 10:39:22 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
前一天晚上太兴奋了,居然只睡了4个小时。凌晨给HR发邮件问能不能改时间,HR很好,说可以,但是不确定明天有没有spot. 心一横还是面了~
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

Round 1: [size=14.6667px]非常好的一个小哥,讲了半天Google interview会很累啊,他很抱歉啊,神马神马的。弄得我都不好意思了。
先问了一下为什么我选择用Java, 有什么优缺点。
然后出了一道题
Given a black and white image represented as a matrix, process the image in-place that only keeps the contour of the black region and turn all the inside pixels to white. 他强调了image可能很大,所以需要考虑怎样节约memory。
Round 2: [size=14.6667px]Design a game unblock me and implement the function to solve the game
[size=14.6667px]就是把把木块移来移去,最终使得红的木块能被移出出口~.1point3acres缃
[size=14.6667px]用backtracking来solve的~
[size=14.6667px]
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Round 3: [size=14.6667px]Find a pair of Strings which don’t have characters in common, and the product of the length is maximum
[size=14.6667px]地里见过,但是没有想到最优,小哥一步一步跟我讨论,最后优化了好多
[size=14.6667px]
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Round 4: [size=14.6667px]Find duplicate subtrees in a BT, and print out
这一轮脑子不转了,啊啊啊~面的不好,他提示我了好多~
反正大的思路是有的,就是在每个node上找到preorder和inorder traversal的结果,然后跟HashSet里面已经有的比较,两个都有duplicate就代表是duplicate subtree.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
[size=14.6667px]他提示了我好多怎么从O(n^2)优化到O(n), 感觉他都急的要直接告诉我最优解是什么了~
[size=14.6667px]汗~~这样是不是会扣很多分?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
[size=14.6667px]-google 1point3acres

[size=14.6667px]教训就是就算是面高富帅公司也要保持平常心啊~像楼主这样兴奋得一晚上不睡觉简直就是作死啊~

评分

7

查看全部评分

本帖被以下淘专辑推荐:

坐看云起 发表于 2015-9-6 04:53:41 | 显示全部楼层
Round 1
其实只用扫最外围是0的点就可以了吧,然后记录一下,需要O(mn)的额外空间. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

Round 3
输入是一个String数组?还是一个完整的String自己分割?优化是用int表示string?

Round 4
直接上代码吧,可以用String再优化一下,懒得写了。。。
public class Solution {
        private boolean contains;
        private TreeNode node1, node2;
       
        public boolean SameSubTree(TreeNode root){
                if(root == null){
                        return true;
                }
               
                contains = false;
                node1 = null;
                node2 = null;
                -google 1point3acres
                HashMap<List<Integer>, TreeNode> record = new HashMap<List<Integer>, TreeNode>();
                search(root, node1, node2, record);. 1point3acres.com/bbs
               
                return contains;
        }
       
        private List<List<Integer>> search(TreeNode root, TreeNode n1, TreeNode n2, HashMap<List<Integer>, TreeNode> record){
                ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
               
                if(root == null){
                        res.add(new ArrayList<Integer>());
                        res.add(new ArrayList<Integer>());
                        return res;
                }
               
                List<List<Integer>> left = search(root.left, n1, n2, record);
                List<List<Integer>> right = search(root.right, n1, n2, record);. 鍥磋鎴戜滑@1point 3 acres
                -google 1point3acres
                List<Integer> inorder = new ArrayList<Integer>();
                List<Integer> preorder = new ArrayList<Integer>();-google 1point3acres
                List<Integer> key = new ArrayList<Integer>();
. 1point3acres.com/bbs               
                inorder.addAll(left.get(0));
                inorder.add(root.val);
                inorder.addAll(right.get(0));
               
                preorder.add(root.val);
                preorder.addAll(left.get(1));.1point3acres缃
                preorder.addAll(right.get(1));
                . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                key.addAll(inorder);
                key.addAll(preorder);
               
                if(record.containsKey(key)){
                        contains = true;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        node1 = record.get(key);
                        node2 = root;
                }
               
                record.put(key, root);
               
                res.add(inorder);
                res.add(preorder);
                return res;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }
       
}-google 1point3acres
. 1point 3acres 璁哄潧

补充内容 (2015-9-6 04:54):
手滑了,root == null的时候应该返回false

补充内容 (2015-9-6 04:55): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
List完全可以用String替代,但是懒得改了
回复 支持 2 反对 0

使用道具 举报

dddxhh 发表于 2015-9-4 17:12:57 | 显示全部楼层
g28wang 发表于 2015-9-4 11:00
第一题的思路是什么啊?我想了一个:走遍每一个cell,如果cell是黑色的,并且cell的四周都是黑色的,那么就 ...

这个思路不对,你改了前面的cell会对后面cell的判断产生影响。. From 1point 3acres bbs

example:

****
****
****

当你改了(1,1)位置为o之后,(1,2)位置会被你误判。

另外表示这个图的matrix显然是boolean的不能改为其他值否则内存会是boolean matrix的好多倍。. from: 1point3acres.com/bbs

我觉得比较节省内存的做法应该是按行处理,记录2个数组维护上一行的状态和下一行的状态。
回复 支持 2 反对 0

使用道具 举报

g28wang 发表于 2015-9-4 11:00:10 | 显示全部楼层
第一题的思路是什么啊?我想了一个:走遍每一个cell,如果cell是黑色的,并且cell的四周都是黑色的,那么就把这个cell变成白色。这个思路符合要求么?
回复 支持 反对

使用道具 举报

VivianDQ 发表于 2015-9-4 11:04:54 | 显示全部楼层
牛牛牛牛牛牛牛牛!
回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-9-4 12:35:52 | 显示全部楼层
g28wang 发表于 2015-9-4 11:00
第一题的思路是什么啊?我想了一个:走遍每一个cell,如果cell是黑色的,并且cell的四周都是黑色的,那么就 ...
. 1point3acres.com/bbs
认同这个思路,但是image的处理一般都不会在原图操作,而是额外复制一份。根据原图的值判断是否是边界,对复制的image进行修改操作。这里强调了image很大,而且是in place,可能需要将inside pixels先设置为其他值,例如-1,然后第二遍的时候再修改成白色。
回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-9-4 12:37:15 | 显示全部楼层
Williamslg 发表于 2015-9-4 12:35
认同这个思路,但是image的处理一般都不会在原图操作,而是额外复制一份。根据原图的值判断是否是边界, ...
. 1point3acres.com/bbs
应该也可以block by block的操作,根据复制的block修改原图,但是要注意block之间边界的处理。
回复 支持 反对

使用道具 举报

baobozo 发表于 2015-9-4 12:51:11 | 显示全部楼层
lz最近的面试可是真多啊, 我也刚刚开始面试,天天看你的面经,什么都不说了,给你上分。
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-9-4 12:55:06 | 显示全部楼层
Williamslg 发表于 2015-9-4 12:35
认同这个思路,但是image的处理一般都不会在原图操作,而是额外复制一份。根据原图的值判断是否是边界, ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我是按block by block的思路做的~题目给的Pixel就是个boolean matrix, 所以没有办法改成第三种值~必须依靠附加的data structure来记录改过没有~
我一开始是用的另一个boolean matrix, 但是这样子memory太大~. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
于是还用HashSet记录已经改过的点的Index
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-4 12:56:36 | 显示全部楼层
lz 好人,祝一切顺利!
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-9-4 12:57:21 | 显示全部楼层
hbsophia 发表于 2015-9-4 12:56
lz 好人,祝一切顺利!
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
恩~~谢谢!!!!
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-9-4 13:02:22 | 显示全部楼层
baobozo 发表于 2015-9-4 12:51
lz最近的面试可是真多啊, 我也刚刚开始面试,天天看你的面经,什么都不说了,给你上分。

也没有啦~都赶在这周了~哈哈
谢谢加分!!
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-4 13:15:17 | 显示全部楼层
lzlz, 面完了就早点休息哈。休息好了,顺便请教下round 4 ,o(n) 咋做呢?

多谢多谢
回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-9-4 13:45:52 | 显示全部楼层
laurie洁 发表于 2015-9-4 12:55
我是按block by block的思路做的~题目给的Pixel就是个boolean matrix, 所以没有办法改成第三种值~必须依 ...

如果整个图都是black的话,用HashSet也会开销很大啊。分成了block的话,每个block对应的boolean matrix应该也能满足条件吧
回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-9-4 14:30:55 | 显示全部楼层
laurie洁 发表于 2015-9-4 12:55
我是按block by block的思路做的~题目给的Pixel就是个boolean matrix, 所以没有办法改成第三种值~必须依 ...

请问楼主的block边界上的点如何处理的?
回复 支持 反对

使用道具 举报

jason51122 发表于 2015-9-4 15:08:51 | 显示全部楼层
求问Round 4怎么优化到O(N)啊
回复 支持 反对

使用道具 举报

g28wang 发表于 2015-9-4 22:04:56 | 显示全部楼层
Williamslg 发表于 2015-9-4 12:37
应该也可以block by block的操作,根据复制的block修改原图,但是要注意block之间边界的处理。

同学能不能说说什么是block by block操作啊?就是把一部分的image复制到一个小一天的block里面处理么?
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-9-5 00:47:42 | 显示全部楼层
dddxhh 发表于 2015-9-4 17:12
这个思路不对,你改了前面的cell会对后面cell的判断产生影响。
. Waral 鍗氬鏈夋洿澶氭枃绔,
example:

我觉得按行来处理很赞诶!!
我觉得可能这个是面试官想要的吧~
我的解法不够好~
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-5 05:48:57 | 显示全部楼层
请问LZ round4为什么会有O(n)解法,随着preorder和inorder的结果长度增加,计算hash的时间也慢慢接近O(n),所以总的时间复杂度还是O(n^2)。我这样理解对吗?
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-9-5 08:05:16 | 显示全部楼层
楼主可否说一下round 4的题呢?没太理解是想干什么,多谢了~
回复 支持 反对

使用道具 举报

Nevermindeaf 发表于 2015-9-5 08:31:11 | 显示全部楼层
我onsite之前一晚上就睡了2个半小时....
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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