G家onsite跪经

二月底G家onsite面试，已跪。
第一轮：第一题，python，给float数的一个list，求平均数。第二题，自己设计数据结构，插入（键，值，有效时长），查询键返回值，更新（键，值，有效时长）。给curre

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

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

认面试官知道算法，一定先和他讲原理，再用。所以复杂的算法应该先想想怎么能几句话讲清楚。
4. 保持一个开心的态度。

第二轮能预先处理数据么 如果可以的话 用一个map<int, set<int>> 来保存矩阵里的点

map的key是横坐标 set 里是 横坐标对应的点的纵坐标的集合

对于找一个从（a,b）到（c,d）的矩形  因为map是排序的 所以 找a和b都用得是O(log N) 的复杂度 同样 在 set里找 c和d之间的点 也是 O(log N) 的复杂度 这样 查找的复杂度就变成了 O(  (log N + k)^2  ) k是 a到b之间 有效的横坐标个数  当矩阵足够稀疏 那可以近似看成  O(log^2 N)

wtcupup 发表于 2018-3-19 11:54
能说下第二轮正确的解法吗？

和面试官讨论的是建一个Dictionary，{Xa:[Y1,Y2], Xb:[Y3]...}, 对每个X建一个segment tree，把X们另排序成一个list，用BST维护新增X的排序。

第二轮感觉就是 Range Sum Query 2D - Immutable ？
第三轮类似 LC 721. Accounts Merge 的union find吗？

楼主是hc跪的吗，hr有告诉你每轮的feedback吗？

wtcupup 发表于 2018-3-19 10:12
第二轮感觉就是 Range Sum Query 2D - Immutable ？
第三轮类似 LC 721. Accounts Merge 的union find吗 ...

第二轮不是，board非常大，不能直接存成矩阵，存成矩阵也要是稀疏矩阵。第三轮，是比较类似这题的。

xxtxdy 发表于 2018-3-19 11:09
楼主是hc跪的吗，hr有告诉你每轮的feedback吗？

并没有

CjnJune 发表于 2018-3-19 11:30
第二轮不是，board非常大，不能直接存成矩阵，存成矩阵也要是稀疏矩阵。第三轮，是比较类似这题的。

能说下第二轮正确的解法吗？

送到hc了么