由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 24点程序,有人能现场写出来么?
相关主题
问道题: numbers of distinct substring贡献面经 amazon, 虽然面挂了,还是攒点人品
关于leetcode: Container With Most Water这道题amazon一道面试题
FB的k-d tree面试题面经
An interview question from a well-known small company微软面经
有人做projecteuler吗?求一个Amazon经常问的问题的答案。。。
递归,一个地方不懂,programming interviews exposed,2版本,贴个FLEXTRADE的在线C++测试的题
twoSum几道a家onsite问题讨论贴
一道题,我觉得挺难有个SB interviewer和我说++i比i++好
相关话题的讨论汇总
话题: numbers话题: result话题: game话题: 10话题: expa
进入JobHunting版参与讨论
1 (共1页)
w********s
发帖数: 1570
1
input: 4个数字, a,b,c,d
output: 所有结果=24的等式,例如:24=(a+b)*(c*d)
l*********8
发帖数: 4642
2
很繁琐,如果不是事先写过,很难在45分钟内写好。
l*********8
发帖数: 4642
3
单单把二叉树输出为算术表达式(没有冗余括号》, 就可以作为面试coding的一道题
目了。
s*********5
发帖数: 514
4
如果只有4个数字的话,一共24个顺序X64种变化,brute force OK了吧
s*********5
发帖数: 514
5
如果只有4个数字的话,一共24个顺序X64种变化,brute force OK了吧
s*********5
发帖数: 514
6
如果只有4个数字的话,一共24个顺序X64种变化,brute force OK了吧
p*****2
发帖数: 21240
7
对呀。好像就是brute force呀
g**********y
发帖数: 14569
8
准备面试的标准应该做到可以写,不是真写完,但应该把框架写出来。
写成接近可运行的程序,45分钟要求有点高,但也不算太离谱。那次谁贴的Amazon的计
算机多个加油站之间距离的,我觉得比这个难多了。大家在版上讨论了很久。碰上那种
题,绝对是人品问题了。

【在 w********s 的大作中提到】
: input: 4个数字, a,b,c,d
: output: 所有结果=24的等式,例如:24=(a+b)*(c*d)

m***n
发帖数: 2154
9
a*(b+c)/d
这个还要考虑括号吧。

【在 s*********5 的大作中提到】
: 如果只有4个数字的话,一共24个顺序X64种变化,brute force OK了吧
l*********8
发帖数: 4642
10
In addition, the output should not contains duplications even if there are
duplicated numbers.
For example,
6 6 6 6
we don't want to output 6+6+6+6 for 24 times.

【在 m***n 的大作中提到】
: a*(b+c)/d
: 这个还要考虑括号吧。

相关主题
递归,一个地方不懂,programming interviews exposed,2版本,贡献面经 amazon, 虽然面挂了,还是攒点人品
twoSumamazon一道面试题
一道题,我觉得挺难面经
进入JobHunting版参与讨论
p*****2
发帖数: 21240
11

明白什么意思了。

【在 m***n 的大作中提到】
: a*(b+c)/d
: 这个还要考虑括号吧。

m***n
发帖数: 2154
12
这个好办,直接表达式压入set就行了。
其实a*(b+c)/d的情况也是可以解决的。不用考虑括号。
a*(b+c)/d 等同于
b+c*a/d 每次evaluate表达式直接从左往右evaluate.
那么只要穷举了所有的abcd排列, 然后3个符号位置组合就行了。

【在 l*********8 的大作中提到】
: In addition, the output should not contains duplications even if there are
: duplicated numbers.
: For example,
: 6 6 6 6
: we don't want to output 6+6+6+6 for 24 times.

l*********8
发帖数: 4642
13
if depends on if the interviewer thinks
a*(b+c)/d and (b+c)*a/d are different or not.

【在 m***n 的大作中提到】
: 这个好办,直接表达式压入set就行了。
: 其实a*(b+c)/d的情况也是可以解决的。不用考虑括号。
: a*(b+c)/d 等同于
: b+c*a/d 每次evaluate表达式直接从左往右evaluate.
: 那么只要穷举了所有的abcd排列, 然后3个符号位置组合就行了。

y****n
发帖数: 743
14
粗想了一下,我会把算24列成两个公式:
((a +-*/ b) +-*/ c) +-*/ d
或者 (a +- b) */ (c +- d)
这样循环穷举可在短时间搞定。
c****p
发帖数: 6474
15
我以前尝试用MATLAB写过,不太成功
基本思路是递归,把四元变成三元,把三元变成两元。
但是这样的不可能找到形如(a+b) * (c+d)这样的解。
另外,因为浮点数精度的问题,对于3 3 7 7 可能找不到(3 + 3/7) * 7这样的解

【在 w********s 的大作中提到】
: input: 4个数字, a,b,c,d
: output: 所有结果=24的等式,例如:24=(a+b)*(c*d)

l*********8
发帖数: 4642
16
how about a*/b +- c*/d

【在 y****n 的大作中提到】
: 粗想了一下,我会把算24列成两个公式:
: ((a +-*/ b) +-*/ c) +-*/ d
: 或者 (a +- b) */ (c +- d)
: 这样循环穷举可在短时间搞定。

g*********e
发帖数: 14401
17
貌似挺难的 有标准解吗
h****e
发帖数: 928
18
我觉得用C++/Java基本上写不出来,但是用Perl、Python、Ruby
之类的scripting languages可能可以。
y****n
发帖数: 743
19
good catch! 我当时想的不够严谨,可能还有漏掉的情况。

【在 l*********8 的大作中提到】
: how about a*/b +- c*/d
b******u
发帖数: 81
20
暴力解. Binary Tree.
3+5+7+9
(3+9)*(7-5)
5*9-3*7
9*(5-7/3)
2+4+8+10
(4*10+8)/2
(10-4)*8/2
2-10+4*8
4*8-10+2
2-(10-4*8)
2*10-(4-8)
(2+10)/(4/8)
(2+10)*8/4
(8/4+10)*2
2*10+8-4
(2+10)*8/4
4*10-2*8
(2*8-10)*4
4*(10-8/2)
8/2*(10-4)
(10-4)/2*8
8/(2/(10-4))
(2+10)/4*8
8/(4/(2+10))
(10-2)*4-8
(10-4)/(2/8)
(3/7+3)*7
5*(5-1/5)
相关主题
微软面经几道a家onsite问题讨论贴
求一个Amazon经常问的问题的答案。。。有个SB interviewer和我说++i比i++好
贴个FLEXTRADE的在线C++测试的题那个24 game given 4 number用= - × /的题
进入JobHunting版参与讨论
l*********8
发帖数: 4642
21
你这个答案看起来不错啊。
你的程序是怎么知道9*5-7*3只是5*9-3*7的trivial variation的?

【在 b******u 的大作中提到】
: 暴力解. Binary Tree.
: 3+5+7+9
: (3+9)*(7-5)
: 5*9-3*7
: 9*(5-7/3)
: 2+4+8+10
: (4*10+8)/2
: (10-4)*8/2
: 2-10+4*8
: 4*8-10+2

l*********8
发帖数: 4642
22
为什么输出两次(2+10)*8/4 ?

【在 b******u 的大作中提到】
: 暴力解. Binary Tree.
: 3+5+7+9
: (3+9)*(7-5)
: 5*9-3*7
: 9*(5-7/3)
: 2+4+8+10
: (4*10+8)/2
: (10-4)*8/2
: 2-10+4*8
: 4*8-10+2

b******u
发帖数: 81
23
用 bool IsSameFor24 ( OperationNode node1, OperationNode node2 )
对 + *, 检查左右互换后是否相同。
也检查了 a + ( b + c ) = ( a + c ) + b 的情况。
有五种TREE
(a - b) - (c - d)
a - ( b - ( c -d ) )
a - ( (b - c) -d )
((a - b) - c) -d
(a - (b - c)) -d


【在 l*********8 的大作中提到】
: 你这个答案看起来不错啊。
: 你的程序是怎么知道9*5-7*3只是5*9-3*7的trivial variation的?

l*********8
发帖数: 4642
24
你是把每个符合条件的答案存起来。生成新答案的时候,和已有答案逐个相比吧?
那为什么输出两次(2+10)*8/4 ?

【在 b******u 的大作中提到】
: 用 bool IsSameFor24 ( OperationNode node1, OperationNode node2 )
: 对 + *, 检查左右互换后是否相同。
: 也检查了 a + ( b + c ) = ( a + c ) + b 的情况。
: 有五种TREE
: (a - b) - (c - d)
: a - ( b - ( c -d ) )
: a - ( (b - c) -d )
: ((a - b) - c) -d
: (a - (b - c)) -d
:

b******u
发帖数: 81
25
是的。
我猜原因是 有两个TREE 31 和 22. TREE 本身不同,但结果相同。
( ( 2 + 10 ) * 8 ) /4
( ( 2 + 10 ) * ( 8 /4 )

【在 l*********8 的大作中提到】
: 你是把每个符合条件的答案存起来。生成新答案的时候,和已有答案逐个相比吧?
: 那为什么输出两次(2+10)*8/4 ?

l*********8
发帖数: 4642
26
知道了。然后你输出的时候去掉了不必要的括号(的确应该),就造成一模一样的两个
答案了。

【在 b******u 的大作中提到】
: 是的。
: 我猜原因是 有两个TREE 31 和 22. TREE 本身不同,但结果相同。
: ( ( 2 + 10 ) * 8 ) /4
: ( ( 2 + 10 ) * ( 8 /4 )

r*****g
发帖数: 478
27
That's an interesting thought..
用scripting L的不同在哪里?

【在 h****e 的大作中提到】
: 我觉得用C++/Java基本上写不出来,但是用Perl、Python、Ruby
: 之类的scripting languages可能可以。

l***i
发帖数: 1309
28
It is easier if you use postfix or prefix notation, then you have no ( ) to
deal with, 3 operators and 4 operands, 7! is small
just write eval_postfix() and in the function check whether it is a valid
postfix or not
h****e
发帖数: 928
29
Scripting languages的强项在于可以做真正的very-high level programming.
举Ruby为例:
- 生成所有的permutations:
a=[1,2,3]
a.permutation.to_a
- Set的操作:
require 'set'
s1 = Set.new [1, 2]
s1.merge([2, 6])
很多在C++/Java里面要一大段代码的,在这些scripting中一句话就解决了。
Google的Peter Norvig有一篇非常经典的文章,就是讲如何只用一小页的
Python代码来解决所有的Sudoku:
http://norvig.com/sudoku.html

【在 r*****g 的大作中提到】
: That's an interesting thought..
: 用scripting L的不同在哪里?

x*******5
发帖数: 152
30
这个编程之美第一章16题是答案, python代码如下
from __future__ import division
def Point_Game(n,numbers,result,Value):
"Implement 24-point game"
if n==1:
if math.fabs(numbers[0]-Value)<0.0001:
print result[0]
return True
else: return False

for i in range(n):
for j in range(i+1,n):
a,b=numbers[i],numbers[j]
expa,expb=result[i],result[j]
numbers[j]=numbers[n-1]
result[j]=result[n-1]

result[i]='('+expa+'+'+expb+')'
numbers[i]=a+b
if Point_Game(n-1,numbers,result,Value):
return True

result[i]='('+expa+'-'+expb+')'
numbers[i]=a-b
if Point_Game(n-1,numbers,result,Value):
return True

result[i]='('+expb+'-'+expa+')'
numbers[i]=b-a
if Point_Game(n-1,numbers,result,Value):
return True

result[i]='('+expa+'*'+expb+')'
numbers[i]=a*b
if Point_Game(n-1,numbers,result,Value):
return True

if b:
result[i]='('+expa+'/'+expb+')'
numbers[i]=a/b
if Point_Game(n-1,numbers,result,Value):
return True

if a:
result[i]='('+expb+'/'+expa+')'
numbers[i]=b/a
if Point_Game(n-1,numbers,result,Value):
return True

numbers[i]=a
numbers[j]=b
result[i]=expa
result[j]=expb

return False
测试:
numbers=[6,6,6,6]
results=[]
for n in numbers:
results.append(str(n))
Recur.Point_Game(4, numbers, results, 24)
Output:
(((6+6)+6)+6)
测试: numbers=[1,3,4,6]--->(6/(1-(3/4)))
numbers=[3,3,8,8]-->(8/(3-(8/3)))
numbers=[3,3,7,7]-->(((3/7)+3)*7)
测试用例是google最难算的24点
基本idea是back-tracking,这个程序可以在45分钟内写出来吧,欢迎找bug
相关主题
新鲜店面L关于leetcode: Container With Most Water这道题
发Q家面经FB的k-d tree面试题
问道题: numbers of distinct substringAn interview question from a well-known small company
进入JobHunting版参与讨论
x*******5
发帖数: 152
31
好像要所有结果啊,我再想想
1 (共1页)
进入JobHunting版参与讨论
相关主题
有个SB interviewer和我说++i比i++好有人做projecteuler吗?
那个24 game given 4 number用= - × /的题递归,一个地方不懂,programming interviews exposed,2版本,
新鲜店面LtwoSum
发Q家面经一道题,我觉得挺难
问道题: numbers of distinct substring贡献面经 amazon, 虽然面挂了,还是攒点人品
关于leetcode: Container With Most Water这道题amazon一道面试题
FB的k-d tree面试题面经
An interview question from a well-known small company微软面经
相关话题的讨论汇总
话题: numbers话题: result话题: game话题: 10话题: expa