数据砖电面

面经攒人品～自己海投的～

API:
public int insert(int number) --> 插入一个新的顾客
public int insert(int number, int referralId) --> 插入一个顾客和它的推荐
一个顾客的rev = 自己的rev

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

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

eBelowThreshold(200), return [2, 0]

面试官希望的答案：维持一个客户利润由小到大的数组，插入二分查找，利润小于threshold二分查找。。

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

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

Smilenceyu 发表于 2021-1-16 04:03
你是说每次refer去更新heap里的节点然后shift up或者shift down么

把heap换成treemap(Java)或者map(C++)

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

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

感谢LZ面经！
请问下lz的例子，不是rev below 200吗？为什么会return[2,0]? 不是应该就return 2吗？0的rev不是300？
还想请问下LZ是投的什么岗位呢？LZ 的YOE是5+所以投的是senior的职位吗？
谢谢！

感谢楼主面经，同问getKCustomerRevenueBelowThreshold，既然是要KCustomer那K是一个constant么，还是应该作为参数传进函数？

litJordan 发表于 2021-1-6 06:17
感谢LZ面经！
请问下lz的例子，不是rev below 200吗？为什么会return[2,0]? 不是应该就return 2吗？0的rev ...

是的。我写错了，要返回所有小于200的客户只有2

Fireball 发表于 2021-1-6 07:22
感谢楼主面经，同问getKCustomerRevenueBelowThreshold，既然是要KCustomer那K是一个constant么，还是应该 ...

对，k是一个参数，两个参数一个是threshold 一个是k

hmm 如果是array从小到大的话，虽然找到插入position是lgn，但是真正插入需要O(n) 不是么？感觉没有heap的办法好啊
除非是用balanced BST

不是很懂， 怎么维持客户利润从小到大的数组， 如果每次都二分插入因为涉及移动插入位置之后的所有元素那么big O是n， 除非这个api调用的次数远远大于插入的次数否则这样就是不划算的。

楼主可以把积分调低一点吗？我的分数比较低，加米加米～

我觉得不应该用array或者list, 因为insert反而O(N)

而是用 heap 或者 平衡BST

Smilenceyu 发表于 2021-1-6 09:14
hmm 如果是array从小到大的话，虽然找到插入position是lgn，但是真正插入需要O(n) 不是么？感觉没有heap的 ...

+1  我觉得用heap + map就可以了