推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

Dec 15 NY Google Onsite

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

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

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

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

x
回报地里,圣诞节前的一个星期在NY面的
. 1point3acres.com/bbs
Round one:
1. Game of Life (Leetcode). From 1point 3acres bbs
Follow up: how to scale if the board has 1 million rows and columns. visit 1point3acres.com for more.
用MapReduce. 鍥磋鎴戜滑@1point 3 acres

Round two:
1. Gate and Wall (Leetcode)
2 Range Sum Query 2D - Mutable  (Leetcode). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
用 Binary Indexed Tree
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
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进行比较
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Round Four 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

1. Given a binary tree, find all duplicate subtrees
后序访问树,计算每个节点的Hash并且保存在一个HashMap里,. 鍥磋鎴戜滑@1point 3 acres
如果有相同的Hash,需要进行比较确认后. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
然后讨论怎么样计算Hash和一些优化. visit 1point3acres.com for more.

Round Five (System Design). more info on 1point3acres.com
- How to design Google Search Suggestion

HC passed and sent ot executive committee . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
求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 | 显示全部楼层
这些问题都不懂诶
回复 支持 反对

使用道具 举报

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. 1point3acres.com/bbs
lz你这个面的好难啊。。是有很多年experience吗?能请教下round four的hash具体是怎么算的?对descendant的 ...

我用Java的类似hashCode的方法根据左节点和右节点的hash,本节点的值来计算本节点的值

后来讨论hash函数时,提到可以加入左右节点的高度和节点个数等因素,
.1point3acres缃
回复 支持 反对

使用道具 举报

 楼主| 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函 ...
. from: 1point3acres.com/bbs

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考虑边界?.鏈枃鍘熷垱鑷1point3acres璁哄潧
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)?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-28 17:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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