Bloomberg FSD Intern 面经 - 未名空间MITBBS历史存档

Bloomberg FSD Intern 面经# JobHunting - 待字闺中

d*82013-04-05 07:04

1 楼

phone interview.
问的问题是说你是tenant，你必须每天付给landlord一刀。付钱的方式是通过支票，但
是只有1刀，2刀，5刀，7刀，9刀，11刀这六种选择。请问到第31天，你使用最少量支
票的数量。
这一天一开始理解成，支付第31天所用支票的最少数量。但是其实支票如果开了就不能
再拆开组合成别的数目了。也就是说要求的解除了cover31，还有cover以前的1到30。
那么这一题其实就是问，找到最小的set，其子集和能够cover从1到31的所有数。
可惜当时没反应过来。讲了半个小时，对方也不懂自己在说什么。还以为对方水平不照
，后来发现理解错了。还没有当下反应出是子集和问题。。。

x*i2013-04-05 07:04

2 楼

啥时候面的？我都面了1个月了。知道这个多少钱一个小时不？

【在 d*******8 的大作中提到】

: phone interview.
: 问的问题是说你是tenant，你必须每天付给landlord一刀。付钱的方式是通过支票，但
: 是只有1刀，2刀，5刀，7刀，9刀，11刀这六种选择。请问到第31天，你使用最少量支
: 票的数量。
: 这一天一开始理解成，支付第31天所用支票的最少数量。但是其实支票如果开了就不能
: 再拆开组合成别的数目了。也就是说要求的解除了cover31，还有cover以前的1到30。
: 那么这一题其实就是问，找到最小的set，其子集和能够cover从1到31的所有数。
: 可惜当时没反应过来。讲了半个小时，对方也不懂自己在说什么。还以为对方水平不照
: ，后来发现理解错了。还没有当下反应出是子集和问题。。。

d*82013-04-05 07:04

3 楼

今天刚面的，不知道多少钱。。。

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

: 啥时候面的？我都面了1个月了。知道这个多少钱一个小时不？

u*82013-04-05 07:04

4 楼

我怎么连题目都没懂

f*42013-04-05 07:04

5 楼

我也没懂。。我感觉所有的智力题最困难的其实就是搞懂题意。。。

r*92013-04-05 07:04

6 楼

2张1刀，2张2刀，1张5刀，1张9刀，1张11刀
需要写程序求通解吗？ad hoc的思路比较好想，写程序的话感觉比较难。

【在 d*******8 的大作中提到】

: phone interview.
: 问的问题是说你是tenant，你必须每天付给landlord一刀。付钱的方式是通过支票，但
: 是只有1刀，2刀，5刀，7刀，9刀，11刀这六种选择。请问到第31天，你使用最少量支
: 票的数量。
: 这一天一开始理解成，支付第31天所用支票的最少数量。但是其实支票如果开了就不能
: 再拆开组合成别的数目了。也就是说要求的解除了cover31，还有cover以前的1到30。
: 那么这一题其实就是问，找到最小的set，其子集和能够cover从1到31的所有数。
: 可惜当时没反应过来。讲了半个小时，对方也不懂自己在说什么。还以为对方水平不照
: ，后来发现理解错了。还没有当下反应出是子集和问题。。。

C*62013-04-05 07:04

7 楼

难道不是 11+11+9 = 31？

【在 d*******8 的大作中提到】

: phone interview.
: 问的问题是说你是tenant，你必须每天付给landlord一刀。付钱的方式是通过支票，但
: 是只有1刀，2刀，5刀，7刀，9刀，11刀这六种选择。请问到第31天，你使用最少量支
: 票的数量。
: 这一天一开始理解成，支付第31天所用支票的最少数量。但是其实支票如果开了就不能
: 再拆开组合成别的数目了。也就是说要求的解除了cover31，还有cover以前的1到30。
: 那么这一题其实就是问，找到最小的set，其子集和能够cover从1到31的所有数。
: 可惜当时没反应过来。讲了半个小时，对方也不懂自己在说什么。还以为对方水平不照
: ，后来发现理解错了。还没有当下反应出是子集和问题。。。

r*n2013-04-05 07:04

8 楼

所以说这个题有歧义，
11表明允许提前支付余下10天的数，能够 11+11+9　也一定可3个11，只不过到第３１
天的时候，我还多支付了余下２天的，但是支票数还是３张支票
如此理解，这个题目也就太简单了

【在 C*6 的大作中提到】

: 难道不是 11+11+9 = 31？

d*82013-04-05 07:04

9 楼

他的意思是讲不能提起支付。不过你可以给张大的，让他找小的。不过他能找的只有你
给他的那些数量。

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

