l*********g
发帖数: 107 | 1 实验室一师兄去面试被问到此题（大概，可能不是100%精确），回来让我做做看
一个Excel表格，行用1，2，3。。。。表示，列用A,B,C,D..表示
每个格子中是一个字符串（也就是说输入是二维字符串数组），这个字符串可能是个简
单数值，也可能是个表达式，
例如：
A B C D E
---------------------------------------------------------
1 | 12 C2+4 D4-A2 4 A4
2 | B3-5+C2 45 C1 A1 9
3 | .. .. .. .. ..
4 | .. .. .. .. ..
类似这样，
写代码：
1） 能不能solve? （可能会有loop的）
2） 能solve的话，最后结果是什么？（是一个二维int数组）
这样一个题算是什么难度？Easy肯定不是了，Medium ? Hard ?
完整solution最优要多少代码？
师兄说他没能全部写完，我试了一下，代码也是非常长，我们实验室的白板（大概1*2
米) 感觉写不下（通常写字的字体大小） |
c*****u
发帖数: 867 | 2 看起来可以用topology sort来做。把格子看作点，如果一个格子里引用了另一个格子
，那么这两点间就有个有向边。建好图后做topology sort，如果没有环路就说明表格
有解。
不知有没有更巧妙的解法
【在 l*********g 的大作中提到】
: 实验室一师兄去面试被问到此题（大概，可能不是100%精确），回来让我做做看
: 一个Excel表格，行用1，2，3。。。。表示，列用A,B,C,D..表示
: 每个格子中是一个字符串（也就是说输入是二维字符串数组），这个字符串可能是个简
: 单数值，也可能是个表达式，
: 例如：
: A B C D E
: ---------------------------------------------------------
: 1 | 12 C2+4 D4-A2 4 A4
: 2 | B3-5+C2 45 C1 A1 9
: 3 | .. .. .. .. ..
|
b***e
发帖数: 383 | |
a*******g
发帖数: 1221 | 4 这个我觉得用topology sort有点大才小用了，就直接递归算就好了，在算的时候注意
一下如果有loop就跳出来吧。然后算完了及时把结果保存下来。用topology sort的话
这题我感觉写不完，并且不一定复杂度上还更优。主要的难度我觉得在于解析“B3-5+
C2”这样复杂的式子。 |
b***e
发帖数: 383 | 5
牛！你的这种思路也非常不错，代码量上面应该更有优势。复杂度上面也就是O(mn).
"主要的难度我觉得在于解析“B3-5+C2”这样复杂的式子", 这种好像只能用逆波兰表
达式求解，先得找出B3, C2对应的值。
【在 a*******g 的大作中提到】
: 这个我觉得用topology sort有点大才小用了，就直接递归算就好了，在算的时候注意
: 一下如果有loop就跳出来吧。然后算完了及时把结果保存下来。用topology sort的话
: 这题我感觉写不完，并且不一定复杂度上还更优。主要的难度我觉得在于解析“B3-5+
: C2”这样复杂的式子。
|
a*******g
发帖数: 3500 | 6 搞个visited记录？
一旦visited了，还要再访问 就跳出？
解析这种公式就是逆波兰表达式
【在 a*******g 的大作中提到】
: 这个我觉得用topology sort有点大才小用了，就直接递归算就好了，在算的时候注意
: 一下如果有loop就跳出来吧。然后算完了及时把结果保存下来。用topology sort的话
: 这题我感觉写不完，并且不一定复杂度上还更优。主要的难度我觉得在于解析“B3-5+
: C2”这样复杂的式子。
|
c********t
发帖数: 5706 | 7 看楼主的帖子，只有加减法也没括号，直接顺序计算就好吧
【在 a*******g 的大作中提到】
: 搞个visited记录？
: 一旦visited了，还要再访问 就跳出？
: 解析这种公式就是逆波兰表达式
|
a*******g
发帖数: 3500 | 8 edge case都要考虑到的啊
【在 c********t 的大作中提到】
: 看楼主的帖子，只有加减法也没括号，直接顺序计算就好吧
|
l*********g
发帖数: 107 | 9 我很想看看，这题完整代码（Java或C++)，最短能到多少。。。
师兄说，当面试官说完这题，他就感觉这题写不完/面试的板上写不下 （不知道板多大
） |
b***e
发帖数: 383 | 10 解这种题，很明显需要实现好几个methods，比如判断一个字符串是一个值还是一个表
达式，实现逆波兰表达式得到expression的值等等. 面试的时候，你可以假设这些
methods已经实现了，毕竟这不是考察的重点。即便要实现，可以等把主要部分实现以
后再实现那些methods。 |
|
|
a*******g
发帖数: 3500 | 11 赞
要学会抽象
【在 b***e 的大作中提到】
: 解这种题，很明显需要实现好几个methods，比如判断一个字符串是一个值还是一个表
: 达式，实现逆波兰表达式得到expression的值等等. 面试的时候，你可以假设这些
: methods已经实现了，毕竟这不是考察的重点。即便要实现，可以等把主要部分实现以
: 后再实现那些methods。
|
h**********c
发帖数: 4120 | 12 怎么觉得是矩阵求kernel,不满秩的情况下要做pivotal，超秩的情况下无解
最坏情况 n^3,n 是未知数的个数。 |
h**********c
发帖数: 4120 | 13 忘了pivotal跟这个没关系
【在 h**********c 的大作中提到】
: 怎么觉得是矩阵求kernel,不满秩的情况下要做pivotal，超秩的情况下无解
: 最坏情况 n^3,n 是未知数的个数。
|
j********g
发帖数: 61 | 14 这是个DAG。能否solve，1.是否loop。2.是否全联通。
递归复杂度应该是 (N-1)!，N是 cell数目。
Parsing 字符串是预处理。topology sort代码不长。 |
R*****i
发帖数: 2126 | 15 我不明白这个问题为什么非要用topological sorting?我嚼着扫描+迭代就可以了。我
敢保证Excel的迭代次数不会超过三四次的。谁吃了没事干，A1表达式里用A2， A2的表
达式里用A3， A3的表达式用A4...An-1的表达式里用An, An的表达式里用B1，...,最多
嵌套个三四次吧？ |
h**********c
发帖数: 4120 | |
z*****6
发帖数: 16 | 17 楼主，B3-5是B3～B5呢还是B3减去5？我觉得这个题不用考虑太多复杂的表达式处理，
因为考点不在那里。或者topology sorting或者dfs每一个cell的关联的cell，如果有
cycle（B3=A5+A6，A5=B3+A6）就返回false。可以用visited和dependencies两个二维
boolean数组去做cache来优化dfs，结果应该是O（mn）的 |
l********e
发帖数: 103 | |
z**********e
发帖数: 91 | 19 这感觉像做过的一家不计时初选题。。toplogical sort注意circular dependency。。 |
a*******g
发帖数: 1221 | 20 为啥都要用topology sort呢？用topology sort解这题就跟用quick sort解一个数组的
最大值似的。这不是sort的问题，因为这里面没有排序，最后的要求是你要么输出“无
解”，要么输出一个最终解，没有排序。我说没有排序的原因是这里面你先算哪个格后
算哪个格没有关系的。直接递归O(MN)就出来了。如果用topo sort的话我想不出来能O(
MN)内能解决的，并且topo sort还得建一个dependency之类的东西，更麻烦。
def __init__(self):
# 这里面存着类似于{'A2':10, 'E3': 20}这种已经算好的值
self.cell2val = {}
self.computing = set()
self.icandoit = true
def compute(self, cell):
if not self.icandoit:
return None
if cell in self.cell2val:
return self.cell2val[cell]
if cell in self.computing:
self.icandoit = False
return None
self.computing.add(cell)
formula = cell的表达式，类似于 X1-Y2+Z8
return_value = None
if formula 是常数:
return_value = 那个常数
else:
result = None
for c in formula.split("+-"):
v = self.compute(c)
if result is None:
result = self.compute(c)
else:
# 看c前面的符号
if 如果c前面是个+:
result += self.compute(c)
else:
result -= self.compute(c)
return_value = result
self.cell2val[cell] = return_value
self.computing.remove(cell)
return return_value
def solve(self, matrix):
for cell in matrix:
if cell not in self.cell2val:
self.compute(cell)
if self.icandoit:
print self.cell2val
else:
print 'i cannot do it' |
l*********g
发帖数: 107 | 21 B3-5 就是 B3 减 5
G的
问了，当时的板居然连1x2大都不到，感觉有点坑啊 |
