今天的探针太假了 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Stock

今天的探针太假了

今天的探针太假了# Stock

w*e2010-02-05 08:02

1 楼

1. 一个5万行的CSV文件，用unix commands写出结果同时满足:
1> 交换最后一列和第一列的位置
2> 拆分成每个500行的小文件
我是没写出来，最后用python搞了，有人知道怎么写么？
2. 一个比赛有n个人参加，1 vs. 1，比赛结果全靠实力，选手实力提前不知，写code
找出水平第二高的选手
不难，不过我写的好多bug，sigh

3. 设计一个找租房的网站

g82010-02-05 08:02

2 楼

今天的探针太假了

A*o2010-02-05 08:02

3 楼

第一题用awk写了个献丑了，后两题求指点？
第二题感觉就是个排序问题？需要给定一个胜负判别的函数吧？类似cmp
附第一题代码,用小文件测试了下,不知G家怎么考脚本了？楼主是什么职位？
#!/bin/awk -f
BEGIN {
line = 0;
fileno = 1;
}
{
# swap 1st and last column
tmp = $1;
$1 = $NF;
$NF = tmp;
arr[line] = $0;
line++;
# counter and print
if (NR % 500 == 0) {
file = sprintf("split_%d.txt", fileno);
for (i = 0; i < line; i++) {
print arr[i] >> file;
}
line = 0;
fileno++;
}
}

g*e2010-02-05 08:02

4 楼

~~
cat file | awk -F 'separator_char' {'print $1, $2, ..$j, .. $i, ..$NF'} > ./
out
~~~
split
i searched google...
code
~~~~

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

: 1. 一个5万行的CSV文件，用unix commands写出结果同时满足:
: 1> 交换最后一列和第一列的位置
: 2> 拆分成每个500行的小文件
: 我是没写出来，最后用python搞了，有人知道怎么写么？
: 2. 一个比赛有n个人参加，1 vs. 1，比赛结果全靠实力，选手实力提前不知，写code
: 找出水平第二高的选手
: 不难，不过我写的好多bug，sigh
:
: 3. 设计一个找租房的网站

w*e2010-02-05 08:02

5 楼

对，第二题是个tournament，有个playmatch(player1, player2)返回winner，但是这
个call is expensive, like 30mins/match
反正我说的是先跑一遍比赛，找出winner，然后把winner之前的对手拿出来再跑一次
tournament，赢的那个就是2nd best，这个好像是linear。不是很确定sort可不可以，
那样就不是tournament了吧？
第三个是比较罗嗦的设计，什么输入一个地址，返回周围可以出租的房子，还要有像
yelp那样的rating和review，关于房子，租客，房东都要，很磨叽很多requirements

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

: 第一题用awk写了个献丑了，后两题求指点？
: 第二题感觉就是个排序问题？需要给定一个胜负判别的函数吧？类似cmp
: 附第一题代码,用小文件测试了下,不知G家怎么考脚本了？楼主是什么职位？
: #!/bin/awk -f
: BEGIN {
: line = 0;
: fileno = 1;
: }
: {
: # swap 1st and last column

S*12010-02-05 08:02

6 楼

code
第二题就是divided and conquer 然后 recursive函数返回两个值，一个最大，一个第
二大。说实话还蛮tricky的感觉

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

h*t2010-02-05 08:02

7 楼

divided and conquer 要比较几次？复杂读也高吧？

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

:
: code
: 第二题就是divided and conquer 然后 recursive函数返回两个值，一个最大，一个第
: 二大。说实话还蛮tricky的感觉

i*o2010-02-05 08:02

8 楼

For 2, does this work and how to improve? thx!
Suppose X1, X2,....Xn,
1) compare X1 and X2, if X1 > X2 then X(1)=X1, X(2)=X2, o.w. X2 X1
2) comapre X3 and X(2):
if X3 < X(2) jump to X4
if X3 > X(2) comapre X3 and X(1): if X3 > X(1) then X(2)=X(1) X(1)=X3
if X3 < X(1) then X(2)=X3
3) compare X4 and X(2)....similar to 2)

code

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

g*g2010-02-05 08:02

9 楼

这第二道题根本就是个错题，三人循环胜怎么办？又不是数字，总可以排序。

code

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

c*p2010-02-05 08:02

10 楼

mark

n*f2010-02-05 08:02

11 楼

第二题有n+log(n)次比较的方法，两两PK，胜者再两两PK，直到决出冠军，整个过程就
构成了一棵树，把冠军对应的那些点标出来，第二名只可能出现在这些点的兄弟结点上
。

c*y2010-02-05 08:02

12 楼

Agreed. Otherwise, we need the following assumption.
Player i has a constant, but unknown power value. Then the question becomes
how to find out the player with the second largest power value.

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

: 这第二道题根本就是个错题，三人循环胜怎么办？又不是数字，总可以排序。
:
: code

c*y2010-02-05 08:02

13 楼

Looks the best solution. This answer reminds me of an example my professor
gave in Algorithm class. In general, finding the kth element can be achieved
using a heap, which leads to an algorithm of O(n log k). However, finding
the 2nd elem can be done in 2n steps, and further be reduced to n + log n as
described below.

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

: 第二题有n+log(n)次比较的方法，两两PK，胜者再两两PK，直到决出冠军，整个过程就
: 构成了一棵树，把冠军对应的那些点标出来，第二名只可能出现在这些点的兄弟结点上
: 。

h*g2010-02-05 08:02

14 楼

第二个不是错题。假如ABC 三个人如果A输给B B输给C 那么我们就可以得出结论C是冠
军B是亚军，而不需要第三场A vs C.
换句话讲，如果我们有一场比赛能够决定一个偏序关系 e.g. A个偏序关系 e.g. B具体到这道题，我们假设n是32. 我们首先设计16场 1 v 1比赛，决出16 强。再设计8
场比赛决出 8强，然后4场比赛决出4强，然后两场比赛决出两强，最后一场决出冠军
。那么冠军一共经历了5场比赛。第二名肯定在冠军的这5个手下败将中产生（如果另有
其人，那么这个人肯定在某淘汰赛输给了另一个人，那么他最多只能是第三，矛盾）。
因此就转换成了求5个人之中的best，需要4场比赛。这个5人之间的best就是第二名

h*g2010-02-05 08:02

15 楼

这题的考点主要在于用尽可能少的比赛次数来获得sufficient证据（偏序关系）来决定
排名