this question is nice - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

this question is nice

this question is nice# JobHunting - 待字闺中

H*M2010-01-15 08:01

1 楼

职业杯上拷来的
觉得不错。不是那么难，但是也很巧妙。
given a file with heirarchial input like below.. create xml representation..
a.b.c=1
a.b.d=4
a.e=6
input can be assumed to be sorted and is heirarchial in nature.
output should look like
146
asked general algorithm and approach.

k*e2010-01-15 08:01

2 楼

这个知道shared prefix length貌似就可以了啊
看看那道边界是黑的最大矩形的题目

..

【在 H*M 的大作中提到】

: 职业杯上拷来的
: 觉得不错。不是那么难，但是也很巧妙。
: given a file with heirarchial input like below.. create xml representation..
: a.b.c=1
: a.b.d=4
: a.e=6
: input can be assumed to be sorted and is heirarchial in nature.
: output should look like
: 146
: asked general algorithm and approach.

k*e2010-01-15 08:01

3 楼

难道你是说given an array of sorted strings, find the shared prefix of all
adjacent pairs efficiently? Then, that is tricky. I think I read some
algorithm before

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

: 这个知道shared prefix length貌似就可以了啊
: 看看那道边界是黑的最大矩形的题目
:
: ..

H*M2010-01-15 08:01

4 楼

求一个边界是1的最大的内部全是0的矩形？
这个貌似讨论过啊?

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

: 这个知道shared prefix length貌似就可以了啊
: 看看那道边界是黑的最大矩形的题目
:
: ..

k*e2010-01-15 08:01

5 楼

no, that is a different problem.
i don't care the rectangle is all 0 or 1, I just want its boundaries to be
all 1

【在 H*M 的大作中提到】

: 求一个边界是1的最大的内部全是0的矩形？
: 这个貌似讨论过啊?

H*M2010-01-15 08:01

6 楼

原题在哪啊？？

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

: no, that is a different problem.
: i don't care the rectangle is all 0 or 1, I just want its boundaries to be
: all 1

b*j2010-01-15 08:01

7 楼

can be done in less than 20 lines of python:
import sys
last = []
for line in sys.stdin:
node, data = map(str.strip, line.split('='))
nodes = map(str.strip, node.split('.'))
for i, (s1, s2) in enumerate(map(None, last, nodes)):
if s1 != s2:
if s1:
sys.stdout.write('' % '>if s2:
sys.stdout.write('' % '>break
sys.stdout.write(data)
last = last[:i] + nodes[i:]
if last:
print '' % '>
【在 H*M 的大作中提到】

m*f2010-01-15 08:01

8 楼

职业杯上就有

【在 H*M 的大作中提到】

: 原题在哪啊？？

r*u2010-01-15 08:01

9 楼

你可以build a tree。然后postfix traverse tree，第一次走到这个节点printf
，当左右子树都遍历过了，就printf。当然，leaf节点要printf number。
a
/ \
b e
/ \ 6
c d
1 4

..

【在 H*M 的大作中提到】

c*o2010-01-15 08:01

10 楼

这个方法好，就是有一点，每个node可能不止左右两个子树，应该可以有若干个子树。
所以应该是从左到右把这个node的所有子树都遍历一遍。

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

: 你可以build a tree。然后postfix traverse tree，第一次走到这个节点printf
: ，当左右子树都遍历过了，就printf。当然，leaf节点要printf number。
: a
: / \
: b e
: / \ 6
: c d
: 1 4
:
: ..

H*M2010-01-15 08:01

11 楼

职业杯上的题是这样的:
Imagine you have a square matrix, where each cell is filled with either blac
k or white. Design an algorithm to find the maximum subsquare such that all
four borders are filled with black pixels.
不过按他的算法,我觉得是O(n^4)而不是O(n^2):
1. iterate each full column ->n
2. iterate each sub column -> n^2
3. check if it can form a sqaure ->n
total O(n^4)
第三步可以用2n个interval tree记录每行每列的连续0的起始index,这样第三步就省到
lgn,总共可以O(n^3.lgn).

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

: 职业杯上就有