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

 找回密码
 立即注册
  • 女汉子又回来了!辣妈angelababy一大清早就健身
  • 好事将近!方媛现身办理港澳通行证
  • 李晨被问要不要娶女友 范冰冰秒答七个字
  • 黄轩终于回应恋情了:试图开始一段感情但不合适
  • 姐的时尚你不懂!蔡依林内衣外穿秀出小蛮腰
  • 和高圆圆接吻什么感觉?赵又廷竟然说…
  • 说好的承诺呢?冯轲被曝未将财产转移给张靓颖
  • 冯轲晒股权变更信息自己仅持有十万 990万给靓颖
  • 全球首座“竹子”基站亮相:抗风210公里/小时
  • 英国狗狗痴迷可口可乐每天必喝:16颗牙掉了12颗
  • Triforce:英特尔、NVIDIA和AMD,你选择哪个?
  • 在Facebook推出更多类似Snap的功能后,Snap股票跌了
  • AMD的股价将进一步上涨
  • 零售死亡漩涡继续
  • 中国电信开启5G网络时代
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3032|回复: 21

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

[复制链接]

17

主题

38

帖子

79

积分

新手上路

Rank: 1

积分
79
QQ
发表于 2016-11-29 05:39:18 | 显示全部楼层 |阅读模式
分享到:
{$content}

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


  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 : 每日滚动更新美国商业投资就业招聘留学移民资讯。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

24

主题

105

帖子

156

积分

注册会员

Rank: 2

积分
156
QQ
发表于 2016-11-29 06:10:12 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


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

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



--

24

主题

89

帖子

146

积分

注册会员

Rank: 2

积分
146
QQ
发表于 2016-11-29 06:12:39 | 显示全部楼层
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?

22

主题

112

帖子

156

积分

注册会员

Rank: 2

积分
156
QQ
发表于 2016-11-29 06:15:17 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


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

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

--

23

主题

103

帖子

154

积分

注册会员

Rank: 2

积分
154
QQ
发表于 2016-11-29 06:16:45 | 显示全部楼层
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
米) 感觉写不下(通常写字的字体大小)     




--

7

主题

219

帖子

229

积分

注册会员

Rank: 2

积分
229
QQ
发表于 2016-11-29 06:26:14 | 显示全部楼层
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)的
--

21

主题

104

帖子

155

积分

注册会员

Rank: 2

积分
155
QQ
发表于 2016-11-29 06:42:34 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?



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


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

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

29

主题

99

帖子

166

积分

注册会员

Rank: 2

积分
166
QQ
发表于 2016-11-29 06:49:28 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


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

24

主题

98

帖子

155

积分

注册会员

Rank: 2

积分
155
QQ
发表于 2016-11-29 06:58:46 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


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

21

主题

94

帖子

133

积分

注册会员

Rank: 2

积分
133
QQ
发表于 2016-11-29 07:37:55 | 显示全部楼层
JobHunting
标  题: Re: 这题怎么解好?


edge case都要考虑到的啊


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



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

本版积分规则

美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -这题怎么解好?- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -这题怎么解好?- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
Sasa.com

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

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

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

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