狗家onsite面经

请问第一轮 follow up f【i】【j】【k】, k 是指什么呢？

第一题lz能说一下从左往右移动的路径是什么意思么？
第二题能说一下把binary file变成all visible text是什么意思么？

想说一下线段树感觉是用来求区间和的数据结构。感觉这个区间问题好像不是求和，就是求某一点的一个值。那如果要支持区间添加删除操作，我觉得好像还不如直接暴力iterate？

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) 树的高度