泡菜斯坦， - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

泡菜斯坦，

泡菜斯坦，# Joke - 肚皮舞运动

b*i2014-04-18 07:04

1 楼

find a intersection to build office so that the sum of all employees’
commute distances is minimum. （the map is represented as a m*n grid, you
are given each employee’s coordination, they can only move in up-down and
left-right directions）
这是Google一道面试题。我能想到的就是从每个employee做BFS，再求出非employee的
格子的最短路径之和。找个和最小的格子。请问这题还有更简单的方法吗？

o*12014-04-18 07:04

2 楼

“岁月”号客轮在珍岛沉没的第二天，即17日，聚集在首尔站候车室的市民们正焦急地
收看救援新闻。虽然海警方面出动169艘舰船和29架飞机，但再未找到幸存者。
韩国《朝鲜日报》中文网站18日报道，16日在珍岛前海沉没的“岁月”号生还率为
37.8%。1912年在北大西洋沉没的“泰坦尼克”号生还率为32%。很多人愤怒地说：“(
在近海沉没的)‘岁月’号生还率竟然和一百年前(在北大西洋茫茫大海中沉没的)‘泰
坦尼克号’差不多”、“2014年的韩国发生这种事情真是令人难以置信”。475名乘客
中179人生还的“岁月”号的生还率只比2224名乘客中710人得救的“泰坦尼克”号高不
到6个百分点。在“无能的韩国仍旧是落后国家”的一片叹息和自嘲声中，甚至出现了
“泡菜斯坦”等贬低韩国的说法。
陆续有迹象表明此次发生的惨案是典型的“落后国人祸”，在各种门户网站和社交
网上，数百万网民难掩愤怒的情绪，纷纷表示“两个小时里就眼睁睁地看着客轮沉没，
失去孩子的国家没有希望”。首尔大学网络论坛中有一名首尔大学学生愤怒地留言说：
“时钟仿佛回到了事故频发的20世纪90年代。韩国已经经历过圣水大桥、三丰百货大楼
倒塌、大邱地铁纵火案等诸多灾难，但还是发生这种‘人祸’，真是令人无语。”公司
职员李某说：“韩国一发生这种灾难就只顾当时处理事态，但却不懂得吸取教训。虽然
经济上有所发展，但社会体系还是落后国家的水平。”
17日上午有消息称，事发时广播通知乘客“不要离开船舱”后和乘务员一起逃离“
岁月”号的船长李俊石(音)获救后忙着晾干钞票，还说“我是乘务员。什么也不知道。
”这一消息传开后，大家纷纷表示：“那些人精神正常吗？”、“自己的孩子在船里也
会那样做吗？”。一位网民说：“壬辰倭乱时，皇帝弃城而逃，朝鲜战争(韩国称6·25
战争、韩国战争)时战争指挥者炸断大桥逃亡，此次是船长丢下乘客自己逃生。”
这种情况下，“泰坦尼克”号沉没时船长、航海师、船舶设计者等负责人一直留在
船上帮助乘客逃生，最后和客轮一起沉没的事实再次成为焦点。很多人自嘲称：“这就
是1912年英国和2014年韩国之间的国格差距”、“政客们总是挂在嘴边的所谓‘国格’
就是如此”。
对于为什么“岁月”号上配备的46艘救生艇中只有一艘漂在海上，运营商清海镇海
运公司表示：“(沉船)打捞上来才能确认。”这一回答受到强烈谴责。大家纷纷指出：
“说什么打捞上来才能知道攸关乘客生死的救生艇有无异常，这是客轮运营商该说的话
吗？”、“连这个都没确认就出海航行？”而“泰坦尼克”号沉没时，只能承载一半乘
客的20艘救生艇全部漂在海上，救了很多条生命。
事发初期，安全行政部、海警和教育厅公布的损失规模和生还者人数一改再改，网
民们对此指出：“这就是三流政府所做的事”、“早晨说‘全部得救’时还很安心，但
现实却是巨大灾难”、“安全行政部洗洗睡吧”。
首尔大学社会系教授郑根埴表示：“韩国人因为‘行动迅速’而在短期内实现高速
增长，但背后却存在将速成和走捷径视为理所当然的‘马马虎虎’现象。‘岁月’号惨
案就是如此，如果船长和乘务员按照原则行事，就能将损失降到最低。”他还说：“不
要只处罚船长等几名负责人，我们所有人都要深刻反省这种‘马马虎虎’文化。”

k*42014-04-18 07:04

3 楼

分别找x，y方向的median，O(n)时间，O（1）空间。

l*t2014-04-18 07:04

4 楼

终于从“宇宙第一国“的意淫的梦境中醒过来了？

a*m2014-04-18 07:04

5 楼

找median O(1)空间能搞定吗，在O(n)时间的前提下？

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

: 分别找x，y方向的median，O(n)时间，O（1）空间。

r*z2014-04-18 07:04

6 楼

难说，就象夜里被憋醒，骂一句，怎么这么黑暗，然后上了趟厕所回去就接着做梦了。

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

: 终于从“宇宙第一国“的意淫的梦境中醒过来了？

