由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Quant版 - An interview question(math)
相关主题
Interview question help --set partion请教一个矩阵Bound问题,谢谢
[合集] find a missing value(c++)今天jane street的面试,我挂在这一题上
Number 1~1000 with two of them missing.Two questions from GS
算法题:show path with covering set is NP-complete一道面试题:如何解释vol和delta之间的关系
问三个编程面试题请教面试题Knight Capital
[合集] 三赌徒问题one questions
[合集] 问一个定理[合集] 两个brainteaser questions 求解? 多谢.
[合集] 高盛面试题[合集] An interview question
相关话题的讨论汇总
话题: numbers话题: question话题: 砝码话题: 40话题: 天平
进入Quant版参与讨论
1 (共1页)
a***n
发帖数: 423
1
There is a list with 40 numbers from 1 to 40. If allowing only addition and
subtraction, what's the smallest subset which can represent all the numbers
in list? For example, 40 = 1+39.
t****a
发帖数: 3544
2
can it be 40 = 1 + 1 + 。。。。 + 1 ?

and
numbers

【在 a***n 的大作中提到】
: There is a list with 40 numbers from 1 to 40. If allowing only addition and
: subtraction, what's the smallest subset which can represent all the numbers
: in list? For example, 40 = 1+39.

t****a
发帖数: 3544
3
If you have 2 numbers, you will generate another two number by add and sub,
thus you will get 4 number, i.e. 2+ C_{2}^(2)*2;
Similarly, with 3 numbers, it will represent 3+C_{3}^{2}*2 = 9;
with 4 numbers, 4 + C_{4}^{2}*2 = 16;
with 5 numbers, 5 + C_{5}^{2}*2 = 25;
with 6 numbers, 6 + C_{6}^{2}*2 = 36;
with 7 numbers, 7 + C_{7}^{2}*2 = 49.
So 7 numbers should be OK.
And we need to find it.

and
numbers

【在 a***n 的大作中提到】
: There is a list with 40 numbers from 1 to 40. If allowing only addition and
: subtraction, what's the smallest subset which can represent all the numbers
: in list? For example, 40 = 1+39.

z****g
发帖数: 1978
4
This formulate a inter-changeable group because + and - are allowed at the
same time. So it is equal to the following algebra question:
find smallest subset A in X such that
A+A=X, where A+A := {a+b} for any a, b in A.
I can't remember the exact theory in algebra to decompose X, but I am sure
there is one. And it has something to do with prime number. Seems the basic
component is decided by 40 = 2 * 2 * 2 * 5
D**u
发帖数: 204
5
1,3,9,27 will do.
You can treat it as a 天平 question. And generally a 天平 question is
related to
三进制.

and
numbers

【在 a***n 的大作中提到】
: There is a list with 40 numbers from 1 to 40. If allowing only addition and
: subtraction, what's the smallest subset which can represent all the numbers
: in list? For example, 40 = 1+39.

c**********e
发帖数: 2007
6
正解。

【在 D**u 的大作中提到】
: 1,3,9,27 will do.
: You can treat it as a 天平 question. And generally a 天平 question is
: related to
: 三进制.
:
: and
: numbers

a***n
发帖数: 423
7
no duplication. only addition and subtraction are allowed.

and
numbers

【在 a***n 的大作中提到】
: There is a list with 40 numbers from 1 to 40. If allowing only addition and
: subtraction, what's the smallest subset which can represent all the numbers
: in list? For example, 40 = 1+39.

a*****h
发帖数: 484
8
Nice! What is a typical 天平 question like?

【在 D**u 的大作中提到】
: 1,3,9,27 will do.
: You can treat it as a 天平 question. And generally a 天平 question is
: related to
: 三进制.
:
: and
: numbers

D**u
发帖数: 204
9
In this question, you can treat 1,3,9,27 as 4 砝码,
and the number you want to measure as the unknown 砝码.
Put the unknown 砝码 you want to measure on the left side of 天平.
Each other 砝码 has "3" possible positions to put it:
on the left of 天平;
on the right of 天平;
or not on either side.
The relation to 三进制 comes from the "3" above.
Generally when you have n 砝码, you can measure
at most 3^n different numbers, and only (3^n-1)/2
of them are positive. This says that
3 砝码 is not enough to measure 1-40, so we have
to use at least 4 砝码.

【在 a*****h 的大作中提到】
: Nice! What is a typical 天平 question like?
a*****h
发帖数: 484
10
Thanks. What a beautiful analysis!

【在 D**u 的大作中提到】
: In this question, you can treat 1,3,9,27 as 4 砝码,
: and the number you want to measure as the unknown 砝码.
: Put the unknown 砝码 you want to measure on the left side of 天平.
: Each other 砝码 has "3" possible positions to put it:
: on the left of 天平;
: on the right of 天平;
: or not on either side.
: The relation to 三进制 comes from the "3" above.
: Generally when you have n 砝码, you can measure
: at most 3^n different numbers, and only (3^n-1)/2

M********t
发帖数: 163
11
火工头陀强啊,尤其喜欢你的expression方式。
我发现虽然有些人老喜欢回答问题,但是似乎从来没有回答到点子上过。

【在 D**u 的大作中提到】
: In this question, you can treat 1,3,9,27 as 4 砝码,
: and the number you want to measure as the unknown 砝码.
: Put the unknown 砝码 you want to measure on the left side of 天平.
: Each other 砝码 has "3" possible positions to put it:
: on the left of 天平;
: on the right of 天平;
: or not on either side.
: The relation to 三进制 comes from the "3" above.
: Generally when you have n 砝码, you can measure
: at most 3^n different numbers, and only (3^n-1)/2

t*******g
发帖数: 373
12
这条评论也很强...

【在 M********t 的大作中提到】
: 火工头陀强啊,尤其喜欢你的expression方式。
: 我发现虽然有些人老喜欢回答问题,但是似乎从来没有回答到点子上过。

1 (共1页)
进入Quant版参与讨论
相关主题
[合集] An interview question问三个编程面试题
[合集] 面试问题 (转载)[合集] 三赌徒问题
[合集] interview question[合集] 问一个定理
Excess Return Coefficient Frontier[合集] 高盛面试题
Interview question help --set partion请教一个矩阵Bound问题,谢谢
[合集] find a missing value(c++)今天jane street的面试,我挂在这一题上
Number 1~1000 with two of them missing.Two questions from GS
算法题:show path with covering set is NP-complete一道面试题:如何解释vol和delta之间的关系
相关话题的讨论汇总
话题: numbers话题: question话题: 砝码话题: 40话题: 天平