Information Sharing: TC Target Price: 18, but don't know when - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Stock

Information Sharing: TC Target Price: 18, but don't know when

Information Sharing: TC Target Price: 18, but don't know when# Stock

l*g2011-01-19 08:01

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
米) 感觉写不下（通常写字的字体大小）

t*e2011-01-19 08:01

2 楼

Deutsche Bank Raises Price Target On Thompson Creek (TC) to $18
More News related to TC
Deutsche Bank Raises Price Target On Thompson Creek (TC) to $18
BCGold Corp. Appoints Darren O'Brien as Vice President, Exploration
BCGold Corp. Appoints Darren O'Brien as Vice President, Exploration
Canaccord Genuity Upgrades Thompson Creek Metals (TC) to Buy
Notable 52-Week Highs and Lows of the Day 01/03: SIRI, MCP, TC, JBL
High; ISPH Low
More News related to TC
More News related to Analyst Comments
Cubist Pharmaceuticals (CBST) Sees Interesting OTM Call Buying
Dick Bove Slashes Earnings Estimates on Goldman (GS), Cuts Target from
$214 to $188
Las Vegas Sands (LVS), Wynn (WYNN) to Benefit from 30% Rsie in Macau
2011 Revenue
National Oilwell Varco (NOV) Shares on the Move as Morgan Stanley Names
'Long Research Tactical Idea'
Q4 Preview: Future in Flux for AMD (AMD)
More News related to Analyst Comments
January 11, 2011 12:41 PM EST
Deutsche Bank raised its price target on Buy-rated Thompson Creek Metals
(NYSE: TC) from $16 to $18.
The firm said, "TC’s development of the Mt. Milligan copper-gold mine
should reduce its single-product valuation discount.
The firm notes, given its single-product exposure to molybdenum (moly)
in the near term, Thompson Creek's (TC) outlook is closely tied to the
performance of this metal. We maintain a positive view for moly given
demand from new applications, uncertain supply growth, and a shifting
industry cost structure as higher-cost primary product accounts for a
greater proportion of world output. DB expects moly price to continue
rising till 2013 which should drive share price performance.
For more ratings news on Thompson Creek Metals click here and for the
rating history of Thompson Creek Metals click here.
Shares of Thompson Creek Metals closed at $14.51 yesterday, with a 52
week range of $8.01-$16.06.

c*u2011-01-19 08:01

3 楼

看起来可以用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*e2011-01-19 08:01

4 楼

楼上正解，就这个思路了。

a*g2011-01-19 08:01

5 楼

这个我觉得用topology sort有点大才小用了，就直接递归算就好了，在算的时候注意
一下如果有loop就跳出来吧。然后算完了及时把结果保存下来。用topology sort的话
这题我感觉写不完，并且不一定复杂度上还更优。主要的难度我觉得在于解析“B3-5+
C2”这样复杂的式子。

b*e2011-01-19 08:01

6 楼

牛！你的这种思路也非常不错，代码量上面应该更有优势。复杂度上面也就是O(mn).
"主要的难度我觉得在于解析“B3-5+C2”这样复杂的式子", 这种好像只能用逆波兰表
达式求解，先得找出B3, C2对应的值。

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

: 这个我觉得用topology sort有点大才小用了，就直接递归算就好了，在算的时候注意
: 一下如果有loop就跳出来吧。然后算完了及时把结果保存下来。用topology sort的话
: 这题我感觉写不完，并且不一定复杂度上还更优。主要的难度我觉得在于解析“B3-5+
: C2”这样复杂的式子。

a*g2011-01-19 08:01

7 楼

搞个visited记录？
一旦visited了，还要再访问就跳出？
解析这种公式就是逆波兰表达式

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

c*t2011-01-19 08:01

8 楼

看楼主的帖子，只有加减法也没括号，直接顺序计算就好吧

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

: 搞个visited记录？
: 一旦visited了，还要再访问就跳出？
: 解析这种公式就是逆波兰表达式

a*g2011-01-19 08:01

9 楼

edge case都要考虑到的啊

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

: 看楼主的帖子，只有加减法也没括号，直接顺序计算就好吧

l*g2011-01-19 08:01

10 楼

我很想看看，这题完整代码（Java或C++)，最短能到多少。。。
师兄说，当面试官说完这题，他就感觉这题写不完/面试的板上写不下（不知道板多大
）

b*e2011-01-19 08:01

11 楼

解这种题，很明显需要实现好几个methods，比如判断一个字符串是一个值还是一个表
达式，实现逆波兰表达式得到expression的值等等. 面试的时候，你可以假设这些
methods已经实现了，毕竟这不是考察的重点。即便要实现，可以等把主要部分实现以
后再实现那些methods。

a*g2011-01-19 08:01

12 楼

赞
要学会抽象

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

: 解这种题，很明显需要实现好几个methods，比如判断一个字符串是一个值还是一个表
: 达式，实现逆波兰表达式得到expression的值等等. 面试的时候，你可以假设这些
: methods已经实现了，毕竟这不是考察的重点。即便要实现，可以等把主要部分实现以
: 后再实现那些methods。

h*c2011-01-19 08:01

13 楼

怎么觉得是矩阵求kernel,不满秩的情况下要做pivotal，超秩的情况下无解
最坏情况 n^3,n 是未知数的个数。

h*c2011-01-19 08:01

14 楼

忘了pivotal跟这个没关系

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

: 怎么觉得是矩阵求kernel,不满秩的情况下要做pivotal，超秩的情况下无解
: 最坏情况 n^3,n 是未知数的个数。

j*g2011-01-19 08:01

15 楼

这是个DAG。能否solve，1.是否loop。2.是否全联通。
递归复杂度应该是 (N-1)!，N是 cell数目。
Parsing 字符串是预处理。topology sort代码不长。

R*i2011-01-19 08:01

16 楼

我不明白这个问题为什么非要用topological sorting?我嚼着扫描+迭代就可以了。我
敢保证Excel的迭代次数不会超过三四次的。谁吃了没事干，A1表达式里用A2， A2的表
达式里用A3， A3的表达式用A4...An-1的表达式里用An, An的表达式里用B1，...,最多
嵌套个三四次吧？

h*c2011-01-19 08:01

17 楼

就是一典型的线性方程组

z*62011-01-19 08:01

18 楼

楼主，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*e2011-01-19 08:01

19 楼

这是谁家的面试题啊？

z*e2011-01-19 08:01

20 楼

这感觉像做过的一家不计时初选题。。toplogical sort注意circular dependency。。

a*g2011-01-19 08:01

21 楼

为啥都要用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*g2011-01-19 08:01

22 楼

B3-5 就是 B3 减 5
G的
问了，当时的板居然连1x2大都不到，感觉有点坑啊