没结婚也能买房啊!大波士顿地区买房小tips

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 3589|回复: 19
收起左侧

Google电面

[复制链接] |试试Instant~ |关注本帖
yummy1221 发表于 2016-1-6 08:18:22 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
今天早晨电面,上来啥都不说,直接写code,简单粗暴. more info on 1point3acres.com
1. Does artice contains words. from: 1point3acres.com/bbs
参数是2个list of string,判断list A里面所有出现的string的次数要小于等于list B的,第一题蛮简单

2. 类似leetcode 240, 不过求的是最小的k个数,兰后,我就写了个brute force... 纠结了几分钟,实在是想不粗来,肿么做。。。就介么自暴自弃了
剩下将近20min都在看小哥引导我想出更好的方法T_T,小哥是个一听声音,就觉得很帅的米国小哥,无奈自己太笨了T_T

评分

1

查看全部评分

jmnjmnjmn 发表于 2016-1-6 09:14:45 | 显示全部楼层
对第一列或者第一行push进minHeap,依次pop出K个最小数,一边pop一边加入pop出的那个位置的下一个元素
复杂度是KLog(Min(M,N,K))
回复 支持 反对

使用道具 举报

 楼主| yummy1221 发表于 2016-1-6 10:04:28 | 显示全部楼层
jmnjmnjmn 发表于 2016-1-5 20:14
对第一列或者第一行push进minHeap,依次pop出K个最小数,一边pop一边加入pop出的那个位置的下一个元素
复 ...

是的,小哥的意思就大概这么做
回复 支持 反对

使用道具 举报

emmarong 发表于 2016-1-6 12:27:14 | 显示全部楼层
顶二楼,先把第一行加到一个minheap里面去,用另一个idx指针指到第二行开始处,然后minheap开始pop,如果minheap上最小的一个数小于idx指针指向的那个数,那idx指针那一行都加进去,然后idx指针下一行,直到收集到k个元素。
def findksmallest(self, matrix, k):
        row, col = len(matrix), len(matrix[0])       
        if row*col < k:
                return []
        heap = []
        results = []
. From 1point 3acres bbs        for i in xrange(col):
                heapq.heappush(heap, matrix[0])
        idx = 1
        while len(results) < k:
                results.append(heapq.heappop(heap))
                if idx < col and matrix[idx][0] < heap[0]:
                        for i in xrange(col):
                                heapq.heappush(heap, matrix[idx]). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        idx += 1.鏈枃鍘熷垱鑷1point3acres璁哄潧
        return results

补充内容 (2016-1-6 12:49):.鏈枃鍘熷垱鑷1point3acres璁哄潧
如果minheap上最小的一个数“大于”idx指针指向的那个数, typo。。。
回复 支持 反对

使用道具 举报

269644943 发表于 2016-1-6 12:28:21 | 显示全部楼层
jmnjmnjmn 发表于 2016-1-6 09:14.鏈枃鍘熷垱鑷1point3acres璁哄潧
对第一列或者第一行push进minHeap,依次pop出K个最小数,一边pop一边加入pop出的那个位置的下一个元素. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
复 ...

如何确定pop出数的下一个位置? 如果含有重复的数呢?

我的想法是: 建一个maxheap(求最小k个得用maxheap, 求最大k个用minheap), 从第一行开始push, 第二行,第三行,......直到maxheap里面有k个数。 然后继续扫。 复杂度: mnlogK.

回复 支持 反对

使用道具 举报

kidzlike 发表于 2016-1-6 12:55:55 | 显示全部楼层
jmnjmnjmn 发表于 2016-1-6 09:14
对第一列或者第一行push进minHeap,依次pop出K个最小数,一边pop一边加入pop出的那个位置的下一个元素
复 ...
. 1point 3acres 璁哄潧
我觉得斜着撸是不是也可以。。?
回复 支持 反对

使用道具 举报

asura23 发表于 2016-1-6 14:02:17 | 显示全部楼层
emmarong 发表于 2016-1-6 12:27
顶二楼,先把第一行加到一个minheap里面去,用另一个idx指针指到第二行开始处,然后minheap开始pop,如果mi ...

