美国华人网FuninUSA|唐人社区|北美华人论坛:找好货,找礼品卡,找折扣,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 大雨后千足虫疯狂钻出地面:爬满围墙
  • 恐怖:大二女生经常熬夜聊天致暴盲
  • 步兵冲锋时 后方机枪为什么打不到自己人?
  • 小熊为偷吃甜甜圈拆掉汽车保险杠 结果让人心疼
  • 见过树懒游泳吗?比陆地快3倍!
  • 买买买!港服Xbox和Windows 10商店正式支持支付宝
  • 马凯驻足阿里巴巴数博会展馆近10分钟 点赞工业大脑
  • 顺丰扩张全球:巨资与世界第一快递UPS成立合资公司
  • 荣威eRX5纯电动版来了:综合续航超320km
  • 奔驰新GLA下线:6月上市 外形升级
  • Total (NYSE:TOT):一个不错的买入选择
  • NVIDIA获软银40亿美元撑腰
  • 你相信吗?特斯拉股价可能飙升至500美元
  • 石油是否下行还得看中国“脸色”
  • 比特币:现在加入似乎很危险
  • 比特币反弹继续……2500美元不是终点
  • 今天的股票市场,投资者该怎么选择
  • 震惊!余额宝资金规模超一万亿其最高存款额度上限降至25万
  • 零售类股价没有最低,只有更低……
  • 德州华人中餐馆老板逃税16万美金
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3048|回复: 21

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

[复制链接]

17

主题

39

帖子

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




--

【思科/IBM/EMC/Juniper采购群】592532555
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

26

主题

111

帖子

167

积分

注册会员

Rank: 2

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


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

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



--

24

主题

92

帖子

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

帖子

163

积分

注册会员

Rank: 2

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


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

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

--

24

主题

110

帖子

162

积分

注册会员

Rank: 2

积分
162
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
米) 感觉写不下(通常写字的字体大小)     




--

8

主题

225

帖子

244

积分

中级会员

Rank: 3Rank: 3

积分
244
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)的
--

22

主题

106

帖子

159

积分

注册会员

Rank: 2

积分
159
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对应的值。
--

27

主题

106

帖子

166

积分

注册会员

Rank: 2

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


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

25

主题

106

帖子

165

积分

注册会员

Rank: 2

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


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

21

主题

101

帖子

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|唐人社区

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

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