楼主: jq0215
跳转到指定楼层
上一主题 下一主题
收起左侧

发个谷歌跪经吧,onsite

🔗
619899442 2018-3-12 06:11:52 | 只看该作者
全局:
提供一个第三题建图的思路:

假设待求矩形是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 (同列)
回复

使用道具 举报

🔗
hyliu0000 2018-3-15 11:38:00 | 只看该作者
全局:
Kwang100 发表于 2018-3-12 03:46
安慰一下楼主先...有几个问题想问下楼主..
第二轮有让实现hash heap吗?还是只要写普通的堆?
第三轮没太 ...

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

使用道具 举报

🔗
hyliu0000 2018-3-15 11:38:55 | 只看该作者
全局:
楼主 可以告知下,你几年工作经验吗?
回复

使用道具 举报

🔗
 楼主| jq0215 2018-3-15 23:58:02 | 只看该作者
全局:
hyliu0000 发表于 2018-3-15 11:38
楼主 可以告知下,你几年工作经验吗?

算起来不到一年
回复

使用道具 举报

🔗
hyliu0000 2018-3-16 00:31:32 | 只看该作者
全局:
jq0215 发表于 2018-3-15 23:58
算起来不到一年

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

使用道具 举报

🔗
Kwang100 2018-3-16 00:51:56 | 只看该作者
全局:
hyliu0000 发表于 2018-3-15 11:38
第四题没太想明白为什么要用lru。 可以直接存过期时间 -》 task的map吗?每一毫秒检查下不可以吗。

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

使用道具 举报

🔗
ohshout 2018-3-16 22:37:56 | 只看该作者
全局:
hyliu0000 发表于 2018-3-15 11:38
第四题没太想明白为什么要用lru。 可以直接存过期时间 -》 task的map吗?每一毫秒检查下不可以吗。

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

使用道具 举报

🔗
hyliu0000 2018-3-17 00:11:56 | 只看该作者
全局:
ohshout 发表于 2018-3-16 22:37
感觉还是list灵活一些吧?万一1ms太频繁,要100ms检查一下怎么办?

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

使用道具 举报

🔗
ohshout 2018-3-17 04:15:27 | 只看该作者
全局:
hyliu0000 发表于 2018-3-17 00:11
list灵活一些什么意思? 能详细说说你的design吗? 1ms哪里频繁了? 就算你要100ms检查也没问题啊。 时间 ...

你是对的,想了下,list完全不行,还不如priority_queue
回复

使用道具 举报

🔗
kimi81017 2018-3-28 14:55:54 | 只看该作者
全局:
hyliu0000 发表于 2018-3-16 00:31
继续加油 楼主 还有好多机会。 不过尽量准备好再面。 听说谷歌只准许fail3次onsite对于同一种职位

哈,我之前听说的是10次
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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