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

 找回密码
 立即注册
  • 网曝古力娜扎行李箱内容图 随身携带烤馕牛肉干
  • 陈乔恩自夸天生车手 雨天夜路70公里用45分钟
  • 李晨工作19小时体力不支 范冰冰心疼成这样了
  • 张馨予发鸡汤文:请原谅我这一生 爱憎太分明
  • 中国军机注意了,你们将在钓鱼岛以一敌四!
  • 赵又廷人气高遭围堵 粉丝入戏喊:夜华!你不能死
  • 神经病?网络女主播为红直播跳楼秀
  • 高中生续写《红楼梦》获一等奖 太有才了!
  • “二月二龙抬头”:吃龙鳞饼 “剃龙头”盼好运
  • 乐天明日移交“萨德”用地,将“对抗中国”进行到底!
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3027|回复: 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
    米) 感觉写不下(通常写字的字体大小)




    --

    【中国海淘拼单总群】36382164
    回复 百度谷歌雅虎搜狗搜搜有道360奇虎

    举报

    23

    主题

    103

    帖子

    152

    积分

    注册会员

    Rank: 2

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


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

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



    --

    23

    主题

    88

    帖子

    144

    积分

    注册会员

    Rank: 2

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

    主题

    109

    帖子

    156

    积分

    注册会员

    Rank: 2

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


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

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

    --

    22

    主题

    99

    帖子

    148

    积分

    注册会员

    Rank: 2

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

    主题

    212

    帖子

    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

    主题

    101

    帖子

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

    28

    主题

    98

    帖子

    162

    积分

    注册会员

    Rank: 2

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


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

    20

    主题

    91

    帖子

    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

    主题

    93

    帖子

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

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

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