一个小公司面经 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

一个小公司面经

一个小公司面经# JobHunting - 待字闺中

B*p2010-06-24 07:06

1 楼

问了些背景,和做过的project,
然后,这个没有搭号,就fail 了
Given an array A of n elements and an integer k (where k..A[k]}and {A[k+1]...A[n]} are
already sorted. Give an algorithm to sort the array A in O(n) time and O(1)
space
有大牛给说说没?

i*r2010-06-24 07:06

2 楼

I don't think there is an answer.
The problem is exactly the last step of merge sort, i.e merging the sorted
first half and the sorted second half of the array. I doubt there is O(n) time in-place
algorithm for merging with array. Otherwise merge sort will not need O(n) space.
The problem should be easy if the container is a linked list instead of an array.
Are you sure you get the question right? or may be the interviewer was just
try to test you?
Good luck