暴风集团爆雷了！冯鑫比贾跃亭还惨 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Money - 海外理财

暴风集团爆雷了！冯鑫比贾跃亭还惨

暴风集团爆雷了！冯鑫比贾跃亭还惨# Money - 海外理财

k*e2019-07-29 07:07

1 楼

被问到一个看似很简单的问题：
一个整数数组，由两部分组成，每部分都已经排好序了，现在要把整个调整成一个有序
数组（就是把两个部分归并一下），要求：时间O(n)空间O(1)。
想了一下没做出来，回来网上搜了一下发现这道题居然有人写了paper，45分钟内搞定
如果事先没看过几乎不可能啊？

q*n2019-07-29 07:07

2 楼

天雷滚滚，又一家昔日明星公司爆雷了。
暴风集团公告，公司实际控制人冯鑫，因涉嫌犯罪被公安机关采取强制措施，相关事项
尚待公安机关进一步调查。
按照现在的暴雷节奏，我估计上市公司董事长们，今年是铁了心要上演一部大片——《
监狱风云2》。冯鑫当初学谁不好，非要学习贾跃亭，暴风模仿乐视，也先后定增了影
视，游戏，VR，娱乐平台等。
但得了老贾的病，并没有老贾的命，现在老贾还能躲在美国继续造车忽悠人，而冯鑫只
能蹲号子了。
从商业模式上，乐视和暴风一样，都属于拿着醋来市场借饺子的，主营电视业务，行业
竞争压力大，现金流极其差，只不过恰好赶上了2015年货币大放水，又讲了一出好故事
。。
但结局恐怕都一样，乐视目前已经被暂停上市，而暴风截至目前，市值只有不到30亿，
账上只有600多万，且连亏三年，退市也几乎是板上钉钉。
从去年开始，随着大环境去杠杆，上市公司开始密集暴雷，而随着公司数量越来越多，
最终，大家一定会得出结论，还是核心资产最靠谱，如果自己瞎折腾，早晚要被各种雷
炸崩了。。

s*a2019-07-29 07:07

3 楼

合并为啥要额外空间

x*12019-07-29 07:07

4 楼

他不讲了数组么。又不是list

r*g2019-07-29 07:07

5 楼

paper怎么做的？

C*e2019-07-29 07:07

6 楼

正常的做法当然需要额外空间。。

【在 s****a 的大作中提到】

: 合并为啥要额外空间

j*82019-07-29 07:07

7 楼

其实就是merge sort中的merge，
in place O(1)是CS教授研究的东西
小黑

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

: 被问到一个看似很简单的问题：
: 一个整数数组，由两部分组成，每部分都已经排好序了，现在要把整个调整成一个有序
: 数组（就是把两个部分归并一下），要求：时间O(n)空间O(1)。
: 想了一下没做出来，回来网上搜了一下发现这道题居然有人写了paper，45分钟内搞定
: 如果事先没看过几乎不可能啊？

m*n2019-07-29 07:07

8 楼

应该是用后一半向前挪空出来的空间存前一半挤出来的数。比较麻烦的是这块地有时还
要分两部分，其中一个要当circular buffer 用。code要写漂亮不容易。

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

: paper怎么做的？

k*e2019-07-29 07:07

9 楼

如果开辟其中一部分等长的空间做buffer的话，空间复杂度就不是O（1）了。

【在 m*****n 的大作中提到】

: 应该是用后一半向前挪空出来的空间存前一半挤出来的数。比较麻烦的是这块地有时还
: 要分两部分，其中一个要当circular buffer 用。code要写漂亮不容易。

k*e2019-07-29 07:07

10 楼

我知道是in place merge sort，但是我没想过怎么O（1）空间复杂度，回来看了才知
道。1988年的paper，发表在Communications of ACM，我认为没看过的话绝对做不出来
，即使看过了的，当场45分钟内把程序写出来也相当有难度。

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

: 其实就是merge sort中的merge，
: in place O(1)是CS教授研究的东西
: 小黑

k*e2019-07-29 07:07

11 楼

