一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2770|回复: 16
收起左侧

Zenefits 电面

[复制链接] |试试Instant~ |关注本帖
ManitobaFarmer 发表于 2015-5-1 01:43:29 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Zenefits - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
印度人
.1point3acres缃
有点像 reverse polish notation 的变种,计算一个表达式的值的。要求自行设计表达式的数据结构并计算表达式的值。

有几种特殊情况
1. 单输入一个数,比如 [0],是合法,结果为0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
2. 单输入一个运算符也是合法的。 无数字运算的 '+', '-', '/' 结果为 0, 单个 '*' 的结果为 1.
3. 一个运算符可以有好几个计算数字。 比如输入为 ['+', 1, 2, 3],结果为1 + 2 + 3 = 6.
4. 表达式可嵌套,['+', 1, 2, ['*', 1, 3]],这样结果为 1 + 2 + 1 * 2 = 5.

输入一定合法,不用考虑给了两个连续数字却没有运算符的情况,也不用考虑除数为0的情况。
. 鍥磋鎴戜滑@1point 3 acres
我的做法为新建一个 Expression 类,用于解决输入包含运算符,数字,或者expression三种情况,这样输入就可以为一个Expresssion 的List,再用一个Queue来决定问题。不知道有没有大神有更好的做法。



面完收到要求第二轮电面的邮件,有没有大神知道这是什么意思?是面得不太好吗?

评分

3

查看全部评分

GatherNone 发表于 2015-5-1 07:59:55 | 显示全部楼层
第四种情况应该是1 + 2 + 1 * 3 = 6 吧
回复 支持 反对

使用道具 举报

 楼主| ManitobaFarmer 发表于 2015-5-1 10:59:45 | 显示全部楼层
GatherNone 发表于 2015-5-1 07:59.1point3acres缃
第四种情况应该是1 + 2 + 1 * 3 = 6 吧

恩,打错了,不好意思。
回复 支持 反对

使用道具 举报

xieqilu1989 发表于 2015-5-1 11:04:10 | 显示全部楼层
楼主,这个原始的输入带那个中括号吗?
回复 支持 反对

使用道具 举报

 楼主| ManitobaFarmer 发表于 2015-5-1 11:10:36 | 显示全部楼层
xieqilu1989 发表于 2015-5-1 11:04
楼主,这个原始的输入带那个中括号吗?

你愿意写成 String[] 的形式也可以,数据结构随便设计,能计算这么个 expression 的值就行。
回复 支持 反对

使用道具 举报

xieqilu1989 发表于 2015-5-1 11:23:42 | 显示全部楼层
ManitobaFarmer 发表于 2015-5-1 11:10
你愿意写成 String[] 的形式也可以,数据结构随便设计,能计算这么个 expression 的值就行。

我知道,我的意思是这个expression里面是否用中括号区分了不同的嵌套部分,还是没有中括号只靠字符去区分?
回复 支持 反对

使用道具 举报

 楼主| ManitobaFarmer 发表于 2015-5-1 11:27:17 | 显示全部楼层
xieqilu1989 发表于 2015-5-1 11:23
我知道,我的意思是这个expression里面是否用中括号区分了不同的嵌套部分,还是没有中括号只靠字符去区分 ...

自己想办法解决。逻辑上是有个中括号区分的,怎么实现就是面试者要处理的问题。
回复 支持 反对

使用道具 举报

xieqilu1989 发表于 2015-5-1 12:05:10 | 显示全部楼层
ManitobaFarmer 发表于 2015-5-1 11:27
自己想办法解决。逻辑上是有个中括号区分的,怎么实现就是面试者要处理的问题。

明白了!多谢啦!
回复 支持 反对

使用道具 举报

ShadowChaser 发表于 2015-5-1 12:28:58 | 显示全部楼层
那么,类似于[+, 1, 2, 3, [*, 2, 3], 6] 这种算合法输入么?
如果不算的话,我觉得逆序处理list比较简单吧
[+, 1, 2, 3, *, 2, 3, 6]  => [+, 1, 2, 3, 36] => 42. 鍥磋鎴戜滑@1point 3 acres
回复 支持 反对

使用道具 举报

 楼主| ManitobaFarmer 发表于 2015-5-1 23:18:01 | 显示全部楼层
ShadowChaser 发表于 2015-5-1 12:28
那么,类似于[+, 1, 2, 3, [*, 2, 3], 6] 这种算合法输入么?
如果不算的话,我觉得逆序处理list比较简单 ...

算,结果是 1 + 2 + 3 + (2 * 3) + 6 = 18
回复 支持 反对

使用道具 举报

