MS Onsite面经 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

MS Onsite面经

MS Onsite面经# JobHunting - 待字闺中

w*t2011-03-25 07:03

1 楼

summer intern
4个人
第一个：一副牌，52张，如何测试一个洗牌算法是否好
如何设计一个电梯
第二个：逆时针打印一个m*n的矩阵
第三个：A!+B!+C! = ABC, A,B,C都是0-9的数，ABC是这三个digit组成的三位数，问A
B C分别是几，如果A! + B! + C! + D! = ABCD，那么如何迅速找ABCD
第四个（boss）：一个有序序列，从某个地方rotate，求在rotate的位置，比如
1 3 5 0 0 0，那么rotate的位置是4，他后来只用了4行就写出来了，很nb，被bs了~~

g*e2011-03-25 07:03

2 楼

5!+4!+1!+=145
四个数的话就在1-7之间选4个，而且一定有7，有5，所以一共有C(2,5)=10种，穷举一下

A

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

: summer intern
: 4个人
: 第一个：一副牌，52张，如何测试一个洗牌算法是否好
: 如何设计一个电梯
: 第二个：逆时针打印一个m*n的矩阵
: 第三个：A!+B!+C! = ABC, A,B,C都是0-9的数，ABC是这三个digit组成的三位数，问A
: B C分别是几，如果A! + B! + C! + D! = ABCD，那么如何迅速找ABCD
: 第四个（boss）：一个有序序列，从某个地方rotate，求在rotate的位置，比如
: 1 3 5 0 0 0，那么rotate的位置是4，他后来只用了4行就写出来了，很nb，被bs了~~

v*y2011-03-25 07:03

3 楼

第四个是O(log(n)) 的解法么？四行，牛，求解

g*e2011-03-25 07:03

4 楼

没说ABCD不能相同，实际上ABCD如果不同，是无解的，要再想想

一下

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

: 5!+4!+1!+=145
: 四个数的话就在1-7之间选4个，而且一定有7，有5，所以一共有C(2,5)=10种，穷举一下
:
: A

k*72011-03-25 07:03

5 楼

1 3 5 0 0 0，为啥rotate的位置是4不是3？
如果1,2,3,4,0,0，那rotate位置按轮转之前还是之后的？
Anyway，用for循环，a[i+1]<=a[i]就return，4行刚好，O(n)时间

D*72011-03-25 07:03

6 楼

FindRotation(int* array, int start, int end)
{
int middle = (start + end)/2;
if (array[start] <= array[end])
return start;
return (array[start] > array[midlle]) ? FindRotation(array, start,
middle) : FindRotation(array, middle, end);
}
假设是升序排列，大概是这样，没有测试过。

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

: 第四个是O(log(n)) 的解法么？四行，牛，求解

g*e2011-03-25 07:03

7 楼

有重复的你这就不灵了

g*e2011-03-25 07:03

8 楼

我觉得A!+B!+C!+D!=ABCD这个没有解啊，穷举了一遍也没有

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

: 没说ABCD不能相同，实际上ABCD如果不同，是无解的，要再想想
:
: 一下

g*e2011-03-25 07:03

9 楼

试试 0 0 0 0 1 0？
你这是O(n)了。我发现这个问题有重复数字的时候写对相当困难

c*m2011-03-25 07:03

10 楼

四个人每人就一道题？

r*e2011-03-25 07:03

11 楼

试了，没问题
不是O(n)，最后两行的条件是不会同时发生的，最后一个if clause可以去掉

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

: 试试 0 0 0 0 1 0？
: 你这是O(n)了。我发现这个问题有重复数字的时候写对相当困难

g*e2011-03-25 07:03

12 楼

我给的这个例子不就是a[mid]==a[low]==a[high]么

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

: 试了，没问题
: 不是O(n)，最后两行的条件是不会同时发生的，最后一个if clause可以去掉

a*y2011-03-25 07:03

13 楼

hi, how can you get 5!+4！+1！ = 145？ is there any theorem can explain
this or other things?

一下

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

: 5!+4!+1!+=145
: 四个数的话就在1-7之间选4个，而且一定有7，有5，所以一共有C(2,5)=10种，穷举一下
:
: A

r*e2011-03-25 07:03

14 楼

恩，是有问题
不过你给的test case在我刚那段代码下结果碰巧是对的
0 1 0 0 0 0才会出问题，这样的情况有点麻烦

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

: 我给的这个例子不就是a[mid]==a[low]==a[high]么

d*l2011-03-25 07:03

15 楼

careercup的那本书上好像有这题，上面提到如果有重复的话，O(n)是必须的，就拿全
零然后只有一个1的情况来说，1在不同位置都是有可能的，除非把所有位置都看一遍否
则是无法确定的

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

: 恩，是有问题
: 不过你给的test case在我刚那段代码下结果碰巧是对的
: 0 1 0 0 0 0才会出问题，这样的情况有点麻烦

g*e2011-03-25 07:03

16 楼

A!+B!+C!=ABC
考虑5!=120, 6!=720，首先不可能有6，不然720里面的7无法实现，所以只可能0-5。
另外一定有5，不然4!x3也不到100. 确定了一个就好办了，另外一定有1，因为最高位
是1.剩下的就是4了

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

: hi, how can you get 5!+4！+1！ = 145？ is there any theorem can explain
: this or other things?
:
: 一下

C*Y2011-03-25 07:03

17 楼

careercup上那道题是在rotated后的array中search某个数
大量duplicate的话就是O(n)的

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

: careercup的那本书上好像有这题，上面提到如果有重复的话，O(n)是必须的，就拿全
: 零然后只有一个1的情况来说，1在不同位置都是有可能的，除非把所有位置都看一遍否
: 则是无法确定的

d*l2011-03-25 07:03

18 楼

我也编程试了下没解。。。亏我还在纸上试了半天，不知这题是怎么个意思

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

: 我觉得A!+B!+C!+D!=ABCD这个没有解啊，穷举了一遍也没有

i*92011-03-25 07:03

19 楼

This question is a bit different with the one on careercup, careercup 上那道
题是search a key,跟这个（只要求找出去拐点,）不一样, so it is doable in O(
lgn) for repeats

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

c*y2011-03-25 07:03

20 楼

Binary search works for an array with duplicate elements.
However, a modified binary search doesn't work for a rotated array with
duplicate elements (see Careercup book p181).
So how should we deal with a rotated array without duplicate elements?
Trying to use the modified binary search is good, but it is hard to remember
. We can first locate the special location, and then use the ordinary binary
search in the "right" range.

B*M2011-03-25 07:03

21 楼

你咋那么聪明哪！

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

: 我给的这个例子不就是a[mid]==a[low]==a[high]么

B*M2011-03-25 07:03

22 楼

这个rotate是什么意思？没懂

A

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

a*y2011-03-25 07:03

23 楼

thanks, gate, good explanation.

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

: A!+B!+C!=ABC
: 考虑5!=120, 6!=720，首先不可能有6，不然720里面的7无法实现，所以只可能0-5。
: 另外一定有5，不然4!x3也不到100. 确定了一个就好办了，另外一定有1，因为最高位
: 是1.剩下的就是4了