假设数组长度为N，以长度n=sqrt(N)将其分块。

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

: paper怎么做的？

S*t2019-07-29 07:07

12 楼

你数组里的6被你活生生跳过了，好可怜

间，p2到末尾之间，总是有序的

C*72019-07-29 07:07

13 楼

谢谢指正

【在 S********t 的大作中提到】

: 你数组里的6被你活生生跳过了，好可怜
:
: 间，p2到末尾之间，总是有序的

j*82019-07-29 07:07

14 楼

我反正是不会O(n),O(1)的解法，估计面试你的人也不会。
以前我也查过，记得还是CS研究课题,
能给个link吗？

[发表自未名空间手机版 - m.mitbbs.com]

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

: 我知道是in place merge sort，但是我没想过怎么O（1）空间复杂度，回来看了才知
: 道。1988年的paper，发表在Communications of ACM，我认为没看过的话绝对做不出来
: ，即使看过了的，当场45分钟内把程序写出来也相当有难度。

l*o2019-07-29 07:07

15 楼

楼主，你应该当时让出题的人做，估计他也做不出来

k*e2019-07-29 07:07

16 楼

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*e2019-07-29 07:07

17 楼

如果现在还有人问我这题我会让他自己做，当时我不知道这题是黑我。
当时想了半天很惭愧地表示做不出来，一点思路都没有，面试官本人自始至终也没有给
我任何提示。回到家找答案发现面试问这个实在是太黑了。

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

: 楼主，你应该当时让出题的人做，估计他也做不出来

S*t2019-07-29 07:07

18 楼

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*o2019-07-29 07:07

19 楼

其实不管他是不是黑你，你想不出来，就问他要提示。
方便透露谁家的面试吗？

如果现在还有人问我这题我会让他自己做，当时我不知道这题是黑我。当时想了半天很
惭愧地表示做不出来，一点思路都没有，面试官本人自始至终也没有给我任何提示。回
到家找答案发现面试问这个........

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

k*e2019-07-29 07:07

20 楼

M.
我觉得我自己的面试技巧也需要加强，我思考的时候习惯于在纸上写写画画，面试官（
不是黑我这个，我只是泛泛而论）看我不说话就不断问我想好了吗，有思路了嘛，一般
这个时候总会打断我的思考。我知道思考的时候一直沉默也不好，把握不好什么时候沉
默思考和什么时候主动交流的度。

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

: 其实不管他是不是黑你，你想不出来，就问他要提示。
: 方便透露谁家的面试吗？
:
: 如果现在还有人问我这题我会让他自己做，当时我不知道这题是黑我。当时想了半天很
: 惭愧地表示做不出来，一点思路都没有，面试官本人自始至终也没有给我任何提示。回
: 到家找答案发现面试问这个........

S*t2019-07-29 07:07

21 楼

从interviewer的角度很难想象一个小时的时间能让candidate一直stuck在那里，
interview的气氛也太不friendly了吧。怎么lead／guide candidate是interviewing
skill里面比较重要的吧

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

k*e2019-07-29 07:07

22 楼

面的不是什么和研究有关的职位，普通开发，我想不至于对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*t2019-07-29 07:07

23 楼

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*n2019-07-29 07:07

24 楼

这哪家？MS？这么喜欢装。
当然面试时是要多多讨论，每步的思路不管对错都要说出来。
结论是，你确实是被黑了。

k*e2019-07-29 07:07

25 楼

大概是个人思考习惯问题吧。一说话就感觉自己思路被打断了。有什么好办法解决或者
说在面试中有什么相应的交流技巧呢？

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*e2019-07-29 07:07

26 楼

是的。有的面试官是挺装的。
我的问题在于，一开始交流，感觉自己思考思路就打断了；但是想沉下心来思考，又惦
记着keep slient过久会有负面影响，这么一折腾，感觉面试的时候自己的思考问题效
率大打折扣。

【在 h**********n 的大作中提到】

: 这哪家？MS？这么喜欢装。
: 当然面试时是要多多讨论，每步的思路不管对错都要说出来。
: 结论是，你确实是被黑了。