谷歌onsite面经

wing0315 发表于 2020-2-7 10:37
所有节点都在同时发送和接收消息，而且节点自己只知道和它相邻有哪些节点，不知道整个图有一共有哪些节点 ...

请问一下这个send和receive都是async的是吧？

joetan2018 发表于 2020-2-7 22:58
请问一下这个send和receive都是async的是吧？

可以是async也可以是sync，这就是为什么我说讨论了两种做法，写了一种。

yangmyfly 发表于 2020-2-7 17:23
你要去掉还要维护一个size k的deque？

deque是要的，至少要维护这个滑动窗口里面的数字咯

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

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

wing0315 发表于 2020-2-7 23:15
可以是async也可以是sync，这就是为什么我说讨论了两种做法，写了一种。

求问async的话应该怎么去重

joetan2018 发表于 2020-2-7 23:36
求问async的话应该怎么去重

我仔细回忆了一下应该是每个node有uid，你可以看看下面这个slide，有介绍大概的做法。

https://www.inf.ed.ac.uk/teachin ... asic-algos.pptx.pdf

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

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

yangmyfly 发表于 2020-2-8 07:37
确实flood不用发送整张map，存下map，只转发之前没见过的nodeid的message和自己的或者timestamp更新的就好 ...

个人感觉应该可以吧，分布式系统里面有环还是挺常见的

wing0315 发表于 2020/02/07 23:28:03

你是说把这个map counter放在message里面互相传输吗？按我的理解因为每个node其实都是一样的，所以你...

觉得follow up他可能想问SWIM

第四题lz可以大致说一下时间复和空间复杂度优化的方法分别是什么吗？谢谢!