w*******e
发帖数: 312 | 1 1. 一个5万行的CSV文件，用unix commands写出结果同时满足:
1> 交换最后一列和第一列的位置
2> 拆分成每个500行的小文件
我是没写出来，最后用python搞了，有人知道怎么写么？
2. 一个比赛有n个人参加，1 vs. 1，比赛结果全靠实力，选手实力提前不知，写code
找出水平第二高的选手
不难，不过我写的好多bug，sigh
3. 设计一个找租房的网站 |
A*****o
发帖数: 284 | 2 第一题用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********e
发帖数: 1142 | 3
~~
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*******e
发帖数: 312 | 4 对，第二题是个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******1
发帖数: 216 | 5
code
第二题就是divided and conquer 然后 recursive函数返回两个值，一个最大，一个第
二大。说实话还蛮tricky的感觉
【在 w*******e 的大作中提到】
: 1. 一个5万行的CSV文件，用unix commands写出结果同时满足:
: 1> 交换最后一列和第一列的位置
: 2> 拆分成每个500行的小文件
: 我是没写出来，最后用python搞了，有人知道怎么写么？
: 2. 一个比赛有n个人参加，1 vs. 1，比赛结果全靠实力，选手实力提前不知，写code
: 找出水平第二高的选手
: 不难，不过我写的好多bug，sigh
:
: 3. 设计一个找租房的网站
|
h****t
发帖数: 184 | 6 divided and conquer 要比较几次？复杂读也高吧？
【在 S******1 的大作中提到】
:
: code
: 第二题就是divided and conquer 然后 recursive函数返回两个值，一个最大，一个第
: 二大。说实话还蛮tricky的感觉
|
i***o
发帖数: 778 | 7 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 的大作中提到】
: 1. 一个5万行的CSV文件，用unix commands写出结果同时满足:
: 1> 交换最后一列和第一列的位置
: 2> 拆分成每个500行的小文件
: 我是没写出来，最后用python搞了，有人知道怎么写么？
: 2. 一个比赛有n个人参加，1 vs. 1，比赛结果全靠实力，选手实力提前不知，写code
: 找出水平第二高的选手
: 不难，不过我写的好多bug，sigh
:
: 3. 设计一个找租房的网站
|
g*****g
发帖数: 34805 | 8 这第二道题根本就是个错题，三人循环胜怎么办？又不是数字，总可以排序。
code
【在 w*******e 的大作中提到】
: 1. 一个5万行的CSV文件，用unix commands写出结果同时满足:
: 1> 交换最后一列和第一列的位置
: 2> 拆分成每个500行的小文件
: 我是没写出来，最后用python搞了，有人知道怎么写么？
: 2. 一个比赛有n个人参加，1 vs. 1，比赛结果全靠实力，选手实力提前不知，写code
: 找出水平第二高的选手
: 不难，不过我写的好多bug，sigh
:
: 3. 设计一个找租房的网站
|
c********p
发帖数: 1969 | |
n*****f
发帖数: 17 | 10 第二题有n+log(n)次比较的方法，两两PK，胜者再两两PK，直到决出冠军，整个过程就
构成了一棵树，把冠军对应的那些点标出来，第二名只可能出现在这些点的兄弟结点上
。 |
|
|
c**y
发帖数: 172 | 11 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**y
发帖数: 172 | 12 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****g
发帖数: 105 | 13 第二个不是错题。假如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****g
发帖数: 105 | 14 这题的考点主要在于用尽可能少的比赛次数来获得sufficient证据（偏序关系）来决定
排名 |
z****x
发帖数: 25 | 15 强调「比赛结果全靠实力」就是想说明不会存在循环的情况吧
这题用 tournament sort 就好了
【在 g*****g 的大作中提到】
: 这第二道题根本就是个错题，三人循环胜怎么办？又不是数字，总可以排序。
:
: code
|
s**x
发帖数: 7506 | 16
Google 了半天，也没发现详细介绍tournament tree data structure 的。
【在 z****x 的大作中提到】
: 强调「比赛结果全靠实力」就是想说明不会存在循环的情况吧
: 这题用 tournament sort 就好了
|
b*******d
发帖数: 750 | 17
不会把。。。难道不是清华严蔚敏那本书上就有？叫胜者树？
【在 s**x 的大作中提到】
:
: Google 了半天，也没发现详细介绍tournament tree data structure 的。
|
s**x
发帖数: 7506 | 18
too many pictures, but not real implementations.
【在 b*******d 的大作中提到】
:
: 不会把。。。难道不是清华严蔚敏那本书上就有？叫胜者树？
|
s*******z
发帖数: 83 | 19 第一个:
sed -i -e "s/\(^[^,]\+\),\([.*]\),\([^,]\+$\)/\3,\2,\1/"
split -l -n 100 |
P**H
发帖数: 1897 | |
x*****0
发帖数: 452 | |
