f*********i
发帖数: 197 | 1 今天在redmond面试，一共见了6个人，5轮technical interview，一轮PM interview.
时间从早上8点到下午4点半。。。累死，没有签什么保密协议，所以一回来就发面经回
报版上，顺便求祝福。
第一轮： 老中，题目很简单，一个数组，有正有负，求最大连续和，这道题直接用经
典的O(n)就做出来了，然后问test cases。 多谢同胞，有了个好的开始。
第二轮：一个美国人，问两个string 是否是 anagram， 附加条件是abc ＝ a c b，
就是允许空格存在。也不难，三种方法，排序，hash table，还有质数相乘。质数相乘
是看版上牛人的答案，这个很快，而且不要extra space， impressive了他一下。
第三轮：老印，据说是这个组里最nice的老印，是90分钟的lunch interview，问了
string 中reverse word， 就是把how are you => you are how，reverse+reverse，
没有什么tricky的，写程序的时候有点麻烦，不过没有出错。
第四轮：老印，这个人是最tough的，一个人问了我三个问题，而且都超级难。
1. 游戏算法，给定一个N*N格的板块，往上面放不规则的element。
1.1， 如何表达这个板块，用什么数据结构来表达element，这个element有
可能是任何形状，like “—”，“X”，“Y”，“田”（参考俄罗斯方块）
1.2， 如何判断这个element可以放在某个cell里面，放在cell的条件是这个
element可以覆盖这个cell。（element之间不能重叠）。
1.3， 象俄罗斯方块一样，这个element可以rotate四个角度，问如何判断
rotate后可以放入。
很恶心吧，不过这个只是他给我的第一题，要我在20分钟内给出算法，并写出
pseudocode，我看看版上有没有人给出一个好的算法，我的那个实在是太耗时间了，就
不献丑了。
2. 用一个array来实现queue, 只给了5分钟
3. 这个是最恶心的，题目很简单，输入一个integer，12345，output是
5
4
3
2
1
这个不难，我是用java回答的
While(num>0){
System.out.println(num%10);
Num=num/10;
}
恶心的是，他问我num/10如果有小数点怎么办，我一下子楞住了，我说一个int 除以一
个int返回的一定是一个int，他硬要说如果返回是double怎么办，我一下子反应不过来
，因为平时没有考虑这个问题，而且如果没有自找麻烦在前面加double是不可能出现的
，所以有半分钟没有说话，然后他很不耐烦地告诉我是num ＝ （num－num%10）/10.
好吧算你狠，这个我确实没有想到。。。。。
第5轮，和PM聊天，聊了40分钟，没有技术问题，就是了解一下这个group做的东西，比
较放松。
第6轮，又出了妖蛾子了，本来约好的interviewer有事情来不了，临时加了一个老美，
人很nice，问了一个链表，1－>2->3->4->5, 每两个交换，2－>1->4->3->5,如果单数
情况返回最后一个。要求recursive和iterative两种方法，然后问哪个更好一点，一开
始写的时候犯了一个小错误，在提醒之后写出来了。这个要求是只能指针交换，不能交
换2 和1之间的数据，要通过链表的next来指向。
就是这样了，顺便说一句，ms campus好大啊，8点我在building 111，9点在building
XX，10点15在building YY，11点半在 building XX，2点在building XX， 下午又在
building YY，最后到building 111写回单，赶场了一天。
好希望可以拿到offer。。。。希望一切顺利。 |
c****t
发帖数: 19049 | |
H**d
发帖数: 152 | 3 Thanks for sharing .
Good luck! |
s**********v
发帖数: 1379 | 4 thanks for sharing, bless !
.
【在 f*********i 的大作中提到】
: 今天在redmond面试，一共见了6个人，5轮technical interview，一轮PM interview.
: 时间从早上8点到下午4点半。。。累死，没有签什么保密协议，所以一回来就发面经回
: 报版上，顺便求祝福。
: 第一轮： 老中，题目很简单，一个数组，有正有负，求最大连续和，这道题直接用经
: 典的O(n)就做出来了，然后问test cases。 多谢同胞，有了个好的开始。
: 第二轮：一个美国人，问两个string 是否是 anagram， 附加条件是abc ＝ a c b，
: 就是允许空格存在。也不难，三种方法，排序，hash table，还有质数相乘。质数相乘
: 是看版上牛人的答案，这个很快，而且不要extra space， impressive了他一下。
: 第三轮：老印，据说是这个组里最nice的老印，是90分钟的lunch interview，问了
: string 中reverse word， 就是把how are you => you are how，reverse+reverse，
|
j*****u
发帖数: 1133 | 5 最后一轮本来应该是boss的，看来boss有事结果又变成技术面了。
不过看起来你拿offer应该没问题。
.
【在 f*********i 的大作中提到】
: 今天在redmond面试，一共见了6个人，5轮technical interview，一轮PM interview.
: 时间从早上8点到下午4点半。。。累死，没有签什么保密协议，所以一回来就发面经回
: 报版上，顺便求祝福。
: 第一轮： 老中，题目很简单，一个数组，有正有负，求最大连续和，这道题直接用经
: 典的O(n)就做出来了，然后问test cases。 多谢同胞，有了个好的开始。
: 第二轮：一个美国人，问两个string 是否是 anagram， 附加条件是abc ＝ a c b，
: 就是允许空格存在。也不难，三种方法，排序，hash table，还有质数相乘。质数相乘
: 是看版上牛人的答案，这个很快，而且不要extra space， impressive了他一下。
: 第三轮：老印，据说是这个组里最nice的老印，是90分钟的lunch interview，问了
: string 中reverse word， 就是把how are you => you are how，reverse+reverse，
|
P***P
发帖数: 1387 | 6 恭喜恭喜, 你phone interview完多久给你消息呢? |
f*********i
发帖数: 197 | 7 phone interview 以后大概1个星期给onsite。
Project manage是第5轮面的，第6轮居然又是技术面。。。。难道最终boss在第7轮我
没有能够看到？ 我第6轮面好已经是下午4点半了。。。 |
g*********s
发帖数: 1782 | 8 what is the fast algorithm for prime multiplication?
.
【在 f*********i 的大作中提到】
: 今天在redmond面试，一共见了6个人，5轮technical interview，一轮PM interview.
: 时间从早上8点到下午4点半。。。累死，没有签什么保密协议，所以一回来就发面经回
: 报版上，顺便求祝福。
: 第一轮： 老中，题目很简单，一个数组，有正有负，求最大连续和，这道题直接用经
: 典的O(n)就做出来了，然后问test cases。 多谢同胞，有了个好的开始。
: 第二轮：一个美国人，问两个string 是否是 anagram， 附加条件是abc ＝ a c b，
: 就是允许空格存在。也不难，三种方法，排序，hash table，还有质数相乘。质数相乘
: 是看版上牛人的答案，这个很快，而且不要extra space， impressive了他一下。
: 第三轮：老印，据说是这个组里最nice的老印，是90分钟的lunch interview，问了
: string 中reverse word， 就是把how are you => you are how，reverse+reverse，
|
g*********s
发帖数: 1782 | 9 第四轮：老印，这个人是最tough的，一个人问了我三个问题，而且都超级难。
1. 游戏算法，给定一个N*N格的板块，往上面放不规则的element。
1.1， 如何表达这个板块，用什么数据结构来表达element，这个element有
可能是任何形状，like “—”，“X”，“Y”，“田”（参考俄罗斯方块）
1.2， 如何判断这个element可以放在某个cell里面，放在cell的条件是这个
element可以覆盖这个cell。（element之间不能重叠）。
1.3， 象俄罗斯方块一样，这个element可以rotate四个角度，问如何判断
rotate后可以放入。
what is "cell" in 1.2? putting one element in a cell sounds like the
cell covers the element, not verse vice.
.
reverse+reverse，
【在 f*********i 的大作中提到】
: 今天在redmond面试，一共见了6个人，5轮technical interview，一轮PM interview.
: 时间从早上8点到下午4点半。。。累死，没有签什么保密协议，所以一回来就发面经回
: 报版上，顺便求祝福。
: 第一轮： 老中，题目很简单，一个数组，有正有负，求最大连续和，这道题直接用经
: 典的O(n)就做出来了，然后问test cases。 多谢同胞，有了个好的开始。
: 第二轮：一个美国人，问两个string 是否是 anagram， 附加条件是abc ＝ a c b，
: 就是允许空格存在。也不难，三种方法，排序，hash table，还有质数相乘。质数相乘
: 是看版上牛人的答案，这个很快，而且不要extra space， impressive了他一下。
: 第三轮：老印，据说是这个组里最nice的老印，是90分钟的lunch interview，问了
: string 中reverse word， 就是把how are you => you are how，reverse+reverse，
|
f*********i
发帖数: 197 | 10 在第四轮中，一个cell就是一个格子啊，我的意思是，给一个n*n的格子，看看给定的
element能不能放在say 第x行y列的那个格子里（element的某个格子可以成功覆盖这个
cell）。
所以这里有两个格子的概念，一个是board的格子，n*n，一个是element的格子，在俄
罗斯方块中是4个，这里是任意个。
另外，因为给定的element可以是任何形状的，象俄罗斯方块一样（那样的情况一个
element需要4个格子，要有4个合适的格子来放这个element），同时，element可以旋
转，看看这个element的某个格子，能不能覆盖这个cell。
还是蛮难解释的，你可以体会我当时是多么的绝望了， |
|
|
n******n
发帖数: 215 | 11 感觉你应该没问题的。
.
【在 f*********i 的大作中提到】
: 今天在redmond面试，一共见了6个人，5轮technical interview，一轮PM interview.
: 时间从早上8点到下午4点半。。。累死，没有签什么保密协议，所以一回来就发面经回
: 报版上，顺便求祝福。
: 第一轮： 老中，题目很简单，一个数组，有正有负，求最大连续和，这道题直接用经
: 典的O(n)就做出来了，然后问test cases。 多谢同胞，有了个好的开始。
: 第二轮：一个美国人，问两个string 是否是 anagram， 附加条件是abc ＝ a c b，
: 就是允许空格存在。也不难，三种方法，排序，hash table，还有质数相乘。质数相乘
: 是看版上牛人的答案，这个很快，而且不要extra space， impressive了他一下。
: 第三轮：老印，据说是这个组里最nice的老印，是90分钟的lunch interview，问了
: string 中reverse word， 就是把how are you => you are how，reverse+reverse，
|
h*****w
发帖数: 220 | 12 bless
你一定能拿到offer的。
.
【在 f*********i 的大作中提到】
: 今天在redmond面试，一共见了6个人，5轮technical interview，一轮PM interview.
: 时间从早上8点到下午4点半。。。累死，没有签什么保密协议，所以一回来就发面经回
: 报版上，顺便求祝福。
: 第一轮： 老中，题目很简单，一个数组，有正有负，求最大连续和，这道题直接用经
: 典的O(n)就做出来了，然后问test cases。 多谢同胞，有了个好的开始。
: 第二轮：一个美国人，问两个string 是否是 anagram， 附加条件是abc ＝ a c b，
: 就是允许空格存在。也不难，三种方法，排序，hash table，还有质数相乘。质数相乘
: 是看版上牛人的答案，这个很快，而且不要extra space， impressive了他一下。
: 第三轮：老印，据说是这个组里最nice的老印，是90分钟的lunch interview，问了
: string 中reverse word， 就是把how are you => you are how，reverse+reverse，
|
b***u
发帖数: 22891 | |
c*********r
发帖数: 77 | 14 game: each block (as a pattern ) is mapping to a number...
pre-proceess the patterns, different pattern can match or did match.
cache this information. utilize the information to fill in the cell,
may be use DP to find the best match for big blocks |
s*******e
发帖数: 93 | 15 i guess the idea is to map each character to a unique prime number,
then get the product
say a=2, b=3, c=5, then abc=acb=cba=..=2*3*5
but in that way is it necessary to consider overflow and cost of introducing
large number multiplication?
since obviously this is talking about comparing very long strings
(otherwise why not sorting?)
and there are many possible characters
(otherwise why not hashtable?)
【在 g*********s 的大作中提到】
: what is the fast algorithm for prime multiplication?
:
: .
|
a******7
发帖数: 106 | 16 could anybody elaborate 质数相乘 for anagram? Need more detail. Thanks! |
f*********i
发帖数: 197 | 17 这个其实很好理解啦，因为质数相乘的结果是unique的，所以假设所有的字符个数是K
个，只要一一对应到头K个质数就可以了。不过要考虑overflow的问题，我当时是这样
回答的，当乘积太大的时候（超过longint的范围），就用字符来表示他们，比如111表
示为“111”，然后算字符串的乘积。
还有第四题，我当时回答是把board用一个2维N*N矩阵表示，如果一个cell已经占据了
，那么就是1，otherwise 0， 然后element也同样用2维M*N矩阵表示，根据形状赋值1
或者 0， 然后看能不能放入的方法是把element矩阵加到board矩阵里，如果有某个
cell的值超过1，那么就conflict。element的rotation可以表示为矩阵的rotation。但
是这样相加比较还是很复杂，因为要考虑M*N*4钟可能，也就是说，要考虑element的任
何一格覆盖这个cell的几率，并且4钟rotation都要考虑，他不是很满意。看看版上有
没有高人给我解惑了。
发信人: anson627 (anson), 信区: JobHunting
标 题: Re: MS onsite 归来，新鲜面经，巨长，顺便求祝福
发信站: BBS 未名空间站 (Sat Feb 19 11:15:42 2011, 美东)
could anybody elaborate 质数相乘 for anagram? Need more detail. Thanks! |
h****b
发帖数: 25 | 18 这个表现应该可以拿到Offer了， bless! zan详细的面经！ |
a******7
发帖数: 106 | 19 cool man! Thanks! I think you can definitely get an offer.
About the data structure for tetris game, my idea is to use a bitmap to
express each shape, and store 4 rotated shaped in circular double link
list, each time when rotate function is called, it either point to the
left and right elem, which is pre-computed bitmap.
The board is also a bitmap, say M*M, so as long as we have the position
of the shape on board, say the rightmost coordinates (x,y), and the size
of the shape bitmap N*N. For each certain position, it takes O(N^2) to
check whether the rotate operation is possible. That's my two cents.
K
1
【在 f*********i 的大作中提到】
: 这个其实很好理解啦，因为质数相乘的结果是unique的，所以假设所有的字符个数是K
: 个，只要一一对应到头K个质数就可以了。不过要考虑overflow的问题，我当时是这样
: 回答的，当乘积太大的时候（超过longint的范围），就用字符来表示他们，比如111表
: 示为“111”，然后算字符串的乘积。
: 还有第四题，我当时回答是把board用一个2维N*N矩阵表示，如果一个cell已经占据了
: ，那么就是1，otherwise 0， 然后element也同样用2维M*N矩阵表示，根据形状赋值1
: 或者 0， 然后看能不能放入的方法是把element矩阵加到board矩阵里，如果有某个
: cell的值超过1，那么就conflict。element的rotation可以表示为矩阵的rotation。但
: 是这样相加比较还是很复杂，因为要考虑M*N*4钟可能，也就是说，要考虑element的任
: 何一格覆盖这个cell的几率，并且4钟rotation都要考虑，他不是很满意。看看版上有
|
m****v
发帖数: 84 | 20 不要考虑大数相乘的复杂度？如果不用这个质数的方法来做，有没有其他比较好的解法
呢？
觉得方块那道题可以用KMP的方法来套，没有仔细想；但也可能是行不通的。
bless lz
K
1
【在 f*********i 的大作中提到】
: 这个其实很好理解啦，因为质数相乘的结果是unique的，所以假设所有的字符个数是K
: 个，只要一一对应到头K个质数就可以了。不过要考虑overflow的问题，我当时是这样
: 回答的，当乘积太大的时候（超过longint的范围），就用字符来表示他们，比如111表
: 示为“111”，然后算字符串的乘积。
: 还有第四题，我当时回答是把board用一个2维N*N矩阵表示，如果一个cell已经占据了
: ，那么就是1，otherwise 0， 然后element也同样用2维M*N矩阵表示，根据形状赋值1
: 或者 0， 然后看能不能放入的方法是把element矩阵加到board矩阵里，如果有某个
: cell的值超过1，那么就conflict。element的rotation可以表示为矩阵的rotation。但
: 是这样相加比较还是很复杂，因为要考虑M*N*4钟可能，也就是说，要考虑element的任
: 何一格覆盖这个cell的几率，并且4钟rotation都要考虑，他不是很满意。看看版上有
|
|
|
a******7
发帖数: 106 | 21 About 用一个array来实现queue, is it a priority queue with getMin() or a
normal queue with push(), pop(), top().
If it's a priority queue, we need implement a heap, with siftup(), siftdown
to maintain the property of heap
If it's a normal queue, we need implement a ring buffer, with the head and
tail pointer and number of elems in queue. |
a******7
发帖数: 106 | 22 Actually each shape bitmap can be interpreted as an integer A, and use the
same size mask (all ones) to get corresponding area of board bitmap, and
convert to another integer B, do (a&b)== 0 to check whether there is
collision, which takes O(1) time.
【在 a******7 的大作中提到】
: cool man! Thanks! I think you can definitely get an offer.
: About the data structure for tetris game, my idea is to use a bitmap to
: express each shape, and store 4 rotated shaped in circular double link
: list, each time when rotate function is called, it either point to the
: left and right elem, which is pre-computed bitmap.
: The board is also a bitmap, say M*M, so as long as we have the position
: of the shape on board, say the rightmost coordinates (x,y), and the size
: of the shape bitmap N*N. For each certain position, it takes O(N^2) to
: check whether the rotate operation is possible. That's my two cents.
:
|
m****v
发帖数: 84 | 23 Sounds great, classic method.
But, what if the "element"'s size is too large, and it can't be
represented by the bits in integer?
the
【在 a******7 的大作中提到】
: Actually each shape bitmap can be interpreted as an integer A, and use the
: same size mask (all ones) to get corresponding area of board bitmap, and
: convert to another integer B, do (a&b)== 0 to check whether there is
: collision, which takes O(1) time.
|
a******7
发帖数: 106 | 24 I think we only need check the bits on the boundary, which means the
leftmost, rightmost column and bottom row, normally these won't be large
than 32bits or 64bits.
【在 m****v 的大作中提到】
: Sounds great, classic method.
: But, what if the "element"'s size is too large, and it can't be
: represented by the bits in integer?
:
: the
|
f*********i
发帖数: 197 | 25 刚刚从西雅图回来，飞了整整一天，其实游戏那道题目，bitmap估计是最好的数据结构
了，和大家讨论的一致。
关键的问题是，如何判断是否可以放入board，我提出的方法是最naive的brute force
，就是单纯的比较，没有用DY，因为我当时实在想不起来了。看老印的意思，是可以用
DY来做的。 |
C***y
发帖数: 2546 | 26 DY是啥？
force
【在 f*********i 的大作中提到】
: 刚刚从西雅图回来，飞了整整一天，其实游戏那道题目，bitmap估计是最好的数据结构
: 了，和大家讨论的一致。
: 关键的问题是，如何判断是否可以放入board，我提出的方法是最naive的brute force
: ，就是单纯的比较，没有用DY，因为我当时实在想不起来了。看老印的意思，是可以用
: DY来做的。
|
f*********i
发帖数: 197 | 27 sorry,头昏了，是DP。
queue的那道题目就是implement enqueue 和 dequeue，不是priority queue。
tricky在判断异常，比如size＝0的时候dequeue抛异常和size full的时候抛提示，还
有头尾结点的指针位置变换，要考虑蛮多细节的 |
l***i
发帖数: 1309 | 28 How much space do you use if you use "111" to represent 111.
K
1
【在 f*********i 的大作中提到】
: 这个其实很好理解啦，因为质数相乘的结果是unique的，所以假设所有的字符个数是K
: 个，只要一一对应到头K个质数就可以了。不过要考虑overflow的问题，我当时是这样
: 回答的，当乘积太大的时候（超过longint的范围），就用字符来表示他们，比如111表
: 示为“111”，然后算字符串的乘积。
: 还有第四题，我当时回答是把board用一个2维N*N矩阵表示，如果一个cell已经占据了
: ，那么就是1，otherwise 0， 然后element也同样用2维M*N矩阵表示，根据形状赋值1
: 或者 0， 然后看能不能放入的方法是把element矩阵加到board矩阵里，如果有某个
: cell的值超过1，那么就conflict。element的rotation可以表示为矩阵的rotation。但
: 是这样相加比较还是很复杂，因为要考虑M*N*4钟可能，也就是说，要考虑element的任
: 何一格覆盖这个cell的几率，并且4钟rotation都要考虑，他不是很满意。看看版上有
|
a******e
发帖数: 95 | 29 use an array of integers then :)
【在 m****v 的大作中提到】
: Sounds great, classic method.
: But, what if the "element"'s size is too large, and it can't be
: represented by the bits in integer?
:
: the
|
n***5
发帖数: 86 | |
|
|
f*****w
发帖数: 2602 | 31 bless!!
有没有高手有全一点的对游戏那道题目的答案阿 我没很明白什么方法好一些 |
g*********s
发帖数: 1782 | 32 i don't see the benefits of this prime product method in terms of both
time and space.
【在 a******e 的大作中提到】
: use an array of integers then :)
|
q******8
发帖数: 848 | 33 能写一下比较具体的算法吗？大概明白了，不过你的意思是你还要每次计算下一个质数
是多少？
谢谢了好心人
你这个必须offer。bless！
K
1
【在 f*********i 的大作中提到】
: 这个其实很好理解啦，因为质数相乘的结果是unique的，所以假设所有的字符个数是K
: 个，只要一一对应到头K个质数就可以了。不过要考虑overflow的问题，我当时是这样
: 回答的，当乘积太大的时候（超过longint的范围），就用字符来表示他们，比如111表
: 示为“111”，然后算字符串的乘积。
: 还有第四题，我当时回答是把board用一个2维N*N矩阵表示，如果一个cell已经占据了
: ，那么就是1，otherwise 0， 然后element也同样用2维M*N矩阵表示，根据形状赋值1
: 或者 0， 然后看能不能放入的方法是把element矩阵加到board矩阵里，如果有某个
: cell的值超过1，那么就conflict。element的rotation可以表示为矩阵的rotation。但
: 是这样相加比较还是很复杂，因为要考虑M*N*4钟可能，也就是说，要考虑element的任
: 何一格覆盖这个cell的几率，并且4钟rotation都要考虑，他不是很满意。看看版上有
|
r******e
发帖数: 80 | 34 do not understand the meaning of the question 4. :-(. Thanks for sharing.
.
【在 f*********i 的大作中提到】
: 今天在redmond面试，一共见了6个人，5轮technical interview，一轮PM interview.
: 时间从早上8点到下午4点半。。。累死，没有签什么保密协议，所以一回来就发面经回
: 报版上，顺便求祝福。
: 第一轮： 老中，题目很简单，一个数组，有正有负，求最大连续和，这道题直接用经
: 典的O(n)就做出来了，然后问test cases。 多谢同胞，有了个好的开始。
: 第二轮：一个美国人，问两个string 是否是 anagram， 附加条件是abc ＝ a c b，
: 就是允许空格存在。也不难，三种方法，排序，hash table，还有质数相乘。质数相乘
: 是看版上牛人的答案，这个很快，而且不要extra space， impressive了他一下。
: 第三轮：老印，据说是这个组里最nice的老印，是90分钟的lunch interview，问了
: string 中reverse word， 就是把how are you => you are how，reverse+reverse，
|
c**********6
发帖数: 105 | |
n********p
发帖数: 708 | 36 bless~~~~~~~~~~~~~~~~~~~~~~ |
f*********i
发帖数: 197 | |
