这几个题目怎么做啊# JobHunting - 待字闺中
g*j
1 楼
第一题, 给一个N个node的BST,给一个key,返回与key最接近的m个node(m < N).
最接近的是什么意思? 比如假设树是, 如下,给定3, 最接近的三个
点是 1,2,4啊,还是2,4,5啊
5
3 6
2 4
1
第二题 用一个数组来表示二维数组,但是每一行的元素个数可以不同,实现get,set函
数。 这个题目怎么做的? 是不是需要把每一行的数组的长度保存起来?还是保存那
个前面所有n行的元素的和?
第三题 Given 2D coordinates , find the k points which are closest to the
origin. Propose a data structure for storing the points and the method to
get the k points. Also point out the complexity of the code.
假设就找最近的,可以用kd tree,但是要找k个怎么找呢? 每次把最近的去掉,然后
找k次?这样每次去掉的时候也要修改kd tree吧? 这样时间复杂度是多少? 如果直
接用heap做呢?
第四题 You are given N ranges of date offsets when N employees are present
in an organization. Something like
1-4 (i.e. employee will come on 1st, 2nd, 3rd and 4th day ) 2-6
8-9
..
1-14
You have to organize an event on minimum number of days such that each
employee can attend the event at least twice. Write an algorithm (there is
apparently an O(n) algorithm for this).
请问这里面这个event是必须连续的么?
请问这个O(n) 的算法是什么? 我能够想到的算法是,对所有ending排序,假设最小的
ending是x,然后对所有的start排序,假设最大的start是y,那么这个minimumnumber
就是 y -x + 4啊,这样算法是nlogn啊。
还有,我看到很多这个range 相关题目,我一直苦于找不到门道,请问谁能指点指点?
最接近的是什么意思? 比如假设树是, 如下,给定3, 最接近的三个
点是 1,2,4啊,还是2,4,5啊
5
3 6
2 4
1
第二题 用一个数组来表示二维数组,但是每一行的元素个数可以不同,实现get,set函
数。 这个题目怎么做的? 是不是需要把每一行的数组的长度保存起来?还是保存那
个前面所有n行的元素的和?
第三题 Given 2D coordinates , find the k points which are closest to the
origin. Propose a data structure for storing the points and the method to
get the k points. Also point out the complexity of the code.
假设就找最近的,可以用kd tree,但是要找k个怎么找呢? 每次把最近的去掉,然后
找k次?这样每次去掉的时候也要修改kd tree吧? 这样时间复杂度是多少? 如果直
接用heap做呢?
第四题 You are given N ranges of date offsets when N employees are present
in an organization. Something like
1-4 (i.e. employee will come on 1st, 2nd, 3rd and 4th day ) 2-6
8-9
..
1-14
You have to organize an event on minimum number of days such that each
employee can attend the event at least twice. Write an algorithm (there is
apparently an O(n) algorithm for this).
请问这里面这个event是必须连续的么?
请问这个O(n) 的算法是什么? 我能够想到的算法是,对所有ending排序,假设最小的
ending是x,然后对所有的start排序,假设最大的start是y,那么这个minimumnumber
就是 y -x + 4啊,这样算法是nlogn啊。
还有,我看到很多这个range 相关题目,我一直苦于找不到门道,请问谁能指点指点?