Another M$ interview question

1. There are four people who need to cross a rickety bridge in 17 minutes. Because of its dilapidated condition, the bridge can only support up to 2 people at any given time. In addition, since it is pitch black out and there is only one lantern between the four people, anybody crossing the bridge must carry the lantern (or if two people are crossing the bridge at the same time, then one of them must be carrying the lantern). Someone must always bring the lantern back to the people who haven't crossed the bridge yet, so that when they cross, they don't fall through the holes in the bridge. You must take into account the additional time it will take for them to cross back. The four people can cross the bridge at the rate of 1, 2, 5, and 10 minutes, each way. There are no tricks: you can't carry anyone, or throw the lantern or drop it on the bridge, or swim across.

Solution:

最基本的概念的是“置换”。

假设that A用1 min B用2 mins C用5 mins D用10 mins，那么，三个步骤即可实现17分钟

1. A+B cross the bridge 2 mins and A returns 1 min; subtotal: 3 mins

2. C+D cross the bridge 10 mins and B returns 2 mins; subtotal: 12 mins

3. A+B cross the bridge 2 mins; total: 17 mins

2. A train leaves Los Angeles for New York at a constant speed of 15 miles an hour. At the same moment, a train leaves New York for Los Angeles on the same track at a constant speed of 20 miles an hour. At still the same moment, a bird leaves the Los Angeles train station and flies toward New York, following the track, at a speed of 25 miles per hour. When it reaches the train from New York, it instantly reverses direction. It travels at the same speed until it reaches the train from Los Angeles, where it reverses again, and so forth. The bird flies back and forth between the two trains until the very moment they collide. How far will the bird have traveled?

Solution

很容易就把鸟的飞行距离当成一个无限相加的算法来求，当然这样是不可能做出来的。最重要的是观察鸟一直匀速在飞，不管是超任何一个方向。而它会在两辆列车相撞的时候停止运动。所以一个求鸟飞行的距离最好的办法就是找到两辆列车相撞的时刻。假如从纽约到洛杉矶要3500英里，那么两车相撞的时间为3500/(15+20) = 100小时。这样再乘以25 m/h，就可以知道鸟一共飞行了2500英里。

The requirement is you should figure out each question in 5 mins. Think first and press Ctrl + A to reveal the solution.

我导师说他当年做了上万道这种智力题 ..... 我觉得，首先，题很难找，上万道... 又忽悠我吧；诶，其次，很多题类型都是相似的没有必要做那么多。Anyway,我承认他是个牛人（一个活生生的大野牛，而且越来越牛）。

想起来去年我胆子真是大，什么都没准备，大脑空空的就去参加摩根斯坦利的面试（更不用提准备服装了，ms我当时就穿拖鞋短裤去的吧...）。更重要的是，那么简单的问题都整得我面红耳赤，嗨。今年10月份可绝对不一样了！无比期待任何技术面试中！