美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 手机影响精子浓度?测试仪器来了:妹纸们侧目
  • Facebook股价过山车:蒸发掉一个“特斯拉”
  • 为偶像直播间炫富!女主播被打赏200万
  • 华为年终奖曝光:入职3年分18万 共1500亿!
  • 20万以内必火!宝马全新入门轿车来袭 中国特供
  • 保时捷全新卡宴曝光:中控抢眼
  • 汽车变速箱如何变速?看完彻底懂了
  • 谷歌又出黑科技:这回要带你玩遍全世界
  • 2016年最奇葩直播Top10:写代码、大保健……
  • 拖库致裸条泄露?黑客老司机解析10G全套图背后故事
  • 川普的胜选,移民政策是否真的会收紧呢?-美国移民指南
  • 特朗普的经济计划已经在转变
  • 奥巴马禁止中国福建购买Aixtron的美国业务
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3004|回复: 20

内推面经 -这题怎么解好?- 唐人社区|北美华人论坛

[复制链接]
TA在交友中心
0 0 38
  @ME:   

15

主题

35

帖子

72

积分

新手上路

Rank: 1

积分
72
QQ
发表于 6 天前 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推HP?mod=forumdisplay&fid=83&fromuid=1" target="_blank" class="relatedlink">面经版-这题怎么解好?


  JobHunting
标 题: 这题怎么解好?


实验室一师兄去面试被问到此题(大概,可能不是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
米) 感觉写不下(通常写字的字体大小)




--


新浪微博官方号:美国华人网FunInUSA 新浪微博官方号:美国省钱快报FunInUSA 微信公众号:玩美生活FunInUSA
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

TA在交友中心
0 0 46
  @ME:   

21

主题

99

帖子

140

积分

注册会员

Rank: 2

积分
140
QQ
发表于 6 天前 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


搞个visited记录?
一旦visited了,还要再访问 就跳出?

解析这种公式就是逆波兰表达式
【 在 aichitang (爱吃糖) 的大作中提到: 】
: 这个我觉得用topology sort有点大才小用了,就直接递归算就好了,在算的时候注意
: 一下如果有loop就跳出来吧。然后算完了及时把结果保存下来。用topology sort的话
: 这题我感觉写不完,并且不一定复杂度上还更优。主要的难度我觉得在于解析“B3-5+
: C2”这样复杂的式子。



--
TA在交友中心
0 0 54
  @ME:   

22

主题

87

帖子

138

积分

注册会员

Rank: 2

积分
138
QQ
发表于 6 天前 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


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

【 在 allienpig (猪 in black) 的大作中提到: 】
: 搞个visited记录?
: 一旦visited了,还要再访问 就跳出?
: 解析这种公式就是逆波兰表达式



--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?
TA在交友中心
0 0 47
  @ME:   

22

主题

106

帖子

156

积分

注册会员

Rank: 2

积分
156
QQ
发表于 6 天前 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


我很想看看,这题完整代码(Java或C++),最短能到多少。。。

师兄说,当面试官说完这题,他就感觉这题写不完/面试的板上写不下 (不知道板多大

--
TA在交友中心
0 0 47
  @ME:   

21

主题

96

帖子

137

积分

注册会员

Rank: 2

积分
137
QQ
发表于 6 天前 | 显示全部楼层
JobHunting
标  题: 这题怎么解好?


实验室一师兄去面试被问到此题(大概,可能不是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
米) 感觉写不下(通常写字的字体大小)     




--

TA在交友中心
0 0 22
  @ME:   

7

主题

208

帖子

229

积分

注册会员

Rank: 2

积分
229
QQ
发表于 6 天前 | 显示全部楼层
JobHunting
标  题: Re:这题怎么解好?


楼主,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)的
--
TA在交友中心
0 0 47
  @ME:   

19

主题

96

帖子

130

积分

注册会员

Rank: 2

积分
130
QQ
发表于 6 天前 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?



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


牛!你的这种思路也非常不错,代码量上面应该更有优势。复杂度上面也就是O(mn).

"主要的难度我觉得在于解析“B3-5+C2”这样复杂的式子", 这种好像只能用逆波兰表
达式求解,先得找出B3, C2对应的值。
--
TA在交友中心
0 0 61
  @ME:   

26

主题

94

帖子

149

积分

注册会员

Rank: 2

积分
149
QQ
发表于 6 天前 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


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

19

主题

87

帖子

126

积分

注册会员

Rank: 2

积分
126
QQ
发表于 6 天前 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


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

21

主题

88

帖子

133

积分

注册会员

Rank: 2

积分
133
QQ
发表于 6 天前 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


edge case都要考虑到的啊


【 在 coldknight (冷骑士) 的大作中提到: 】
: 看楼主的帖子,只有加减法也没括号,直接顺序计算就好吧



--
您需要登录后才可以回帖 登录 | 立即注册  

本版积分规则

玩美生活FunInUSA.net 华人娱乐论坛发布的内推面经 -这题怎么解好?- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -这题怎么解好?- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
1&1 Hosting

Copyright ©2011 FunInUSA.com All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA

安全联盟认证 安全联盟认证

快速回复 返回顶部 返回列表