: 所以说这个题有歧义，
: 11表明允许提前支付余下10天的数，能够 11+11+9　也一定可3个11，只不过到第３１
: 天的时候，我还多支付了余下２天的，但是支票数还是３张支票
: 如此理解，这个题目也就太简单了

d*82013-04-05 07:04

10 楼

这个应该是（没有verify）
他让我说算法来着，按他最后的解法，感觉写程序也不容易

【在 r********9 的大作中提到】

: 2张1刀，2张2刀，1张5刀，1张9刀，1张11刀
: 需要写程序求通解吗？ad hoc的思路比较好想，写程序的话感觉比较难。

r*92013-04-05 07:04

11 楼

这个是老题型阿，这么多人都没有见过吗？我再解释下。
日期支票
1 1 $1
2 2 $1
3 1 $2,1 $1 (要回1张$1，给一张$2)
4 2 $2 (要回一张$1，再给一张$2，下同）
5 1 $5
6 1 $5, 1 $1
7 1 $5, 2 $1
...
10 1 $5, 1 $1, 2 $2
11 1 $11
...
31 1 $11, 1$9, 1$5, 2$2, 2$1
总之，我一开始写了7张支票（2张1刀，2张2刀，1张5刀，1张9刀，1张11刀），然后31
天每天都组合出若干支票付款，一个月都不需要再写新支票了。

【在 r********9 的大作中提到】

: 2张1刀，2张2刀，1张5刀，1张9刀，1张11刀
: 需要写程序求通解吗？ad hoc的思路比较好想，写程序的话感觉比较难。

H*92013-04-05 07:04

12 楼

没读懂题目呢

【在 d*******8 的大作中提到】

: phone interview.
: 问的问题是说你是tenant，你必须每天付给landlord一刀。付钱的方式是通过支票，但
: 是只有1刀，2刀，5刀，7刀，9刀，11刀这六种选择。请问到第31天，你使用最少量支
: 票的数量。
: 这一天一开始理解成，支付第31天所用支票的最少数量。但是其实支票如果开了就不能
: 再拆开组合成别的数目了。也就是说要求的解除了cover31，还有cover以前的1到30。
: 那么这一题其实就是问，找到最小的set，其子集和能够cover从1到31的所有数。
: 可惜当时没反应过来。讲了半个小时，对方也不懂自己在说什么。还以为对方水平不照
: ，后来发现理解错了。还没有当下反应出是子集和问题。。。

a*y2013-04-05 07:04

13 楼

为什么答案不是[1张1刀，2张2刀，1张5刀，2张11刀]呢？
1张1刀，2张2刀，1张5刀可以凑出1-10的所有值，加一张11刀后，可以凑出1-21的所
有值，再加一个11刀，可以凑出1-32的所有值，包含31。
既然允许找钱，那最后一天的时候我手上剩一张1刀也应该满足要求吧。

【在 r********9 的大作中提到】

: 这个是老题型阿，这么多人都没有见过吗？我再解释下。
: 日期支票
: 1 1 $1
: 2 2 $1
: 3 1 $2,1 $1 (要回1张$1，给一张$2)
: 4 2 $2 (要回一张$1，再给一张$2，下同）
: 5 1 $5
: 6 1 $5, 1 $1
: 7 1 $5, 2 $1
: ...

d*82013-04-05 07:04

14 楼

我觉得有道理。这个６张更少

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

: 为什么答案不是[1张1刀，2张2刀，1张5刀，2张11刀]呢？
: 1张1刀，2张2刀，1张5刀可以凑出1-10的所有值，加一张11刀后，可以凑出1-21的所
: 有值，再加一个11刀，可以凑出1-32的所有值，包含31。
: 既然允许找钱，那最后一天的时候我手上剩一张1刀也应该满足要求吧。

r*92013-04-05 07:04

15 楼

你是对的
point是，怎么写程序

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

: 为什么答案不是[1张1刀，2张2刀，1张5刀，2张11刀]呢？
: 1张1刀，2张2刀，1张5刀可以凑出1-10的所有值，加一张11刀后，可以凑出1-21的所
: 有值，再加一个11刀，可以凑出1-32的所有值，包含31。
: 既然允许找钱，那最后一天的时候我手上剩一张1刀也应该满足要求吧。

A*w2013-04-05 07:04

16 楼

感觉这个可以试试用贪心算法

a*y2013-04-05 07:04

17 楼

我自己在纸上推是用的贪心. 你说是经典题,有答案吗? 谢谢.

【在 r********9 的大作中提到】

: 你是对的
: point是，怎么写程序

r*92013-04-05 07:04

18 楼

我也不知道标准解法，感觉应该是贪心法吧

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

: 我自己在纸上推是用的贪心. 你说是经典题,有答案吗? 谢谢.