一亩三分地论坛

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

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

Google电面

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

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

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

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

x
今天早晨电面,上来啥都不说,直接写code,简单粗暴
1. Does artice contains words
参数是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):. From 1point 3acres bbs
        row, col = len(matrix), len(matrix[0])       
        if row*col < k:
                return []
        heap = []
        results = []
        for i in xrange(col):-google 1point3acres
                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
        return results. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2016-1-6 12:49):.1point3acres缃
如果minheap上最小的一个数“大于”idx指针指向的那个数, typo。。。
回复 支持 反对

使用道具 举报

269644943 发表于 2016-1-6 12:28:21 | 显示全部楼层
jmnjmnjmn 发表于 2016-1-6 09:14. more info on 1point3acres.com
对第一列或者第一行push进minHeap,依次pop出K个最小数,一边pop一边加入pop出的那个位置的下一个元素
复 ...

如何确定pop出数的下一个位置? 如果含有重复的数呢?
. From 1point 3acres bbs
我的想法是: 建一个maxheap(求最小k个得用maxheap, 求最大k个用minheap), 从第一行开始push, 第二行,第三行,......直到maxheap里面有k个数。 然后继续扫。 复杂度: mnlogK.. 鍥磋鎴戜滑@1point 3 acres

回复 支持 反对

使用道具 举报

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

我觉得斜着撸是不是也可以。。?
回复 支持 反对

使用道具 举报

asura23 发表于 2016-1-6 14:02:17 | 显示全部楼层
emmarong 发表于 2016-1-6 12:27. 1point3acres.com/bbs
顶二楼,先把第一行加到一个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 ...

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个,所以 ...

还是不太懂,能详细讲解下吗. 鍥磋鎴戜滑@1point 3 acres
回复 支持 反对

使用道具 举报

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。可不可以内推一下?
. From 1point 3acres bbs
我是昨天发的时候刚刚做的电面,并木有办法内推啊~
回复 支持 反对

使用道具 举报

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

不同意。我认为 “斜着” 是更自然的作法。. Waral 鍗氬鏈夋洿澶氭枃绔,
这里的斜着不是指沿着对角线走,而是说:
先把左上角的元素push进pq,然后开始pop,每次pop一个node后,都把它右边和下边的元素push进pq,
(注意这样需要一个额外的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是自己选日子的,所以看你自己咯
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 00:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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