狗家onsite面经

wtcupup 发表于 2018-8-17 12:36
请问第一轮 follow up f【i】【j】【k】, k 是指什么呢？

从起始点开始，到达点(i, j) 并且已经经过了第k个要求高度但是还未经过第k+1个要求高度的路径数量。

您好！
本帖隐藏的内容需要积分高于 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

szyyn95 发表于 2018-8-17 05:10
请问一下，第一题的第二问，在做完Prefix sum之后怎么做O(1)的查询？难道是用类似TreeSet保存prefix sum吗

时间轴范围给的不大 0..65535。直接开个prefixSum数组存就行了

jeffztn0816 发表于 2018-8-17 14:48
从起始点开始，到达点(i, j) 并且已经经过了第k个要求高度但是还未经过第k+1个要求高度的路径数量。

所以要是用 三层for loop populate这个三维dp吗
for(int i = 1 ; i<=k; k++) 放在最外层 ？

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

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

wtcupup 发表于 2018-8-17 14:57
所以要是用 三层for loop populate这个三维dp吗
for(int i = 1 ; i

无所谓。里外都ok，只要是0 to k别是k downto 0就行。

jeffztn0816 发表于 2018-8-17 14:49
暴力iterate，每次查询是O(n)的。线段数每次查询是O(logn)的。

补充内容 (2018-8-17 14:54):

Sorry 一个typo。查询是O(logn) 树的高度

jeffztn0816 发表于 2018-8-17 14:51
对于每个区间，在区间的开始点打加1 tag，在结束点打-1 tag。
然后这样的话做前缀和之后，prefixSum就是 ...

懂了，多谢

感谢分享面经