请教2个面试问题的回答 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Actuary - 精算

请教2个面试问题的回答

请教2个面试问题的回答# Actuary - 精算

f*p2012-04-17 07:04

1 楼

自君之出矣，愁云覆东岭。思君若残辉，丝丝缠暮影
自君之出矣，行道风渐冷。思君如乱雪，纷纷结尘境

h*y2012-04-17 07:04

2 楼

听了老先生的分析，周先生的眼睛腾地就红了。他一边用力地搓着双手，一边不断地自
责，为自己的粗心而忏悔。
周先生和他的家人一直错误地认为，济坤所有的痛苦和所有的改变都源于她和那个男生
完全不该发生的恋情。令他们感到疑惑的是，如果济坤喜欢那个男生，愿意和他在一
起，对他们的未来充满期待，为什么从来没有见到她像其他热恋中的女孩那样越来越温
柔、越来越可爱？为什么从来没见她有满怀喜悦和甜蜜笑容？如果济坤不喜欢那个男
生，为什么要为了资助他读书而辛辛苦苦地打几份工？为什么总是对家人说他们很快就
要结婚了？为什么总是担心家人会拆散他们？
想到这里，周先生的脑门上冒出了冷汗。他呆呆地看着老先生却好似自言自语地说：“
对啊。我们从心里不喜欢那个男生，觉得他和济坤不般配，可我们还是尊重济坤的选
择，从来没有强行干预过他们的事情。”周先生接连叹了几声，又抹了一把额头上的汗
珠，继续说：“在这之前我怎么就没想到，济坤如此孤注一掷地去恋爱，如此难为自
己地去恋爱，正是因为她的心理出了问题呢？我们从来没有干预过她，但她始终说不要
我们管，不要我们阻拦她。原来，是她的假想欺骗了她。她把她心里想到的可能性都
当成了已经发生或即将发生的事情，这活得有多辛苦又有多痛苦啊！”
烦乱的心绪使得周先生语无伦次，但深谙心理学的老先生还是听懂了他的意思。他轻轻
地拍了拍周先生的肩膀，语重心长地说：“孩子，不要自责了，尽早解决问题就是了
。过去的这二三十年以来，你和你的家人活得都不轻松。依我看，你的心理问题也比较
严重，只不过，你比别人更坚忍、更能克制自己，所以没有出什么大问题。”
老先生站起身，在房间里踱了几个来回后又重新坐下来，继续说道：“之前我反复地问
你，你爱人的身体状况、精神状况和心理状况如何，你都说她还好，虽然一直为济坤
担心，但情绪很稳定，精神既不亢奋也不萎靡。我告诉你，到现在为止，我最为担心的
除了济坤还有你的爱人。我无法想象，一个因为痛失儿子而导致精神出现过严重问题
的女人，这二三十年以来生活在你们这样的表面上祥和、温馨实际上极度压抑的家庭氛
围里，她是怎样进行自我调节又是怎样保持这种平和、稳定的状态的。”
听了老先生的话，周先生的眼睛更红了。他一把抓住了老先生的手，用力地握着，哽咽
道：“老先生，您担心的事情也是我越来越担心的事情！都怪我，混啊！过去我以为
，一些事，一些伤，只要不再提起，不去触碰，它就会慢慢消失，就再也不会痛。前几
天见了一位老同事后我才开始反思，过去那些年，我实在是委屈了她，让她受苦了！
”周先生低下头，任几滴泪水滴在他和老先生的手背上，继续说道，“现在想一想，何
止是济坤和她的妈妈？就是我的儿子济民，也一直饱受着心灵和精神之痛的折磨啊。”
“你已经发现了问题，这就好，这就好。”老先生见周先生早已注意到了这个问题，欣
慰地笑了笑，安慰他道，“依据你们家的实际情况，我想到了一个解决问题的办法。
这个办法与我以往治疗心理疾病的方法都不相同，但我相信，如果进展顺利的话，这个
办法可以在帮助济坤解除心理障碍的同时帮助她的母亲卸载压在她生命中的种种负累
，让她开始轻松的生活。”
老先生考虑得如此周到，让周先生满怀惊喜又满怀感恩。他接受了老先生的建议，答应
用他那独特的办法来解决济坤的心理问题，同时帮助妻子卸载负累，还她轻松愉快的生
活。
没想到，世间事瞬息万变。就在周先生努力寻找机会，即将按照老先生的建议开始行动
的时候，济坤的精神濒临崩溃，做出了自残的傻事。在接到女儿自残的消息后，周先
生一边驱车赶往医院，一边给老先生打电话说明了情况，并向老先生求教，现在他应该
怎么办？是把这次发生的状况当作一次机会，按照原计划开始行动，还是等济坤的伤
口好起来再做打算？
听周先生说完，老先生平静地说：“小周，你靠边停车，我要和你说几句话。我必须确
切地知道，你有没有能力按照原计划开始行动。”
待周先生停好车后，老先生郑重地问：“小周，我知道你很坚强，很坚忍，但我还是要
再问你一遍这个问题。你要好好考虑考虑再回答我，你确信你完全能够像你之前答应
我的那样，不论她们母女之间发生怎样的状况，你都能狠下心来‘躲’出家门，任她们
母女两个单独面对，自行解决问题吗？你能狠下心来吗？”
“您能保证，只要给她们母女两个单独面对的机会，她们完全有能力解决彼此的问题吗
？”周先生大口大口地喘着粗气，声音不知不觉地就颤抖了起来。
“是的。我能保证！”老先生斩钉截铁地说，“没有哪一对母女如她们这样，彼此深爱
、彼此信任，却又极少亲密地单独相处，从来没有说过悄悄话；没有哪一对母女如她
们这样，始终是母亲照料女儿，女儿从来没有为母亲做过任何一件事情。你要知道，事
实上，这一对母女都是有爱、懂爱、需要爱与被爱的人。尤其是济坤，她是一个极度
需要被家人需要的孩子。与一味地接受爱比较而言，济坤更需要被家人需要、更需要有
机会为家人做些什么，尤其是为母亲做些什么。因为，只有这样，她才能够确定，她
的存在对于母亲、对于周家来说有着无可替代的意义。你要相信我，更要相信她们！”
尽管，老先生斩钉截铁地向周先生保证，只要他肯把时间交给她们母女俩儿，她们一定
可以用自己的方式解决问题；尽管，周先生也斩钉截铁地向老先生保证，哪怕不忍心
，哪怕不放心，他也要铤而走险，让她们母女俩独处一个晚上，可是，当他咬紧牙关对
妻子说，公司里有点急事，他必须临时出一趟差的时候，他的声音还是哽咽了。
躺在床上的妻子盯着他的脸，虚弱地笑了笑，对他说：“你去忙吧，不要担心我和济坤
。待我休息一会，身体有些力气了，我会照料她的。”
周先生握住妻子的手，将面颊贴在妻子的胸前，轻声说道：“老婆，辛苦你了！我希望
等我回来，一切都好起来了。”
“去吧。我相信，等你回来，一切都会好起来的。”妻子的声音很轻，却也很重。
周先生含着泪水点了点头。当他咬着牙根一步一步地走出他们的房间，一步一步地来到
济坤的门前时，济坤正挥起拳头砸向自己那受伤的手指。而当济坤的拳头落下后，她的
身体剧烈地抽搐之时，周先生也感到了一阵眩晕。

