一亩三分地论坛

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

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

Dec 15 NY Google Onsite

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

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

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

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

x
回报地里,圣诞节前的一个星期在NY面的

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). 1point 3acres 璁哄潧
2 Range Sum Query 2D - Mutable  (Leetcode)
用 Binary Indexed Tree.鏈枃鍘熷垱鑷1point3acres璁哄潧
. From 1point 3acres bbs
Round Three

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进行比较

Round Four. Waral 鍗氬鏈夋洿澶氭枃绔,

1. Given a binary tree, find all duplicate subtrees . 1point3acres.com/bbs
后序访问树,计算每个节点的Hash并且保存在一个HashMap里,. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果有相同的Hash,需要进行比较确认后
然后讨论怎么样计算Hash和一些优化

Round Five (System Design). From 1point 3acres bbs
- How to design Google Search Suggestion
. more info on 1point3acres.com
HC passed and sent ot executive committee
求bless
. 鍥磋鎴戜滑@1point 3 acres

评分

5

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

wtcupup 发表于 2016-1-11 10:20:24 | 显示全部楼层
Round 4那道是经典的难题
回复 支持 反对

使用道具 举报

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

使用道具 举报

tbian 发表于 2016-1-11 11:55:13 | 显示全部楼层
这些问题都不懂诶
回复 支持 反对

使用道具 举报

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,本节点的值来计算本节点的值
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
后来讨论hash函数时,提到可以加入左右节点的高度和节点个数等因素,. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

回复 支持 反对

使用道具 举报

 楼主| lfenjoy9 发表于 2016-1-12 01:24:25 来自手机 | 显示全部楼层
say543 发表于 2016-1-11 15:07
能说说round 3的HTML 同一个level elements 如果顺序不同要考虑吗? 另外round 4 可以有哪些优化? 感觉hashM ...

顺序要相同

优化我指的是避免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函 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧

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一样。. 1point3acres.com/bbs
看楼主的回答,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考虑边界?
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>();. from: 1point3acres.com/bbs
                }
        }
回复 支持 反对

使用道具 举报

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, 2016-12-6 04:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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