k***e
发帖数: 1931 | 1 被问到一个看似很简单的问题：
一个整数数组，由两部分组成，每部分都已经排好序了，现在要把整个调整成一个有序
数组（就是把两个部分归并一下），要求：时间O(n)空间O(1)。
想了一下没做出来，回来网上搜了一下发现这道题居然有人写了paper，45分钟内搞定
如果事先没看过几乎不可能啊？ |
s****a
发帖数: 794 | |
x*******1
发帖数: 28835 | |
r*******g
发帖数: 1335 | |
C********e
发帖数: 492 | 5 正常的做法当然需要额外空间。。
【在 s****a 的大作中提到】
: 合并为啥要额外空间
|
j******8
发帖数: 105 | 6 其实就是merge sort中的merge，
in place O(1)是CS教授研究的东西
小黑
【在 k***e 的大作中提到】
: 被问到一个看似很简单的问题：
: 一个整数数组，由两部分组成，每部分都已经排好序了，现在要把整个调整成一个有序
: 数组（就是把两个部分归并一下），要求：时间O(n)空间O(1)。
: 想了一下没做出来，回来网上搜了一下发现这道题居然有人写了paper，45分钟内搞定
: 如果事先没看过几乎不可能啊？
|
m*****n
发帖数: 204 | 7 应该是用后一半向前挪空出来的空间存前一半挤出来的数。比较麻烦的是这块地有时还
要分两部分，其中一个要当circular buffer 用。code要写漂亮不容易。
【在 r*******g 的大作中提到】
: paper怎么做的？
|
k***e
发帖数: 1931 | 8 如果开辟其中一部分等长的空间做buffer的话，空间复杂度就不是O（1）了。
【在 m*****n 的大作中提到】
: 应该是用后一半向前挪空出来的空间存前一半挤出来的数。比较麻烦的是这块地有时还
: 要分两部分，其中一个要当circular buffer 用。code要写漂亮不容易。
|
k***e
发帖数: 1931 | 9 我知道是in place merge sort，但是我没想过怎么O（1）空间复杂度，回来看了才知
道。1988年的paper，发表在Communications of ACM，我认为没看过的话绝对做不出来
，即使看过了的，当场45分钟内把程序写出来也相当有难度。
【在 j******8 的大作中提到】
: 其实就是merge sort中的merge，
: in place O(1)是CS教授研究的东西
: 小黑
|
k***e
发帖数: 1931 | 10 假设数组长度为N，以长度n=sqrt(N)将其分块。
【在 r*******g 的大作中提到】
: paper怎么做的？
|
|
|
S********t
发帖数: 3431 | 11 你数组里的6被你活生生跳过了，好可怜
间，p2到末尾之间，总是有序的 |
C*7
发帖数: 234 | 12 谢谢指正
【在 S********t 的大作中提到】
: 你数组里的6被你活生生跳过了，好可怜
:
: 间，p2到末尾之间，总是有序的
|
j******8
发帖数: 105 | 13 我反正是不会O(n),O(1)的解法，估计面试你的人也不会。
以前我也查过，记得还是CS研究课题,
能给个link吗？
[发表自未名空间手机版 - m.mitbbs.com]
【在 k***e 的大作中提到】
: 我知道是in place merge sort，但是我没想过怎么O（1）空间复杂度，回来看了才知
: 道。1988年的paper，发表在Communications of ACM，我认为没看过的话绝对做不出来
: ，即使看过了的，当场45分钟内把程序写出来也相当有难度。
|
l**o
发帖数: 356 | 14 楼主，你应该当时让出题的人做，估计他也做不出来 |
k***e
发帖数: 1931 | 15 Huang Bing-Chao and Langston Michael.A.,Practical in-place merging,
Comm. ACM 31(1988)
http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Arti
Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Practical in-place
mergesort"
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.852
【在 j******8 的大作中提到】
: 我反正是不会O(n),O(1)的解法，估计面试你的人也不会。
: 以前我也查过，记得还是CS研究课题,
: 能给个link吗？
:
: [发表自未名空间手机版 - m.mitbbs.com]
|
k***e
发帖数: 1931 | 16 如果现在还有人问我这题我会让他自己做，当时我不知道这题是黑我。
当时想了半天很惭愧地表示做不出来，一点思路都没有，面试官本人自始至终也没有给
我任何提示。回到家找答案发现面试问这个实在是太黑了。
【在 l**o 的大作中提到】
: 楼主，你应该当时让出题的人做，估计他也做不出来
|
S********t
发帖数: 3431 | 17 maybe he was expecting good candidate to respond "I remember there was a
research paper on this..."
I recall there was another in place shuffle problem: shuffle a1b1a2b2 ...
anbn into a1a2... b1b2...
in O(n) time
There was also a paper to solve it
I would advise you to complain to your recruiter, at least let them know
this problem was not appropriate (unreasonably difficult) and why. Maybe
your interviewer was actually stupid enough to have a wrong solution in his/
her own mind.
【在 k***e 的大作中提到】
: 如果现在还有人问我这题我会让他自己做，当时我不知道这题是黑我。
: 当时想了半天很惭愧地表示做不出来，一点思路都没有，面试官本人自始至终也没有给
: 我任何提示。回到家找答案发现面试问这个实在是太黑了。
|
l**o
发帖数: 356 | 18 其实不管他是不是黑你，你想不出来，就问他要提示。
方便透露谁家的面试吗？
如果现在还有人问我这题我会让他自己做，当时我不知道这题是黑我。当时想了半天很
惭愧地表示做不出来，一点思路都没有，面试官本人自始至终也没有给我任何提示。回
到家找答案发现面试问这个........
【在 k***e 的大作中提到】
: 如果现在还有人问我这题我会让他自己做，当时我不知道这题是黑我。
: 当时想了半天很惭愧地表示做不出来，一点思路都没有，面试官本人自始至终也没有给
: 我任何提示。回到家找答案发现面试问这个实在是太黑了。
|
k***e
发帖数: 1931 | 19 M.
我觉得我自己的面试技巧也需要加强，我思考的时候习惯于在纸上写写画画，面试官（
不是黑我这个，我只是泛泛而论）看我不说话就不断问我想好了吗，有思路了嘛，一般
这个时候总会打断我的思考。我知道思考的时候一直沉默也不好，把握不好什么时候沉
默思考和什么时候主动交流的度。
【在 l**o 的大作中提到】
: 其实不管他是不是黑你，你想不出来，就问他要提示。
: 方便透露谁家的面试吗？
:
: 如果现在还有人问我这题我会让他自己做，当时我不知道这题是黑我。当时想了半天很
: 惭愧地表示做不出来，一点思路都没有，面试官本人自始至终也没有给我任何提示。回
: 到家找答案发现面试问这个........
|
S********t
发帖数: 3431 | 20 从interviewer的角度很难想象一个小时的时间能让candidate一直stuck在那里，
interview的气氛也太不friendly了吧。怎么lead／guide candidate是interviewing
skill里面比较重要的吧
【在 l**o 的大作中提到】
: 其实不管他是不是黑你，你想不出来，就问他要提示。
: 方便透露谁家的面试吗？
:
: 如果现在还有人问我这题我会让他自己做，当时我不知道这题是黑我。当时想了半天很
: 惭愧地表示做不出来，一点思路都没有，面试官本人自始至终也没有给我任何提示。回
: 到家找答案发现面试问这个........
|
|
|
k***e
发帖数: 1931 | 21 面的不是什么和研究有关的职位，普通开发，我想不至于对candidate平时是否习惯阅
读paper有要求吧……就算说“我记得有个paper blablabla”，最后也还是要把code写
出来的，我承认剩下30分钟（假设复述，讨论思路10~15分钟），要写出bug free的这
个O(n)，O(1)的算法对我来说几乎不可能，况且写完了code，总要解释一遍的，这也得
起码五分钟。
你后面的建议很好，我以后会这样做的。
his/
【在 S********t 的大作中提到】
: maybe he was expecting good candidate to respond "I remember there was a
: research paper on this..."
: I recall there was another in place shuffle problem: shuffle a1b1a2b2 ...
: anbn into a1a2... b1b2...
: in O(n) time
: There was also a paper to solve it
: I would advise you to complain to your recruiter, at least let them know
: this problem was not appropriate (unreasonably difficult) and why. Maybe
: your interviewer was actually stupid enough to have a wrong solution in his/
: her own mind.
|
S********t
发帖数: 3431 | 22 From interviewer's POV, silence during solving problem is a big negative,
even if candidate may be actually brilliant.
If you're lucky, some interviewer may be willing to not penalize you too
much, if you were able to arrive at solution and then explained clearly how
you did.
The part of problem solving during interview is more about evaluating the
thought process that candidate took to arrive at solution, not just his/her
capability to solve problem. If you remain silent, you mute the evaluation
entirely.
As a rule of thumb, never "沉默思考". Just pretend you are talking to
yourself as you do in your own brain.
【在 k***e 的大作中提到】
: M.
: 我觉得我自己的面试技巧也需要加强，我思考的时候习惯于在纸上写写画画，面试官（
: 不是黑我这个，我只是泛泛而论）看我不说话就不断问我想好了吗，有思路了嘛，一般
: 这个时候总会打断我的思考。我知道思考的时候一直沉默也不好，把握不好什么时候沉
: 默思考和什么时候主动交流的度。
|
h**********n
发帖数: 897 | 23 这哪家？MS？这么喜欢装。
当然面试时是要多多讨论，每步的思路不管对错都要说出来。
结论是，你确实是被黑了。 |
k***e
发帖数: 1931 | 24 大概是个人思考习惯问题吧。一说话就感觉自己思路被打断了。有什么好办法解决或者
说在面试中有什么相应的交流技巧呢？
how
her
evaluation
【在 S********t 的大作中提到】
: From interviewer's POV, silence during solving problem is a big negative,
: even if candidate may be actually brilliant.
: If you're lucky, some interviewer may be willing to not penalize you too
: much, if you were able to arrive at solution and then explained clearly how
: you did.
: The part of problem solving during interview is more about evaluating the
: thought process that candidate took to arrive at solution, not just his/her
: capability to solve problem. If you remain silent, you mute the evaluation
: entirely.
: As a rule of thumb, never "沉默思考". Just pretend you are talking to
|
k***e
发帖数: 1931 | 25 是的。有的面试官是挺装的。
我的问题在于，一开始交流，感觉自己思考思路就打断了；但是想沉下心来思考，又惦
记着keep slient过久会有负面影响，这么一折腾，感觉面试的时候自己的思考问题效
率大打折扣。
【在 h**********n 的大作中提到】
: 这哪家？MS？这么喜欢装。
: 当然面试时是要多多讨论，每步的思路不管对错都要说出来。
: 结论是，你确实是被黑了。
|