c*t2012-04-17 07:04

3 楼

【以下文字转载自 JobHunting 讨论区】
发信人: cookiesweet (apple), 信区: JobHunting
标题: 关于那个经典的missing number的题
发信站: BBS 未名空间站 (Tue Jun 28 03:25:50 2011, 美东)
到底是什么？哪里有具体的描述？
是不是指的是下面的三个问题？
1. 给定数组size 是 n-1, 1,....n中的一个数missing, 求如何找出那个missing
number?
2. 给定数组size 是 n-2, 1,....n中的两个数missing, 求如何找出那两个missing
numbers?
3. 给定数组size 是 n-m, 1,....n中的m个数missing, 求如何找出那个m个missing
numbers? (假设 m < n/2).
是不是上面的题都有O(n) solution?

i*W2012-04-17 07:04

4 楼

Do you want to be a leader in the future?
Would you rather risk missing an important deadline and ensure accuracy or
meet your deadline and risk inaccuracies?
谢谢！

L*o2012-04-17 07:04

5 楼

赞图与文

【在 f*******p 的大作中提到】

: 自君之出矣，愁云覆东岭。思君若残辉，丝丝缠暮影
: 自君之出矣，行道风渐冷。思君如乱雪，纷纷结尘境

G*A2012-04-17 07:04

