谷歌 VO

發個面經，求個大米

首先，不得不說，谷歌的題都滿活的，可能都是有看過的概念，但以全新的方式呈現

面的是L5, 所以有一輪System design

Coding 1:
概念就是Splitwise, 要求實現add_debt(creditor, debtor, amount) and get_debt(creditor, debtor)
get_debt() 如果有互欠的情況要抵消掉，有個edge case就是cycle, Alice (欠$10) -> Bob (欠$10) -> Carol (欠$10) -> Alice, 也要抵銷掉

GPaySplits
You’re developing a new feature that will allow groups of users to keep track of shared IOUs and debts.

Example 1
Alice

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

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

ween the two trees.
2. Extension: thinking if you want to run your function on a machine with limit memory, and the trees are really large to fit into the memory.[it is too wide to fit into the memory but depth is ok.]

BQ:
聊天

分享了這麼多，只求看官加個米，救救看不到文章的小弟

coding 1: leetcode 465

第一题蠡口465 hard

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

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

请问楼主能不能讲一下第一个coding的思路， 是每次加都要寻找cycle吗？那这样复杂度还挺高的？
第三个coding 的followup是sharding 然后aggregate吗？

第一题这种情况也要抵消吗：
a欠b 20， b欠c d 10，c d欠a 10
要把abcd之间的欠债全都抵消吗

asss 发表于 2021-7-9 13:47
第一题这种情况也要抵消吗：
a欠b 20， b欠c d 10，c d欠a 10
要把abcd之间的欠债全都抵消吗

也要，相當於兩個circle，我當下也只能暴力解了。。。

匿名者 发表于 2021-7-9 14:55
我當下也只能想得到這方法了，應該可以再optimize
第三題其實我沒做到那個follow up, 因為面試官引導到 ...

楼主有什么optimize的思路吗, 我好像还暂时没想到

想请教楼主coding2: 是要用minimum spanning tree做吗？

对于那个System design的题目，楼主的解法可以分享下吗？

creditor不是债权人么？Alice pays $30 bill for Alice, Bob, Carol     # AddDebt(Bob, Alice, 10), AddDebt(Carol, Alice, 10) 不该是addDebt( Alice, Bob, 10)还是我理解哪里错了