A G interview question - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

A G interview question

A G interview question# JobHunting - 待字闺中

b*r2011-05-29 07:05

1 楼

From careercup
A line plotter is given which accepts start and end points to be plotted
as well as the line colour. What are the factors that affect the time
taken to plot the lines? Given a sequence of lines to be plotted give an
algorithm that helps you to plot the lines in the least amount of time.
Looks like a NPC problem

y*g2011-05-29 07:05

2 楼

没看懂
准许的最基本plot操作是什么？

【在 b**********r 的大作中提到】

: From careercup
: A line plotter is given which accepts start and end points to be plotted
: as well as the line colour. What are the factors that affect the time
: taken to plot the lines? Given a sequence of lines to be plotted give an
: algorithm that helps you to plot the lines in the least amount of time.
: Looks like a NPC problem

b*r2011-05-29 07:05

3 楼

I think there are costs when move the plotter from one end of an interval
to one end of another one, changing color could have cost also.

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

: 没看懂
: 准许的最基本plot操作是什么？

b*r2011-05-29 07:05

4 楼

Some clarification of the problem:
(1) the line plotter take time to move from one point to another
proportional to the distance
(2) It takes constant time to change color from one to another
Give the above condition, how to arrange the line segment sequence to
minimize the total time to paint all of them?

【在 b**********r 的大作中提到】

d*l2011-05-29 07:05

5 楼

好像还是有点不清楚诶，lines是在数轴上还是在二维平面上，重合的部分怎么算什么
的。。

【在 b**********r 的大作中提到】

: Some clarification of the problem:
: (1) the line plotter take time to move from one point to another
: proportional to the distance
: (2) It takes constant time to change color from one to another
: Give the above condition, how to arrange the line segment sequence to
: minimize the total time to paint all of them?

b*r2011-05-29 07:05

6 楼

It's should be on 2d plane, and we can assume no two lines are overlapped
or even intersected. This is from careercup asked by G.
http://www.careercup.com/question?id=9344067

【在 d*******l 的大作中提到】

: 好像还是有点不清楚诶，lines是在数轴上还是在二维平面上，重合的部分怎么算什么
: 的。。

B*12011-05-29 07:05

7 楼

请问这题有大牛有idea吗？
如果颜色不一样，应该怎么弄？
如果颜色都一样，应该怎么弄？

g*y2011-05-29 07:05

8 楼

- 看见careercup上有人给minimum spanning tree的解法，初看好象有道理，仔细想一
下是错的。
- change color的cost对题目来说不重要，你就可以把这个cost折合进路径cost里，计
算方法是一样的。
- 这个有点象变形的bi-partition的min-flow, 直觉上计算量很大。

l*n2011-05-29 07:05

9 楼

I guess it's some graph theory problem. First find a partition for the graph
so that each sub-graph is a connected graph and no two subgraph share the
same point. Next find the minimum tour path for each subgraph

【在 b**********r 的大作中提到】

g*y2011-05-29 07:05

10 楼

算了，不想了，你把所有线段退化成点，那就等同于货郎担问题了。这个找出简单解来
就牛大了。

B*12011-05-29 07:05

11 楼

货郎担问题是什么问题阿？
可否给个连接？
thanks

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

: 算了，不想了，你把所有线段退化成点，那就等同于货郎担问题了。这个找出简单解来
: 就牛大了。

g*y2011-05-29 07:05

12 楼

http://en.wikipedia.org/wiki/Travelling_salesman_problem

【在 B*******1 的大作中提到】

: 货郎担问题是什么问题阿？
: 可否给个连接？
: thanks