狗狗实习电面

ningvithle 发表于 2017-11-8 07:50
那我就放心了  不过lz你这两道题都挺简单呀， 没把握住太可惜了

层主对第二题有什么想法么？如果要小于linear time挺tricky的呀。

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

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

qingsong 发表于 2017-11-8 08:29
第二题可以有2种方法吧
1. 把所有区间的点对应的区间数都提前算好，放到map里，然后query的时候直接查询。 ...

第二种方法是可行的，但第一种区间是无限的吧，没法对应啊

calixguo 发表于 2017-11-8 08:32
第二种方法是可行的，但第一种区间是无限的吧，没法对应啊

要是小数精度是一定的话，应该可以吧，比如说[1.0, 1.9] 之间算10个点，查询的输入也只到小数点后一位

qingsong 发表于 2017-11-8 08:36
要是小数精度是一定的话，应该可以吧，比如说[1.0, 1.9] 之间算10个点，查询的输入也只到小数点后一位

嗯嗯，精度确定可以。

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

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

570468837 发表于 2017-11-8 08:17
层主对第二题有什么想法么？如果要小于linear time挺tricky的呀。

不是说了pre processing的可以忽略不计吗 先对左边区间排序  再用binary search 找上下限区间， 中间的全部输出

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

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

qingsong 发表于 2017-11-8 08:29
第二题可以有2种方法吧
1. 把所有区间的点对应的区间数都提前算好，放到map里，然后query的时候直接查询。 ...

方法2找区间数, 然后要怎么继续找所属区间呢?

570468837 发表于 2017-11-8 08:51
请问您说的第二种方法是什么意思啊？没看懂sigh...
比如LZ的例子 [-1.1, 1.0], [-0.5, 3.5], [3.6, 4.0] ...

同没看懂，sign