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

 找回密码
 立即注册
  • 你知道麻、木吗?学问可大了
  • 中国第一颗卫星东方红一号:现在是太空垃圾吗?
  • 这种布能自动修复 再也不用担心划破衣服
  • 英国大狗重如小象:每月吃千元狗粮 还很瘦
  • 气象台主持人遭雷击:火花四溅 险些殉职
  • 中华神箭!长征五号火箭二次起航
  • 中国女游客南非突遭猎豹袭击:跪地尖叫
  • 公司被曝剽窃创意?黄磊:不清楚细节 有错会认
  • 台湾女孩6岁骑行千里丝路 9年来横越亚非、北美多国
  • 霸气!朱婷率瓦基弗夺留洋首冠 荣膺欧冠MVP
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3040|回复: 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
    米) 感觉写不下(通常写字的字体大小)




    --

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

    举报

    25

    主题

    110

    帖子

    162

    积分

    注册会员

    Rank: 2

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


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

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



    --

    24

    主题

    91

    帖子

    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++),最短能到多少。。。

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

    --

    24

    主题

    106

    帖子

    158

    积分

    注册会员

    Rank: 2

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

    主题

    222

    帖子

    246

    积分

    注册会员

    Rank: 2

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

    主题

    105

    帖子

    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

    主题

    101

    帖子

    166

    积分

    注册会员

    Rank: 2

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


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

    26

    主题

    103

    帖子

    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

    主题

    98

    帖子

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

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

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