一亩三分地论坛

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

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

google电面

[复制链接] |试试Instant~ |关注本帖
SiyaoZhu 发表于 2016-11-5 04:45:42 | 显示全部楼层 |阅读模式

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

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

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

x
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
判断toeplitz maxtrix, follow up 是矩阵很大怎么办。。听面试官的介绍应该要问很多题的。。可能时间不够或是我太水了吧。。
面试官貌似在机场,各种噪声,电话还莫名断了好几次,上来发现我俩进的还不是一个google doc耽误了好久好久。。
求onsite。。求大米。。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

crir 发表于 2016-11-6 11:23:48 | 显示全部楼层
求问矩阵很大怎么办?
回复 支持 反对

使用道具 举报

 楼主| SiyaoZhu 发表于 2016-11-6 14:15:37 | 显示全部楼层
crir 发表于 2016-11-6 11:23
求问矩阵很大怎么办?

我说的是分成几块然后记录边界的值
回复 支持 反对

使用道具 举报

123呆板彻底 发表于 2016-11-9 03:27:51 | 显示全部楼层
矩阵很大的话一行一行读就可以了
只要判断i行和i+1行关系就行了
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-11-9 06:55:42 | 显示全部楼层
123呆板彻底 发表于 2016-11-9 03:27
矩阵很大的话一行一行读就可以了
只要判断i行和i+1行关系就行了

不懂 能麻烦详细说说嘛?~ 这样和直接找对角线有什么区别呢? 复杂度有差嘛?0.0.。。。。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-11-9 06:58:35 | 显示全部楼层
SiyaoZhu 发表于 2016-11-6 14:15
.鐣欏璁哄潧-涓浜-涓夊垎鍦我说的是分成几块然后记录边界的值

楼主没有明白 求讲解
回复 支持 反对

使用道具 举报

 楼主| SiyaoZhu 发表于 2016-11-9 07:45:01 | 显示全部楼层
何打发123 发表于 2016-11-9 06:58
楼主没有明白 求讲解

啊应该就一部分一部分load这个矩阵 然后把最下面和最右边的一列记下来就行了,楼上的那个同学讲的对的
. more info on 1point3acres.com
面试官说了也可能矩阵大到只能load一行的一部分

复杂度的话虽然都是O(mn),但是最好尽可能减少那个常数项 他说的是seek time
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-11-9 08:25:01 | 显示全部楼层
SiyaoZhu 发表于 2016-11-9 07:45
啊应该就一部分一部分load这个矩阵 然后把最下面和最右边的一列记下来就行了,楼上的那个同学讲的对的-google 1point3acres

...

哦明白了!! 感谢你!
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-10 06:39:31 | 显示全部楼层
SiyaoZhu 发表于 2016-11-9 07:45
啊应该就一部分一部分load这个矩阵 然后把最下面和最右边的一列记下来就行了,楼上的那个同学讲的对的

...

请问一下对于Matrix (M*N)特别大的情况,例如每次只能load k个元素(按global index一行一行的load),不到一行。那么这个题对于内存有没有限制?就是说内存够不够存O(M+N)个值呢?因为toeplitz matrix的自由度就是长和宽的M+N-1个值。
若内存也只有O(k),k远远小于O(M+N)的话,那么就只能先比较宽度为k的相邻k个对角线,这样就会多次调用load来获取合适位置的matrix values,那么时间复杂度就会很高,但这也是space vs time的trade-off吧。
回复 支持 反对

使用道具 举报

 楼主| SiyaoZhu 发表于 2016-11-10 08:42:38 | 显示全部楼层
zzgzzm 发表于 2016-11-10 06:39
请问一下对于Matrix (M*N)特别大的情况,例如每次只能load k个元素(按global index一行一行的load), ...

额面试官木有说的这么详细
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我觉得他的意思就是想只要比较一个元素和他右下方元素的大小就行了

因为他有说过不能精确定位到一个点。。别想太复杂啦= =
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-12-3 15:45:39 | 显示全部楼层
问一下。判断是不是Toeplitz matrix肯定是O(mn)吧?
回复 支持 反对

使用道具 举报

wkvictor 发表于 7 天前 | 显示全部楼层
cgxy1991 发表于 2016-12-3 15:45
问一下。判断是不是Toeplitz matrix肯定是O(mn)吧?

感觉是的,矩阵的每个元素都访问一遍就是O(mn)了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 20:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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