Xin_walker 发表于 2015-5-2 01:30:06 | 显示全部楼层
ManitobaFarmer 发表于 2015-5-1 23:18
算,结果是 1 + 2 + 3 + (2 * 3) + 6 = 18

所以输入序列本身是有[]的吗?不然输入+, 1, 2, 3, *, 2, 3, 6, 就有[+, 1, 2, 3, [*, 2, 3], 6] 和[+, 1, 2, 3, [*, 2, 3], 6] 两种解释嘞?
回复 支持 反对

使用道具 举报

 楼主| ManitobaFarmer 发表于 2015-5-2 02:01:54 | 显示全部楼层
Xin_walker 发表于 2015-5-2 01:30
所以输入序列本身是有[]的吗?不然输入+, 1, 2, 3, *, 2, 3, 6, 就有[+, 1, 2, 3, [*, 2, 3], 6] 和[+, 1 ...
. 鍥磋鎴戜滑@1point 3 acres
所以你需要自己解决这个问题。
回复 支持 反对

使用道具 举报

summerjx 发表于 2015-5-2 13:14:10 | 显示全部楼层
请问一下用queue怎么做呢
回复 支持 反对

使用道具 举报

hami33 发表于 2015-5-7 15:34:01 | 显示全部楼层
有人能分享一个code怎么写吗?
回复 支持 反对

使用道具 举报

johnnywsd 发表于 2015-5-12 12:14:20 | 显示全部楼层
  1. class Solution:

  2.     def eval(self, expr):. visit 1point3acres.com for more.
  3.         operator = expr[0]
  4.         expr = expr[1:]
  5.         evaled_expr = []-google 1point3acres
  6.         for it in expr:
  7.             if isinstance(it, list):
  8.                 evaled = self.eval(it)
  9.                 evaled_expr.append(evaled)
  10.             else:
  11.                 evaled_expr.append(it). visit 1point3acres.com for more.
  12.         res = 0
  13.         if operator == '+':
  14.             res = sum(evaled_expr)
  15.         elif operator == '*':
  16.             res = 1
  17.             for it in evaled_expr:. more info on 1point3acres.com
  18.                 res *= it
  19.         elif operator == '-':
  20.             res = evaled_expr[0] if len(evaled_expr) > 0 else 0
  21.             for it in evaled_expr[1:]:
  22.                 res -= it
  23.         elif operator == '/':
  24.             res = evaled_expr[0] if len(evaled_expr) > 0 else 0. from: 1point3acres.com/bbs
  25.             for it in evaled_expr[1:]:
  26.                 res /= it. 1point3acres.com/bbs
  27.         return res
复制代码
Test Cases:
  1. import unittest
  2. from solution import Solution


  3. class Test(unittest.TestCase):

  4.     def test1(self):
  5.         s = Solution()
  6.         expr = ['+', 1, 2, ['*', 1, 3]]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.         res = s.eval(expr)
  8.         self.assertEqual(res, 6)

  9.     def test2(self):
  10.         s = Solution(). Waral 鍗氬鏈夋洿澶氭枃绔,
  11.         expr = ['+', 1, 2, ['*', 2, 3]]. from: 1point3acres.com/bbs
  12.         res = s.eval(expr)
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.         self.assertEqual(res, 9)
  14. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.     def test3(self):
  16.         s = Solution()
  17.         expr = ['+', ['*'], ['-'], ['/']]
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  18.         res = s.eval(expr)
  19.         self.assertEqual(res, 1)

  20.     def test4(self):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.         s = Solution()
  22.         expr = ['+', 1, 2, ['*', 2, 3], ['-', 4, 5], ['/', 8, 2]]
  23.         res = s.eval(expr). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  24.         self.assertEqual(res, 12)
  25. . more info on 1point3acres.com
  26. if __name__ == '__main__':
  27.     unittest.main(verbosity=2)
复制代码
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-17 07:21:24 | 显示全部楼层
没太想明白楼主的做法,我的想法跟johnnywsd 的类似,不过python我不熟,我用java的话就是这样一个class
class Expression{
char operator;
list<double> numbers;
list<Expression> innerExpression;
...
}

但是这样比较麻烦的是需要有一个parser 把类似 [+, 1, 2, 3, [*, 2, 3], 6]  的输入变成一个object

我没想明白怎么用“Expresssion 的List,再用一个Queue来决定问题”,我这种定义class的方法,貌似一个object就足够了
回复 支持 反对

使用道具 举报

sunnycat 发表于 2015-5-23 12:00:15 | 显示全部楼层
谢谢楼主,解法很clean
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 08:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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