google电面

判断toeplitz maxtrix, follow up 是矩

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

久好久。。
求onsite。。求大米。。

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吧。

zzgzzm 发表于 2016-11-10 06:39
请问一下对于Matrix （M*N）特别大的情况，例如每次只能load k个元素（按global index一行一行的load）， ...

额面试官木有说的这么详细

我觉得他的意思就是想只要比较一个元素和他右下方元素的大小就行了

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

何打发123 发表于 2016-11-9 06:58
楼主没有明白 求讲解

啊应该就一部分一部分load这个矩阵 然后把最下面和最右边的一列记下来就行了,楼上的那个同学讲的对的

面试官说了也可能矩阵大到只能load一行的一部分

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

求问矩阵很大怎么办？

crir 发表于 2016-11-6 11:23
求问矩阵很大怎么办？

我说的是分成几块然后记录边界的值

矩阵很大的话一行一行读就可以了
只要判断i行和i+1行关系就行了

123呆板彻底 发表于 2016-11-9 03:27
矩阵很大的话一行一行读就可以了
只要判断i行和i+1行关系就行了

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

SiyaoZhu 发表于 2016-11-6 14:15
我说的是分成几块然后记录边界的值

楼主没有明白 求讲解

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

...

哦明白了！！ 感谢你！