一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2616|回复: 16
收起左侧

Dec 15 NY Google Onsite

[复制链接] |试试Instant~ |关注本帖
lfenjoy9 发表于 2016-1-11 07:57:46 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
回报地里,圣诞节前的一个星期在NY面的. 1point 3acres 璁哄潧

Round one:
1. Game of Life (Leetcode)
Follow up: how to scale if the board has 1 million rows and columns
用MapReduce. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

Round two:
1. Gate and Wall (Leetcode)
2 Range Sum Query 2D - Mutable  (Leetcode). 1point3acres.com/bbs
用 Binary Indexed Tree

Round Three
. from: 1point3acres.com/bbs
1. How to Model HTML dococument . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
用Tree

2. Check if two documents represend by tree have the same inner text
首先extract all text in the tree and then compare
考官不满意,然后写个Iterator,用Iterators进行比较
. 1point 3acres 璁哄潧
Round Four

1. Given a binary tree, find all duplicate subtrees . visit 1point3acres.com for more.
后序访问树,计算每个节点的Hash并且保存在一个HashMap里,
如果有相同的Hash,需要进行比较确认后
然后讨论怎么样计算Hash和一些优化

Round Five (System Design)
- How to design Google Search Suggestion

HC passed and sent ot executive committee . visit 1point3acres.com for more.
求bless

评分

5

查看全部评分

本帖被以下淘专辑推荐:

atwoodwang0918 发表于 2016-1-11 09:06:55 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
楼主好厉害。。。第一题你说用mapreduce做我听都没听过 后来去百度百科里面看了半天 还没看懂=_=|| 哈哈 祝早日offer!
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-11 10:20:24 | 显示全部楼层
关注一亩三分地微博:
Warald
Round 4那道是经典的难题
回复 支持 反对

使用道具 举报

ssross 发表于 2016-1-11 11:42:38 | 显示全部楼层
想问下LZ第三轮HTML那题能不能详细讲讲做法?谢谢!
回复 支持 反对

使用道具 举报

tbian 发表于 2016-1-11 11:55:13 | 显示全部楼层
这些问题都不懂诶
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

tbian 发表于 2016-1-11 11:56:45 | 显示全部楼层
第一题 没明白什么意思
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-11 15:07:32 | 显示全部楼层
能说说round 3的HTML 同一个level elements 如果顺序不同要考虑吗? 另外round 4 可以有哪些优化? 感觉hashMap比较就行了?
回复 支持 反对

使用道具 举报

Thrice 发表于 2016-1-12 00:02:32 | 显示全部楼层
lz你这个面的好难啊。。是有很多年experience吗?能请教下round four的hash具体是怎么算的?对descendant的和hash?hash函数怎样减小collision的
回复 支持 反对

使用道具 举报

 楼主| lfenjoy9 发表于 2016-1-12 01:20:44 来自手机 | 显示全部楼层
Thrice 发表于 2016-1-12 00:02
lz你这个面的好难啊。。是有很多年experience吗?能请教下round four的hash具体是怎么算的?对descendant的 ...

我用Java的类似hashCode的方法根据左节点和右节点的hash,本节点的值来计算本节点的值. Waral 鍗氬鏈夋洿澶氭枃绔,

后来讨论hash函数时,提到可以加入左右节点的高度和节点个数等因素,

回复 支持 反对

使用道具 举报

 楼主| lfenjoy9 发表于 2016-1-12 01:24:25 来自手机 | 显示全部楼层
say543 发表于 2016-1-11 15:07. 1point3acres.com/bbs
能说说round 3的HTML 同一个level elements 如果顺序不同要考虑吗? 另外round 4 可以有哪些优化? 感觉hashM ...
. From 1point 3acres bbs
顺序要相同 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

优化我指的是避免collision
回复 支持 反对

使用道具 举报

 楼主| lfenjoy9 发表于 2016-1-12 01:27:17 来自手机 | 显示全部楼层
tbian 发表于 2016-1-11 11:56
第一题 没明白什么意思

https://leetcode.com/problems/game-of-life/
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2016-1-12 10:58:51 | 显示全部楼层
round 4这题好像就是暴力解决?   感觉树上相同value的node要被比较好多次,有什么优化可以改进时间的吗
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-12 15:10:15 | 显示全部楼层
LZ 能说说round 1的game of life 的扩展怎么解吗? 感觉用hadoop也没办法解决分割boundary 的问题?
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-12 15:37:10 | 显示全部楼层
lfenjoy9 发表于 2016-1-12 01:20
我用Java的类似hashCode的方法根据左节点和右节点的hash,本节点的值来计算本节点的值

后来讨论hash函 ...


hashcode 因该是没有办法uniquely 辨认object 还是这边的object是node的value 相等就当作相等? 还是有更好的方法?
回复 支持 反对

使用道具 举报

Thrice 发表于 2016-1-14 13:15:08 | 显示全部楼层
say543 发表于 2016-1-12 15:37
hashcode 因该是没有办法uniquely 辨认object 还是这边的object是node的value 相等就当作相等? 还是有 ...

是没有办法uniquely辨认,所以还要比一遍,但是可以过滤掉很多肯定不相等的subtree。像bloom filter一样。
看楼主的回答,hash function应该是能加进去越多元素(root value, left /right child value, height, number of descendants) 越好。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-25 08:41:26 | 显示全部楼层
请问楼主说的game of life 用mapreduce是说将matrix 分成一块一块,然后reduce考虑边界?. 鍥磋鎴戜滑@1point 3 acres
HTML比较是建立Node:
class Node {
                String name;
                String value;
                Map<String, Node> map;

                public Node(String name) {
                        this.name = name;
                        this.value = ""; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        map = new HashMap<String, Node>();
                }
        }
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-25 08:43:43 | 显示全部楼层
Round four是用hashmap<Integer, HashSet<TreeNode>> 解决吧,key是value,然后比较,时间复杂度是O(n^ 3)?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-25 05:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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