《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 3748|回复: 16
收起左侧

Dec 15 NY Google Onsite

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

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

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

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

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)
2 Range Sum Query 2D - Mutable  (Leetcode).鏈枃鍘熷垱鑷1point3acres璁哄潧
用 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. From 1point 3acres bbs
考官不满意,然后写个Iterator,用Iterators进行比较

Round Four

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

Round Five (System Design)
- How to design Google Search Suggestion. Waral 鍗氬鏈夋洿澶氭枃绔,

HC passed and sent ot executive committee
求bless

评分

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 ...
. visit 1point3acres.com for more.
顺序要相同

优化我指的是避免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
. Waral 鍗氬鏈夋洿澶氭枃绔,我用Java的类似hashCode的方法根据左节点和右节点的hash,本节点的值来计算本节点的值. visit 1point3acres.com for more.
.1point3acres缃
后来讨论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考虑边界?
HTML比较是建立Node:
class Node {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                String name;
                String value;
. more info on 1point3acres.com                Map<String, Node> map;.鏈枃鍘熷垱鑷1point3acres璁哄潧

                public Node(String name) {
                        this.name = name;
                        this.value = "";
. visit 1point3acres.com for more.                        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-11-24 14:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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