这几个题目怎么做啊 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

这几个题目怎么做啊

这几个题目怎么做啊# JobHunting - 待字闺中

g*j2012-12-23 08:12

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 相关题目，我一直苦于找不到门道，请问谁能指点指点？

e*e2012-12-23 08:12

2 楼

第一题
最接近的意思是和key的值最接近吧。
第二题
可不可以用另外一个数组，来记录每一行的第一个元素在一维数组的位置。
i.e.
二维数组 M
1 2 3
4 5 6 7
8 9
一维数组 A
1 2 3 4 5 6 7 8 9
辅助数组 B
0 3 7
所以：M[i,j] <==> A[B[i]+j]
第三题
用max heap吧。对于N个坐标点，求K个最小点。time complexity is N*lg(K)
第四题
维护两个变量x和y，最小的ending是x, 最大的start是y,扫一遍就可以得到x和y.

【在 g***j 的大作中提到】

: 第一题，给一个N个node的BST,给一个key,返回与key最接近的m个node(m < N).
: 最接近的是什么意思？比如假设树是，如下，给定3，最接近的三个
: 点是 1，2，4啊，还是2，4，5啊
: 5
: 3 6
:
: 2 4
: 1
: 第二题用一个数组来表示二维数组,但是每一行的元素个数可以不同,实现get,set函
: 数。这个题目怎么做的？是不是需要把每一行的数组的长度保存起来？还是保存那

j*y2012-12-23 08:12

3 楼

第四题你得到 x, y 以后呢？比如
[1 2] [10 11]
x = 2, y = 10
然后呢？

【在 e****e 的大作中提到】

: 第一题
: 最接近的意思是和key的值最接近吧。
: 第二题
: 可不可以用另外一个数组，来记录每一行的第一个元素在一维数组的位置。
: i.e.
: 二维数组 M
: 1 2 3
: 4 5 6 7
: 8 9
: 一维数组 A

e*e2012-12-23 08:12

4 楼

event start: x-1
event end: y+1

【在 j*****y 的大作中提到】

: 第四题你得到 x, y 以后呢？比如
: [1 2] [10 11]
: x = 2, y = 10
: 然后呢？

j*y2012-12-23 08:12

5 楼

也就是说 event的区间是 1-11 , 是11天
这个太多了吧，实际上只需要四天: 1, 2, 10, 11

【在 e****e 的大作中提到】

: event start: x-1
: event end: y+1

e*e2012-12-23 08:12

6 楼

I'm not sure the event can be 不连续。If it's 不连续, for the case [1 3] [10
12], 就有多种答案：
1 2 10 11
1 2 10 12
1 2 11 12
1 3 10 11
...

【在 j*****y 的大作中提到】

: 也就是说 event的区间是 1-11 , 是11天
: 这个太多了吧，实际上只需要四天: 1, 2, 10, 11

j*y2012-12-23 08:12

7 楼

这个没问题阿，题目是需要找到举办event最少的天数。
你这里就是 4天

10

【在 e****e 的大作中提到】

: I'm not sure the event can be 不连续。If it's 不连续, for the case [1 3] [10
: 12], 就有多种答案：
: 1 2 10 11
: 1 2 10 12
: 1 2 11 12
: 1 3 10 11
: ...

e*e2012-12-23 08:12

8 楼

"You have to organize an event on minimum number of days"
不是求最少的天数，是求最小天数的那些天。

【在 j*****y 的大作中提到】

: 这个没问题阿，题目是需要找到举办event最少的天数。
: 你这里就是 4天
:
: 10

g*j2012-12-23 08:12

9 楼

第一题我给的例子也是值啊。

第一题最接近的意思是和key的值最接近吧。第二题可不可以用另外一个数组，来记录
每一行的第一个元素在一维数组的位置。i.e.二维数组 M1 2 34 5 6 78 9一维数组 A.
.......

【在 e****e 的大作中提到】

: "You have to organize an event on minimum number of days"
: 不是求最少的天数，是求最小天数的那些天。

e*e2012-12-23 08:12

10 楼

不大明白你的意思。第一题例子中最接近的三个点是：2，3，4吧。

【在 g***j 的大作中提到】

: 第一题我给的例子也是值啊。
:
: 第一题最接近的意思是和key的值最接近吧。第二题可不可以用另外一个数组，来记录
: 每一行的第一个元素在一维数组的位置。i.e.二维数组 M1 2 34 5 6 78 9一维数组 A.
: .......

g*j2012-12-23 08:12

11 楼

我给的是3啊，难道3本身算一个么？
如果3本身算一个，那最近的四个值又是多少呢？

不大明白你的意思。第一题例子中最接近的三个点是：2，3，4吧。

【在 e****e 的大作中提到】

:
: 不大明白你的意思。第一题例子中最接近的三个点是：2，3，4吧。

e*e2012-12-23 08:12

12 楼

如果3本身算一个, 1, 2, 3, 4 和 2, 3, 4, 5都行吧。

【在 g***j 的大作中提到】

: 我给的是3啊，难道3本身算一个么？
: 如果3本身算一个，那最近的四个值又是多少呢？
:
: 不大明白你的意思。第一题例子中最接近的三个点是：2，3，4吧。

g*j2012-12-23 08:12

13 楼

这就是我的疑问

如果3本身算一个, 1, 2, 3, 4 和 2, 3, 4, 5都行吧。

【在 e****e 的大作中提到】

: 如果3本身算一个, 1, 2, 3, 4 和 2, 3, 4, 5都行吧。

e*e2012-12-23 08:12

14 楼

What's the solution? Any idea?

【在 g***j 的大作中提到】

: 这就是我的疑问
:
: 如果3本身算一个, 1, 2, 3, 4 和 2, 3, 4, 5都行吧。

d*e2012-12-23 08:12

15 楼

没什么问题吧，也就是有多个答案而已

【在 g***j 的大作中提到】

: 这就是我的疑问
:
: 如果3本身算一个, 1, 2, 3, 4 和 2, 3, 4, 5都行吧。

2024-01-28 18:01

2024-01-09 19:01

2024-01-07 18:01

2024-01-06 18:01

2024-01-06 18:01

2023-12-13 17:12

2023-12-02 07:12

2023-11-26 18:11

中美航班重磅消息！每周85班，直飞更方便！

微软、亚马逊、谷歌大裁员！哪些科技和零售公司有缩减规模计划？

中国外长王毅：中美关系已经止跌回稳

脱轨事故造成20多人受伤联邦调查纽约市全部地铁系统

更多 2024-06-28 的新闻