python不太熟,如果第一行的元素个数大于k的话进不了while吧?
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-1-6 14:09:26 | 显示全部楼层
kidzlike 发表于 2016-1-6 12:55
我觉得斜着撸是不是也可以。。?

斜着可以找某个特定target 前K个的话 还是得heap
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-1-6 14:11:23 | 显示全部楼层
269644943 发表于 2016-1-6 12:28
如何确定pop出数的下一个位置? 如果含有重复的数呢?

我的想法是: 建一个maxheap(求最小k个得用max ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
minHeap每次只进一个就够了,也就是上一个pop出的那个位置相同行(列)的下一个。总共进K个,出K个,所以复杂度只要KLog(Min(M,N,K))
回复 支持 反对

使用道具 举报

269644943 发表于 2016-1-6 14:39:45 | 显示全部楼层
jmnjmnjmn 发表于 2016-1-6 14:11
minHeap每次只进一个就够了,也就是上一个pop出的那个位置相同行(列)的下一个。总共进K个,出K个,所以 ...

还是不太懂,能详细讲解下吗
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-1-6 14:45:51 | 显示全部楼层
269644943 发表于 2016-1-6 14:39
还是不太懂,能详细讲解下吗
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
http://www.jiuzhang.com/solutions/kth-smallest-number-in-sorted-matrix/
回复 支持 反对

使用道具 举报

firemanysome 发表于 2016-1-6 15:02:35 | 显示全部楼层
求楼主的timeline。可不可以内推一下?
回复 支持 反对

使用道具 举报

 楼主| yummy1221 发表于 2016-1-7 04:03:18 | 显示全部楼层
firemanysome 发表于 2016-1-6 02:02
求楼主的timeline。可不可以内推一下?
. more info on 1point3acres.com
我是昨天发的时候刚刚做的电面,并木有办法内推啊~
回复 支持 反对

使用道具 举报

163 发表于 2016-1-7 04:41:29 | 显示全部楼层
jmnjmnjmn 发表于 2016-1-6 14:09
斜着可以找某个特定target 前K个的话 还是得heap

不同意。我认为 “斜着” 是更自然的作法。
这里的斜着不是指沿着对角线走,而是说:
先把左上角的元素push进pq,然后开始pop,每次pop一个node后,都把它右边和下边的元素push进pq,. 1point3acres.com/bbs
(注意这样需要一个额外的set<pair<int, int>>来标记哪些node被push过以防止重复push,不过这个也最多就K log K所以可以无视)
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-1-7 13:05:14 | 显示全部楼层
请问楼主第一题的意思是list a 和 b有一样的单词,然后list a 这些单词出现次数要更少吗?
回复 支持 反对

使用道具 举报

 楼主| yummy1221 发表于 2016-1-7 14:44:31 | 显示全部楼层
ninacc 发表于 2016-1-7 00:05. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
请问楼主第一题的意思是list a 和 b有一样的单词,然后list a 这些单词出现次数要更少吗?

是的。。。
回复 支持 反对

使用道具 举报

michellnum001 发表于 2016-1-8 10:12:43 | 显示全部楼层
请问楼主电面有消息了吗,大概多久能回信呀
回复 支持 反对

使用道具 举报

 楼主| yummy1221 发表于 2016-1-9 00:38:41 | 显示全部楼层
michellnum001 发表于 2016-1-7 21:12
请问楼主电面有消息了吗,大概多久能回信呀

面完第二天早晨就收到onsite通知啦
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-1-9 02:48:42 | 显示全部楼层
yummy1221 发表于 2016-1-9 00:38
面完第二天早晨就收到onsite通知啦

onsite会隔多久啊
回复 支持 反对

使用道具 举报

 楼主| yummy1221 发表于 2016-1-13 09:29:20 | 显示全部楼层

onsite是自己选日子的,所以看你自己咯
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-388663-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-21 08:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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