发个谷歌跪经吧，onsite

提供一个第三题建图的思路：

假设待求矩形是A (m * n), 第i行第j列的元素是Aij, 第x行之和为Rx, 第y行之和为Cy.

对于Graph API，输入是node val输出是edge val  而题目的输入是R和C，输出是A，因此考虑用R和C表示node val，用edge val表示A。

由于Graph满足等式  IN + node = OUT 可以变形为node = OUT - IN. 对于矩阵 我们可以写出类似方程式：

Aij + (Ri - Aij) = Ri  and Aij + (Cj - Aij) = Cj  两者联立可以推出 Ri - Cj = (Ri - Aij) + (Cj - Aij) = (Ai1 + Ai2 +... + Aij-1 + Aij+1 +... + Ain) - (A1j + A2j + ... + Ai-1j + Ai+1j + ... + Amj)

因此，可以设法令 node = Ri - Cj , 入边 = Ai1 Ai2 ...   Aij-1  Aij+1 ... Ain （同行） 出边 = A1j  A2j ...  Ai-1j  Ai+1j  ...  Amj （同列）即使用下面的规则建图：

1. 对于矩阵的每一个元素Aij, 建立一个节点并设置节点值为 Ri - Cj
2. 对于矩阵的每一个元素，建立一条从它到它同行元素 （不包括自己）对应节点的边 （OUT）
3. 对于矩阵的每一个元素，建立一条从它同列元素（不包括自己）到它自己的边 （IN）

使用面试官提供的Graph API计算边的值，Aij = 任意一个指向Aij对应节点的边

补充内容 (2018-3-12 06:13):
出边 = Ai1 Ai2 ...   Aij-1  Aij+1 ... Ain （同行） 入边 = A1j  A2j ...  Ai-1j  Ai+1j  ...  Amj （同列）

Kwang100 发表于 2018-3-12 03:46
安慰一下楼主先...有几个问题想问下楼主..
第二轮有让实现hash heap吗？还是只要写普通的堆？
第三轮没太 ...

第四题没太想明白为什么要用lru。 可以直接存过期时间 -》 task的map吗？每一毫秒检查下不可以吗。  

楼主 可以告知下，你几年工作经验吗？

hyliu0000 发表于 2018-3-15 11:38
楼主 可以告知下，你几年工作经验吗？

算起来不到一年

jq0215 发表于 2018-3-15 23:58
算起来不到一年

继续加油 楼主 还有好多机会。 不过尽量准备好再面。 听说谷歌只准许fail3次onsite对于同一种职位

hyliu0000 发表于 2018-3-15 11:38
第四题没太想明白为什么要用lru。 可以直接存过期时间 -》 task的map吗？每一毫秒检查下不可以吗。

好像确实是...我可能是看到楼主说用heap，才觉得需要排序...但是从目前这个描述来看，好像并不需要都排序。

hyliu0000 发表于 2018-3-15 11:38
第四题没太想明白为什么要用lru。 可以直接存过期时间 -》 task的map吗？每一毫秒检查下不可以吗。

感觉还是list灵活一些吧？万一1ms太频繁，要100ms检查一下怎么办？

ohshout 发表于 2018-3-16 22:37
感觉还是list灵活一些吧？万一1ms太频繁，要100ms检查一下怎么办？

list灵活一些什么意思？ 能详细说说你的design吗？ 1ms哪里频繁了？ 就算你要100ms检查也没问题啊。 时间存储的精确度可以改变。。 不明白你的意思

hyliu0000 发表于 2018-3-17 00:11
list灵活一些什么意思？ 能详细说说你的design吗？ 1ms哪里频繁了？ 就算你要100ms检查也没问题啊。 时间 ...

你是对的，想了下，list完全不行，还不如priority_queue

hyliu0000 发表于 2018-3-16 00:31
继续加油 楼主 还有好多机会。 不过尽量准备好再面。 听说谷歌只准许fail3次onsite对于同一种职位

哈，我之前听说的是10次