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

 找回密码
 立即注册
  • 杨幂刘恺威再生二胎?公公刘丹这样回应…
  • 1岁咘咘登名校考题!贾静雯:怎么知道我爱草莓
  • 自拍露出白发!舒淇喊话粉丝见证她变老
  • 韩歌手IU和男友3年恋情告吹 各忙事业关系疏远
  • 超霸气!范冰冰一听吴亦凡受伤 秒问:你在哪?
  • 刚满月的儿子要网购?陈妍希一孕傻三年模式开启
  • 马伊琍罕见晒3岁小女儿近照 小公主乖巧可爱
  • 朱丹晒素颜自拍 卸了妆根本就是换了个人
  • 罗志祥深夜泄感情状态 要给女友颁“终身成就奖”
  • 多多帮妹妹装饰柜子 网友:这样的好姐姐来一沓
  • 特朗普反弹并没有结束
  • 推动市场的最大驱动力
  • 星期一上午重要的投资事件
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3022|回复: 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
米) 感觉写不下(通常写字的字体大小)




--

【COACH美国代购总群】99634155
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

22

主题

101

帖子

149

积分

注册会员

Rank: 2

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


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

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



--

22

主题

87

帖子

138

积分

注册会员

Rank: 2

积分
138
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

主题

108

帖子

156

积分

注册会员

Rank: 2

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


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

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

--

21

主题

97

帖子

137

积分

注册会员

Rank: 2

积分
137
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

主题

209

帖子

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)的
--

19

主题

100

帖子

130

积分

注册会员

Rank: 2

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

26

主题

95

帖子

149

积分

注册会员

Rank: 2

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


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

20

主题

90

帖子

141

积分

注册会员

Rank: 2

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


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

21

主题

90

帖子

133

积分

注册会员

Rank: 2

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


edge case都要考虑到的啊


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



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

本版积分规则

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

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

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

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

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