6 楼

如果不考虑空间上的开销(extra space of size n),时间复杂度上很容易控制到O(n) -
counting sort?
但是如果想把空间开销控制在O(1),同时时间复杂度控制到O(n)，暂时没想到好办法...

【在 c*********t 的大作中提到】

: 【以下文字转载自 JobHunting 讨论区】
: 发信人: cookiesweet (apple), 信区: JobHunting
: 标题: 关于那个经典的missing number的题
: 发信站: BBS 未名空间站 (Tue Jun 28 03:25:50 2011, 美东)
: 到底是什么？哪里有具体的描述？
: 是不是指的是下面的三个问题？
: 1. 给定数组size 是 n-1, 1,....n中的一个数missing, 求如何找出那个missing
: number?
: 2. 给定数组size 是 n-2, 1,....n中的两个数missing, 求如何找出那两个missing
: numbers?

s*02012-04-17 07:04

7 楼

1) yes 吧
2）meet deadline?

f*p2012-04-17 07:04

8 楼

多谢鼓励，还请多多指教

【在 L****o 的大作中提到】

: 赞图与文

g*y2012-04-17 07:04

9 楼

全加起来是不是和sort一样，算nlogn呢？

-
...

【在 G****A 的大作中提到】

: 如果不考虑空间上的开销(extra space of size n),时间复杂度上很容易控制到O(n) -
: counting sort?
: 但是如果想把空间开销控制在O(1),同时时间复杂度控制到O(n)，暂时没想到好办法...

Y*H2012-04-17 07:04

10 楼

say yes and tell them you are willing to work hard to get there. don't sound
like you deserve it automatically.
one of the precept is to control work product...but i think the best answer
is to talk to your boss and possibly extend the deadline.

【在 i***W 的大作中提到】

: Do you want to be a leader in the future?
: Would you rather risk missing an important deadline and ensure accuracy or
: meet your deadline and risk inaccuracies?
: 谢谢！

l*12012-04-17 07:04

11 楼

写的不错，欢迎去文海征文。

【在 f*******p 的大作中提到】

: 多谢鼓励，还请多多指教

t*t2012-04-17 07:04

12 楼

你把N个数加起来为什么需要N log N?

【在 g*****y 的大作中提到】

: 全加起来是不是和sort一样，算nlogn呢？
:
: -
: ...

s*t2012-04-17 07:04

13 楼

真有味道，加一个积分

【在 f*******p 的大作中提到】

: 多谢鼓励，还请多多指教

g*y2012-04-17 07:04

14 楼

如果N很大的话，位数就多，位数不就是logN么。所以和所谓的
bucket sort差不多，如果N不是很大，可以认为O(1)。如果
N真的很大，那就应该是logN了吧？

【在 t****t 的大作中提到】

: 你把N个数加起来为什么需要N log N?

i*s2012-04-17 07:04

15 楼

好诗！图片和诗配得很好，有意境!

t*t2012-04-17 07:04

16 楼

严格的说这样当然也对了, 不过一般都不这么算吧.

【在 g*****y 的大作中提到】

: 如果N很大的话，位数就多，位数不就是logN么。所以和所谓的
: bucket sort差不多，如果N不是很大，可以认为O(1)。如果
: N真的很大，那就应该是logN了吧？

b*92012-04-17 07:04

17 楼

气势大而用情深，不流于空泛，赞

D*a2012-04-17 07:04

18 楼

Is it possible to do 3 in O(n) time and O(m) space for arbitrary m
【在 c*********t 的大作中提到】