b*i2014-04-18 07:04

7 楼

Good point
我忘了，一维的情况为什么median是距离最短的？
这题还有个变种，matrix中有的格子是block，是否只能bfs了？

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

: 分别找x，y方向的median，O(n)时间，O（1）空间。

g*n2014-04-18 07:04

8 楼

顺便吃两口泡菜能做个娶媳妇儿的美梦

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

: 难说，就象夜里被憋醒，骂一句，怎么这么黑暗，然后上了趟厕所回去就接着做梦了。

a*m2014-04-18 07:04

9 楼

排序以后从最外往里面消去。只考虑最外两个人，对于他们的区别来说只有两种情况：
在两个人里面还是在两个人外面，如果在里面两个走的距离不可避免是他们之间的距离
；在外面的话会超过这个距离。所以选的点必定在他们之间。而且因为路径长度不变，
所以去掉不影响最后结果。重复这个过程。到最后如果只有一个人的时候类似，两种情
况变成在他家还是不在他家，不在的话肯定比在他家更远。如果最后剩两个人，任意一
个在这两人之间的点都没区别，包括这两个人的位置。
啥叫有的格子是block?

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

: Good point
: 我忘了，一维的情况为什么median是距离最短的？
: 这题还有个变种，matrix中有的格子是block，是否只能bfs了？

d*02014-04-18 07:04

10 楼

韩亚的飞机再也不能坐了

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

: “岁月”号客轮在珍岛沉没的第二天，即17日，聚集在首尔站候车室的市民们正焦急地
: 收看救援新闻。虽然海警方面出动169艘舰船和29架飞机，但再未找到幸存者。
: 韩国《朝鲜日报》中文网站18日报道，16日在珍岛前海沉没的“岁月”号生还率为
: 37.8%。1912年在北大西洋沉没的“泰坦尼克”号生还率为32%。很多人愤怒地说：“(
: 在近海沉没的)‘岁月’号生还率竟然和一百年前(在北大西洋茫茫大海中沉没的)‘泰
: 坦尼克号’差不多”、“2014年的韩国发生这种事情真是令人难以置信”。475名乘客
: 中179人生还的“岁月”号的生还率只比2224名乘客中710人得救的“泰坦尼克”号高不
: 到6个百分点。在“无能的韩国仍旧是落后国家”的一片叹息和自嘲声中，甚至出现了
: “泡菜斯坦”等贬低韩国的说法。
: 陆续有迹象表明此次发生的惨案是典型的“落后国人祸”，在各种门户网站和社交

i*e2014-04-18 07:04

11 楼

有的格子是障碍物吧

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

: 排序以后从最外往里面消去。只考虑最外两个人，对于他们的区别来说只有两种情况：
: 在两个人里面还是在两个人外面，如果在里面两个走的距离不可避免是他们之间的距离
: ；在外面的话会超过这个距离。所以选的点必定在他们之间。而且因为路径长度不变，
: 所以去掉不影响最后结果。重复这个过程。到最后如果只有一个人的时候类似，两种情
: 况变成在他家还是不在他家，不在的话肯定比在他家更远。如果最后剩两个人，任意一
: 个在这两人之间的点都没区别，包括这两个人的位置。
: 啥叫有的格子是block?

a*m2014-04-18 07:04

12 楼

哦。那比较烦了。感觉用dp比较好。每个人单独算一遍，最后整个map扫描一遍。
修改一下，bfs应该可以，dp没好处。

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

:
: 有的格子是障碍物吧

k*42014-04-18 07:04

13 楼

基于qiuck select的方法找median可以吧，不用递归而是循环。

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

: 找median O(1)空间能搞定吗，在O(n)时间的前提下？

a*m2014-04-18 07:04

14 楼

看了一下，你说的对，in place可以constant memory overhead。

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

: 基于qiuck select的方法找median可以吧，不用递归而是循环。

S*s2014-04-18 07:04

15 楼

可以建立这样一个函数，对于一个特定的点，只可能有最多4个方向可以移动，可以从
（0，0）开始，计算每个位置的距离，取最小值:
min(当前位置，左移动（可以的话），右移动（可以的话），上移动（可以的话），下
移动（可以的话））
终止条件是无法移动了。这个算法对于有block的也适用。

w*a2014-04-18 07:04

16 楼

http://www.ninechapter.com/problem/30/
是不是这题
最短曼哈顿距离和

h*c2014-04-18 07:04

17 楼

很看成最短路径怪
那捂空捉了来，一棒打去
岂不是到了西天

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

: find a intersection to build office so that the sum of all employees’
: commute distances is minimum. （the map is represented as a m*n grid, you
: are given each employee’s coordination, they can only move in up-down and
: left-right directions）
: 这是Google一道面试题。我能想到的就是从每个employee做BFS，再求出非employee的
: 格子的最短路径之和。找个和最小的格子。请问这题还有更简单的方法吗？

h*c2014-04-18 07:04

18 楼

那武松听了
也把那怪捉来，一棒打去
却打出景阳冈的exception

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

: 很看成最短路径怪
: 那捂空捉了来，一棒打去
: 岂不是到了西天