谷歌一日游

Linzertorte 发表于 2014-4-2 12:01
第二面如果楼主学过一定的容斥原理就好了。
主要就是记录部分和  sum= A[0,0]+A[0,1]...A[0,j]+A[1,0]+A[1 ...

第二个题目：
第二面中国人。给个n乘n矩阵，写set和getSum (of a sub-matrix)。本来写这个也不难吧结果handling error的时候不太记得java的try/catch怎么写了（快一年没怎么用过java了泪千行……然后问时间复杂度，然后说给我一个large memory怎么能够让getSum的时间复杂度变为O(1)。。。想不出来问了提示，然后他就提示了一句"the memory is really huge"我就有点懂了，先是说把所有sub-matrix都存到memory里头。然后问空间复杂度，我就当场一个一个把这个矩阵有多少个sub matrix给手算出来了，然后听到面试官夸我your maths is impressive!!! 然后又问我如何在时间复杂度还是O(1)的情况下减少空间复杂度。。。然后我就扑街了。。。

这个到底什么意思，写set和getsum什么意思，是dp那个求得最大的矩阵的和吗？

shire1989 发表于 2014-5-9 05:45
第二个题目：
第二面中国人。给个n乘n矩阵，写set和getSum (of a sub-matrix)。本来写这个也不难吧结果h ...

你去查查“二维树状数组”

Linzertorte 发表于 2014-5-9 06:23
你去查查“二维树状数组”

你之前提到容斥原理，也是二维树状数组问题吗

shire1989 发表于 2014-5-9 07:01
你之前提到容斥原理，也是二维树状数组问题吗

没有那么复杂，就是个二维前缀和。
你自己画图直接就看出来了

8*8棋盘那题挺经典的，把棋盘染色以后就会发现有一半格子永远走不到，转45度会发现与你颜色相同的格子就是一个矩阵，所以2步内必走到

renli3000 发表于 2014-7-17 09:56
8*8棋盘那题挺经典的，把棋盘染色以后就会发现有一半格子永远走不到，转45度会发现与你颜色相同的格子就是 ...

至于判断颜色，横纵坐标的差值的和判断奇偶即可，然后判断1步还是2步，判断一下横纵坐标差是否相等就可以了

renli3000 发表于 2014-7-17 10:02
至于判断颜色，横纵坐标的差值的和判断奇偶即可，然后判断1步还是2步，判断一下横纵坐标差是否相等就可以 ...

求题目链接

CTCR第九章第七题的一个变种（写一个算法让机器人清扫房间），于是我第一反应就是递归，解释了几句她懂了
这是什么题？

lz怎么花了一千刀啊，感觉晚饭机票也才500刀左右啊

xanadulord 发表于 2015-5-30 04:02
lz怎么花了一千刀啊，感觉晚饭机票也才500刀左右啊

写错，往返机票