P*e2012-04-17 07:04

19 楼

这哪对了?

【在 t****t 的大作中提到】

: 严格的说这样当然也对了, 不过一般都不这么算吧.

g*y2012-04-17 07:04

20 楼

哦，哪不对了？加两个一千多位的数，不得是（1000×常数）左右的运算量？

【在 P********e 的大作中提到】

: 这哪对了?

G*A2012-04-17 07:04

21 楼

complexity的定义不是这样的。
这道题网上有讨论，你自己艘艘

【在 g*****y 的大作中提到】

: 哦，哪不对了？加两个一千多位的数，不得是（1000×常数）左右的运算量？

s*v2012-04-17 07:04

22 楼

BigInteger好像就是这么做的吧

【在 t****t 的大作中提到】

: 严格的说这样当然也对了, 不过一般都不这么算吧.

b*h2012-04-17 07:04

23 楼

那加3个哪，加4个，。。。，加n个？

【在 g*****y 的大作中提到】

: 哦，哪不对了？加两个一千多位的数，不得是（1000×常数）左右的运算量？

g*y2012-04-17 07:04

24 楼

那不就是我说的nlogn了么？？？？ @[email protected]

【在 b********h 的大作中提到】

: 那加3个哪，加4个，。。。，加n个？

g*y2012-04-17 07:04

25 楼

哦，complexity 有新的定义了么？看来我又过时了。呵呵

【在 G****A 的大作中提到】

: complexity的定义不是这样的。
: 这道题网上有讨论，你自己艘艘

h*c2012-04-17 07:04

26 楼

好像可以binary search 伐？
log (n) not necessarily m log (n).

【在 c*********t 的大作中提到】

G*A2012-04-17 07:04

27 楼

complexity: Number of basic operations performed as a function of problem
size. 如果the problem (of size n) requires n次"+"运算, complexity 就是O(n),我
不明白跟位数有什么关系？
你说的“如果N很大的话，位数就多，位数不就是logN么”。你是不是把size of problem和size of
operand混淆了..?

【在 g*****y 的大作中提到】

: 哦，complexity 有新的定义了么？看来我又过时了。呵呵

t*t2012-04-17 07:04

28 楼

basic operation implies that input is bounded in a proper range. for not-so-
big number, adding 2 number is a basic operation. that's the common case.
however there exists cases that adding 2 very big number is multiple basic
operations. for example, doing encrypt/decrypt, often you need to deal with
1024-bit numbers. obviously the number of bit is a big factor of complexity.

,我
problem和size of

【在 G****A 的大作中提到】

: complexity: Number of basic operations performed as a function of problem
: size. 如果the problem (of size n) requires n次"+"运算, complexity 就是O(n),我
: 不明白跟位数有什么关系？
: 你说的“如果N很大的话，位数就多，位数不就是logN么”。你是不是把size of problem和size of
: operand混淆了..?

p*o2012-04-17 07:04

29 楼

Maybe, construct a polynomial with the missing numbers as roots
and then solve it.

【在 D*******a 的大作中提到】

: Is it possible to do 3 in O(n) time and O(m) space for arbitrary m

P*e2012-04-17 07:04

30 楼

麻烦你证明一下,你们所说的加法复杂度: O (logN)

so-
with
complexity.

【在 t****t 的大作中提到】

: basic operation implies that input is bounded in a proper range. for not-so-
: big number, adding 2 number is a basic operation. that's the common case.
: however there exists cases that adding 2 very big number is multiple basic
: operations. for example, doing encrypt/decrypt, often you need to deal with
: 1024-bit numbers. obviously the number of bit is a big factor of complexity.
:
: ,我
: problem和size of

P*e2012-04-17 07:04

31 楼

不知道他们的理论从什么地方来的,反正算法理论上你的对的.

,我
problem和size of

【在 G****A 的大作中提到】

t*t2012-04-17 07:04

32 楼

the original problem is to add 1~N. the maximum bit width is propotional to
logN, of course.

【在 P********e 的大作中提到】

: 麻烦你证明一下,你们所说的加法复杂度: O (logN)
:
: so-
: with
: complexity.

