📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1534| 回复: 3
跳转到指定楼层
上一主题 下一主题
收起左侧

大家来刷题:求问一道coding题,最近被问到了...

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 pennboy 于 2016-1-14 23:57 编辑


用string形式给一个含有x,y,+,-,*,/,(, )以及用a,b,c,d等表示的数字的表达式,比如:

y = (a*x) + b

要求写一个程序输出x的表达式: x = (y-b)/a;

其中x可能出现多次,比如:y = (x+a)/b + x*c;

PS: 限制是y是linear in terms of x;

面试当时想的是先简化表达式,将所有含x的terms合并,然后parse这个string生成一
个以y为root的eval tree,然后找到x所在的node,将这个eval tree改造成以这个node
为root的eval tree,然后重建表达式,这样结果就会是x=ay-b之类的形式,不过
interviewer当时
不置可否,我当时也没写出来具体code,求大家帮忙看看有没有什么简明的解法。谢了。

上一篇:关于hash table中remove方法的递归实现问题
下一篇:欧拉回路or哈密顿回路
🔗
dukemon7 2016-1-14 20:00:21 | 只看该作者
全局:
给两个x的值,计算表达式的值,然后根据两组(x,y)直接写出直线就可以了
回复

使用道具 举报

🔗
 楼主| pennboy 2016-1-14 23:58:52 | 只看该作者
全局:
dukemon7 发表于 2016-1-14 20:00
给两个x的值,计算表达式的值,然后根据两组(x,y)直接写出直线就可以了

啊是我原题表述不清,这个是无法用代入值来求的,我把题目已经改好了。
回复

使用道具 举报

🔗
stellari 2016-1-15 09:52:51 | 只看该作者
全局:
你也提到了,如果原函数是y = kx + b,那么转换以后的结果必是x = y/k-b/k

那么,假设我们现在已经有一个算法A能够合并含x的项,那么A稍作改动,同样也能够合并不含x的项,因此,我们可以由算法A得到y = kx + b的形式。既然k和b两个字符串都已经知道了,从这里我们就能直接写出x = y/k - b/k。当然,这个形式未必是最简,所以可能还要想办法进一步化简。

面试官不置可否可能是觉得你的答案和他的想法不同,但是他又不能马上判断是否有问题。抑或他可能觉得eval tree这个东西用得没有必要。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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