狗家现场表演

狗家新鲜面经虽然准备的不够充分，但是🐶的面试官给人整体的感觉都很好，题都很灵活，倾向于先口头把问题和想法说清楚再写code，没有冷场，更像是在peer programming

1. coding. 1~n n个数 和 一个prime p，求n个数中除去所有的p的multiplers的剩下的数之和。脱口而出暴力解，被要求优化；然后用了求和公式，不知道这样算不算过；follow-up: 求有两个prime number的情况下的和.  需要考虑两个prime的倍数有相同的情况。 也是先暴力解，然后优化

2. BQ: 问了conflict， inspire， work with ambiguious

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

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

g。一开始用hashmap存，每次处理log时，check hashmap里面的entry，如果violate 或者 end，remove entry。但是如果很多RPC都没有end，hashmap会越来越大，不行；后来想了queue和hashset，还是有问题，最后发现面试官要的是linkedlist，但是删除已经end的log还是需要O(n)，最后时间来不及了，这个问题一直没想清楚，求大神指点

Hongjie1 发表于 2022-02-10 16:09:24
感觉还要再判断一下p是不是q的倍数? 或者q 是不是p的倍数

题目好像是说prime，所以应该不用吧。不过若木有这个条件的话，应该注意一下

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

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

求问 第四题的dfs的时间复杂度是多少呢？

第五题如果是担心没有end的log导致了数据变大，那么也许可以用一个hashmap外加一个PQ？ map依旧是 id - time， pq按照time排序，时间越小点在heap top， 来一个log就看pq要不要pop… pop出去的在map里也顺便delete entry…
logn的时间复杂度

ND0406 发表于 2022-02-06 23:26:10
求问 第四题的dfs的时间复杂度是多少呢？

我觉得是n^2. 当时没来得及问

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

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

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

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

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

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

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

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

第一题的话，先求出1-n的和（求和公式，O(1)时间），然后再求出所有p的倍数的和，两者相减吧。
follow up的话，先求出总和S1，再求出所有p的倍数和S2，再求出q的倍数和S3，然后就是p*q的倍数和S4，结果应该是S1-S2-S3+S4，每一步感觉都是O(1)。

第五题 log里面的entry是已经按timestamp排序了吗