P*e2012-04-17 07:04

33 楼

要证明sum(1~N) 复杂度是O(NlogN),需要证明加法复杂度O (logN)
只想说,这是不对的.不知道你们从什么地方学的.
BTW, 你对他比对我友善多了.....

to

【在 t****t 的大作中提到】

: the original problem is to add 1~N. the maximum bit width is propotional to
: logN, of course.

G*A2012-04-17 07:04

34 楼

thanks for clarifying. Now, I see how we understand it differently:

G*A2012-04-17 07:04

35 楼

严格来说，他们说的是# of computations, 我们说的是computational complexity。

【在 P********e 的大作中提到】

: 不知道他们的理论从什么地方来的,反正算法理论上你的对的.
:
: ,我
: problem和size of

g*y2012-04-17 07:04

36 楼

其实我最初以为你想到全加的做法，但是你说你不知道怎么实现O(N)运算量，O(1)
storage的方法，我就想你是不是认为一次加法是O(logN)。现在看来不是这样，呵呵
另外，complexity 就是 # of basic operations，没有区别的。
比方说，字符串搜索问题，不管字符串有多长，每个字符就是8bit或32bit，不会有
变化，所以一次字符比较可以认为是常数运算量。
再比方sorting，不管sort多少个数，所有的数可以都采用float（4bytes），即使
数据个数超出2^32, 只是数串里有重复而已，并不影响sorting，所以可以认为一次比较
是常数运算量。
这个题里面，数据个数和数据范围是直接相关的（相等），这种情况，我们严格来说，
当然
不能认为加法是常数运算量了，对不对？
举个例子，这题另一种做法是全部数乘起来跟N!做个除法，也能找出missing number，
但是你如果还是不考虑溢出的可能性的话，或者仍然认为乘法是常数运算量的话，
是不是有点太搞笑了？而且这题里面不管乘法加法，都是不能有任何精度损失，所以我们
不能说把数转成float来算，是不是？

【在 G****A 的大作中提到】

: 严格来说，他们说的是# of computations, 我们说的是computational complexity。

t*t2012-04-17 07:04

37 楼

不用在意gagama和paulpierce说什么, 你说的他们听不懂是很正常的.

比较

【在 g*****y 的大作中提到】

: 其实我最初以为你想到全加的做法，但是你说你不知道怎么实现O(N)运算量，O(1)
: storage的方法，我就想你是不是认为一次加法是O(logN)。现在看来不是这样，呵呵
: 另外，complexity 就是 # of basic operations，没有区别的。
: 比方说，字符串搜索问题，不管字符串有多长，每个字符就是8bit或32bit，不会有
: 变化，所以一次字符比较可以认为是常数运算量。
: 再比方sorting，不管sort多少个数，所有的数可以都采用float（4bytes），即使
: 数据个数超出2^32, 只是数串里有重复而已，并不影响sorting，所以可以认为一次比较
: 是常数运算量。
: 这个题里面，数据个数和数据范围是直接相关的（相等），这种情况，我们严格来说，
: 当然

N*n2012-04-17 07:04

38 楼

1) If there is 1 missing then find it in O(N) using divide and conquer.
method: use n/2 as pivot to swap & split the array. Find out which half
is short by one. Re-swap and re-split the missing half til you find the
missing # out. The complexity is N + n/2 + n/4 ... = 2N which is O(N).
2) If there are 2 missing then S&S the array with n/2. If both halves are
short by one then you reduce the problem to two type-1 problems of half
the size so the complexity is N + 2(N/2) + 2(N/2) = 3N which is O(N). If
only one half is short by 2 then you reduce the size of the problem by
half so keep S&S the shorter half til you find out what the two #s are.
The complexity is less than 3N which is O(N). So either way it's O(N).
...
3) If there are m missing then S&S the array with n/2 again. The result
is one half has i missing #s and the other j, i + j = m. If both i and j
are greater than 1 then you reduce the problem to the previously solved
type-i & type-j problems, which are both O(N) so the complexity is O(N).
If either i or j is zero then you reduce the size of the problem by half
so keep S&S till you either reduce it into smaller type-i problems or
find out all missing #s in one half. The complexity is O(m * N).
If m is O(lg N) then it's no longer efficient. In that case you might as
well sort the whole array to find out which ones are missing.

