一亩三分地论坛

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

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

G家onsite,PhD, full-time

[复制链接] |试试Instant~ |关注本帖
rhett.lhy 发表于 2015-10-7 00:52:29 | 显示全部楼层 |阅读模式

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

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

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

x
G家onsite面经, PhD, full-time

第一轮: 一个排好序的长度为n的数组,最多只有一个数出现了超过n/4次,找出这个数

第二轮: (题目忘了不好意思……)

第三轮: PhD thesis discussion
. 鍥磋鎴戜滑@1point 3 acres
第四轮:乱序数组找top K。用merge sort找top K。数组分别存在很多个机器上找top K。2D matrix search (leetcode 原题)

第五轮:检查一个BST是不是valid
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感觉题目都挺无聊的……没有问任何design方面的题。. from: 1point3acres.com/bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
大米 ^_^

评分

3

查看全部评分

本帖被以下淘专辑推荐:

sc.77885 发表于 2015-10-7 01:04:35 | 显示全部楼层
请问LZ,2d matrix search具体哪道啊?
回复 支持 反对

使用道具 举报

头像被屏蔽
bitware 发表于 2015-10-7 01:34:51 来自手机 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-10-7 03:54:33 | 显示全部楼层
请问lz数组分别存在很多个机器上找top K怎么做的
回复 支持 反对

使用道具 举报

tomdarling 发表于 2015-10-7 20:56:06 | 显示全部楼层
请问楼主是在哪里onsite的呢
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-7 21:33:38 | 显示全部楼层
多个机器上找topk这个题,思路是不是,现在每台机器上找topk,然后在每个机器的topk中再找topk?找topk的算法可以用quick selection,请问lz怎么答的?这样的题目在面试中需要回答的多深呢?
回复 支持 反对

使用道具 举报

hdy0616 发表于 2015-10-7 22:03:59 | 显示全部楼层
求问第一题的思路,谢谢
回复 支持 反对

使用道具 举报

saberkun 发表于 2015-10-7 23:58:38 | 显示全部楼层
求问第一题n/4frequent怎么做?
回复 支持 反对

使用道具 举报

wxr.dal 发表于 2015-10-9 11:22:06 | 显示全部楼层
同求第一题思路
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-29 08:57:18 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-7 21:33. more info on 1point3acres.com
多个机器上找topk这个题,思路是不是,现在每台机器上找topk,然后在每个机器的topk中再找topk?找topk的算 ...

万一每台机器上也有1但是不多,排不进那些机器的top K,结果就不对了吧。。感觉还是得先统计出所有机器上相同数字的个数。。。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-29 09:21:03 | 显示全部楼层
hj867955629 发表于 2015-10-29 08:57
万一每台机器上也有1但是不多,排不进那些机器的top K,结果就不对了吧。。感觉还是得先统计出所有机器上 ...

嗯嗯,是的,这样结果就不对了。仔细想想,可能是考mapreduce,先map到不同的机器上,这样可以保证相同的元素会被map进同一个机器,然后再每个机器机器找top k,然后再合起来找top k
回复 支持 反对

使用道具 举报

djjkobe 发表于 2015-10-29 09:51:18 | 显示全部楼层
第一题O(logn)的方法怎么做啊?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-29 10:33:46 | 显示全部楼层
djjkobe 发表于 2015-10-29 09:51
第一题O(logn)的方法怎么做啊?

分别在0, n/4, n/2, n/3处找到4个候选数字,然后做四次二分搜索

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

djjkobe 发表于 2015-10-29 11:53:23 | 显示全部楼层
hj867955629 发表于 2015-10-29 10:33
分别在0, n/4, n/2, n/3处找到4个候选数字,然后做四次二分搜索

. 1point3acres.com/bbs应该是0, n/4, n/2和3n/4吧。。之后二分法怎么做? 比如1,2,3,3,3,4,5,8,9,10,11,12   拿到1,3,5,10这四个点后怎么二分搜索?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-29 11:58:47 | 显示全部楼层
djjkobe 发表于 2015-10-29 11:53. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
应该是0, n/4, n/2和3n/4吧。。之后二分法怎么做? 比如1,2,3,3,3,4,5,8,9,10,11,12   拿到1 ...

对,笔误。。。然后search target number,一次搜左边界,一次搜右边界,得到长度

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

superxiaoding 发表于 2015-11-1 07:50:31 | 显示全部楼层
想问楼主乱序数组top k要怎么找?如果不能counting sort的话?

谢谢!
回复 支持 反对

使用道具 举报

bensvage1989 发表于 2015-11-1 10:35:06 | 显示全部楼层
hj867955629 发表于 2015-10-29 11:58. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
对,笔误。。。然后search target number,一次搜左边界,一次搜右边界,得到长度

后面的没明白,search target number, 搜左边界,有边界,怎么得出长度。。。
求讲解
回复 支持 反对

使用道具 举报

dustinzeng 发表于 2015-11-1 10:55:14 | 显示全部楼层
请问楼主面的是啥职位?
回复 支持 反对

使用道具 举报

 楼主| rhett.lhy 发表于 2015-11-1 23:40:28 | 显示全部楼层
dustinzeng 发表于 2015-11-1 10:55
请问楼主面的是啥职位?

software engineer
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-2 03:14:33 | 显示全部楼层
bensvage1989 发表于 2015-11-1 10:35
后面的没明白,search target number, 搜左边界,有边界,怎么得出长度。。。
求讲解

它是sort的呀,所以右边界减掉左边界再加1就是这个值的个数了呀
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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