【在 c*********t 的大作中提到】

g*y2012-04-17 07:04

39 楼

如果把原数据序列改变了，算O(N) storage，还是算O(1)？

【在 N********n 的大作中提到】

:
: 1) If there is 1 missing then find it in O(N) using divide and conquer.
: method: use n/2 as pivot to swap & split the array. Find out which half
: is short by one. Re-swap and re-split the missing half til you find the
: missing # out. The complexity is N + n/2 + n/4 ... = 2N which is O(N).
: 2) If there are 2 missing then S&S the array with n/2. If both halves are
: short by one then you reduce the problem to two type-1 problems of half
: the size so the complexity is N + 2(N/2) + 2(N/2) = 3N which is O(N). If
: only one half is short by 2 then you reduce the size of the problem by
: half so keep S&S the shorter half til you find out what the two #s are.

G*A2012-04-17 07:04

40 楼

你是码工，别人是研究算法的，看问题的focus不一样,互相听不懂很正常...
讨论问题而已，范的着这么说话。

【在 t****t 的大作中提到】

: 不用在意gagama和paulpierce说什么, 你说的他们听不懂是很正常的.
:
: 比较

c*t2012-04-17 07:04

41 楼

Thanks.
In your answer to 3), what do you mean by "S&S"?
好像有人在jobhunting 很久以前提到过，把数字归位，就是说把数字放到在数组中应
该的位置，比如1->A[0], 2->A[1], ....然后看哪些位置的数字不对，就说明那个
index对应的数missing,不过好像是有m个数missing,有点tricky,能否忘这个方向想想？
谢谢！

【在 N********n 的大作中提到】

h*o2012-04-17 07:04

42 楼

actually lz and thrust are right. talking about number problems, if you
assume numbers are stored in binary form, the size is logN itself. This is
the nuance in complexity theory.

【在 G****A 的大作中提到】

: 你是码工，别人是研究算法的，看问题的focus不一样,互相听不懂很正常...
: 讨论问题而已，范的着这么说话。

g*s2012-04-17 07:04

43 楼

M个missing一样可以。这个方法做两遍就可以了。

Thanks.In your answer to 3), what do you mean by "S
★ Sent from iPhone App: iReader Mitbbs Lite 7.20

【在 c*********t 的大作中提到】

: Thanks.
: In your answer to 3), what do you mean by "S&S"?
: 好像有人在jobhunting 很久以前提到过，把数字归位，就是说把数字放到在数组中应
: 该的位置，比如1->A[0], 2->A[1], ....然后看哪些位置的数字不对，就说明那个
: index对应的数missing,不过好像是有m个数missing,有点tricky,能否忘这个方向想想？
: 谢谢！

N*n2012-04-17 07:04

44 楼

Hmmm that's a better strategy.
Input: A[n-m], B[m];
Init B to all flags;
for (i = 0; i < n - m; i++) {
t = a[i]; a[i] = flag;
while (t <= n-m && a[t] != flag) {
t1 = at[t]; a[t] = t; t = t1;
}
if (t > n-m)
{
B[t - n + m] = t;
a[i] = flag;
}
else
a[t] = t;
}
Scan through A and B. Flags indicate missing ones. Each element in the
for loop is accessed at most constant times so it's O(N).

【在 c*********t 的大作中提到】

P*e2012-04-17 07:04

45 楼

有什么reference说，the size of number is LogN itself?

【在 h****o 的大作中提到】

: actually lz and thrust are right. talking about number problems, if you
: assume numbers are stored in binary form, the size is logN itself. This is
: the nuance in complexity theory.

P*e2012-04-17 07:04

46 楼

我不同意你的说法是因为你abuse big O notation.

比较

【在 g*****y 的大作中提到】

t*t2012-04-17 07:04

47 楼

i am speechless.

【在 P********e 的大作中提到】

: 有什么reference说，the size of number is LogN itself?