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

l*y2010-12-14 08:12

1 楼

面的是business platform division 的SQL Server team。我简历上一个DB的keyword
都没有，我连DB的课都没上过，不
知道他们怎么选的。尽管这样，题目全是基本的算法和coding，没有考DB的任何问题。
可惜我还是表现很差，感觉脑子进
水了（或者是进seattle的雨了）。面试从12：30开始（本来说是10点，临时改了，说
是他们上午有会），见了4个人。3
个是印度人，还有一个不知道是什么国籍的。
我就把所有technical的题罗列下来吧。很多都是常见题。
给一个array of integers, 需要多少个comparison能找到min? how about min and
max? what's the best worst-
case? (3n/2)
怎么merge两个sorted的array，n 个呢？
给一个tree，把同层的nodes都连起来，assume每个node都有个指针，你要让它指向下
一个同层的node。
count 1's in an integer.
mergeSort, mergeSort without recursion, why nlogn?
Find whether one string is a subset of another string (not need to be
contiguous, but order should match).
Print the nodes on the exterior of a binary tree in a anti-clockwise order,
i.e., nodes on left edge, then leaf
nodes, then nodes on right edge.
Find two integers in an array that sum to a target integer.
题目给的都很明确，不需要怎么clarify。
才想起还没发thank you letter。interviewer的名字都不记得了，也没要contact，唉
。

x*32010-12-14 08:12

2 楼

题目都记得这么清楚，应该面的也不会差吧，bless

l*a2010-12-14 08:12

3 楼

how to implement Merge Sort without recursion

keyword

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

: 面的是business platform division 的SQL Server team。我简历上一个DB的keyword
: 都没有，我连DB的课都没上过，不
: 知道他们怎么选的。尽管这样，题目全是基本的算法和coding，没有考DB的任何问题。
: 可惜我还是表现很差，感觉脑子进
: 水了（或者是进seattle的雨了）。面试从12：30开始（本来说是10点，临时改了，说
: 是他们上午有会），见了4个人。3
: 个是印度人，还有一个不知道是什么国籍的。
: 我就把所有technical的题罗列下来吧。很多都是常见题。
: 给一个array of integers, 需要多少个comparison能找到min? how about min and
: max? what's the best worst-

s*t2010-12-14 08:12

4 楼

Bless 楼主！
第一个题 3n/2，咋来的？怎么都得 n-1吧
另外在一个string里找另外一个string，有什么好办法吗？

keyword

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

: 面的是business platform division 的SQL Server team。我简历上一个DB的keyword
: 都没有，我连DB的课都没上过，不
: 知道他们怎么选的。尽管这样，题目全是基本的算法和coding，没有考DB的任何问题。
: 可惜我还是表现很差，感觉脑子进
: 水了（或者是进seattle的雨了）。面试从12：30开始（本来说是10点，临时改了，说
: 是他们上午有会），见了4个人。3
: 个是印度人，还有一个不知道是什么国籍的。
: 我就把所有technical的题罗列下来吧。很多都是常见题。
: 给一个array of integers, 需要多少个comparison能找到min? how about min and
: max? what's the best worst-

k*n2010-12-14 08:12

5 楼

keyword
BFS的变体吧
Greedy就可以吧
,
最直接的，先打left edge，再ANY-order traversal加判断是否是leaf
最后打right edge
暂时想不出更好的办法，虽然Preorder能直接打出来前两部分，但是还要多带一个参数
编起程序来反而麻烦

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

: 面的是business platform division 的SQL Server team。我简历上一个DB的keyword
: 都没有，我连DB的课都没上过，不
: 知道他们怎么选的。尽管这样，题目全是基本的算法和coding，没有考DB的任何问题。
: 可惜我还是表现很差，感觉脑子进
: 水了（或者是进seattle的雨了）。面试从12：30开始（本来说是10点，临时改了，说
: 是他们上午有会），见了4个人。3
: 个是印度人，还有一个不知道是什么国籍的。
: 我就把所有technical的题罗列下来吧。很多都是常见题。
: 给一个array of integers, 需要多少个comparison能找到min? how about min and
: max? what's the best worst-

k*n2010-12-14 08:12

6 楼

第一题两两比较，可以每一对数少一次比较
找subset这个我不确定有没有比greedy更好的办法
不加预处理应该没有吧

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

: Bless 楼主！
: 第一个题 3n/2，咋来的？怎么都得 n-1吧
: 另外在一个string里找另外一个string，有什么好办法吗？
:
: keyword

y*a2010-12-14 08:12

7 楼

bless LZ！

keyword

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

: 面的是business platform division 的SQL Server team。我简历上一个DB的keyword
: 都没有，我连DB的课都没上过，不
: 知道他们怎么选的。尽管这样，题目全是基本的算法和coding，没有考DB的任何问题。
: 可惜我还是表现很差，感觉脑子进
: 水了（或者是进seattle的雨了）。面试从12：30开始（本来说是10点，临时改了，说
: 是他们上午有会），见了4个人。3
: 个是印度人，还有一个不知道是什么国籍的。
: 我就把所有technical的题罗列下来吧。很多都是常见题。
: 给一个array of integers, 需要多少个comparison能找到min? how about min and
: max? what's the best worst-

y*a2010-12-14 08:12

8 楼

LZ面的是SDE吗？完全没考oodesign和test的题？

keyword

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

: 面的是business platform division 的SQL Server team。我简历上一个DB的keyword
: 都没有，我连DB的课都没上过，不
: 知道他们怎么选的。尽管这样，题目全是基本的算法和coding，没有考DB的任何问题。
: 可惜我还是表现很差，感觉脑子进
: 水了（或者是进seattle的雨了）。面试从12：30开始（本来说是10点，临时改了，说
: 是他们上午有会），见了4个人。3
: 个是印度人，还有一个不知道是什么国籍的。
: 我就把所有technical的题罗列下来吧。很多都是常见题。
: 给一个array of integers, 需要多少个comparison能找到min? how about min and
: max? what's the best worst-

m*62010-12-14 08:12

9 楼

only four ppl...

d*a2010-12-14 08:12

10 楼

some of them might be easy to give out idea, but a little hard to write bug-
free code.
1 merge-sort without recursion
we should use loop to sovle it. we could use loop to get n/2 sorted
subarrays, then n/4 sorted arrays...I think we should be careful to consider
the boundary conditions.
2 Find whether one string is a subset of another string (not need to be
contiguous, but order should match).
use the idea of hash, > is a pair. e.g. "abcaeaf", "aaf"
a 0, 3, 5
b 1,
c 2,
e 4,
f 6
when we look up "aaf", use an index to keep track of the previous char's
position. when we look up one char, we could compare its position with index
. And we also need to remove(dequeue) elements from each queue.
3 Print the nodes on the exterior of a binary tree in a anti-clockwise order
,
i.e., nodes on left edge, then leaf
nodes, then nodes on right edge.
queue q;
struct node *curr = root;
while(root != NULL)
{
q.push_back(curr);
curr = curr->left;
}
use a inorder tree walk to enqueue leaf nodes to q.
struct node *curr = root;
while(root != NULL)
{
q.push_back(curr);
curr = curr->right;
}
then print.

X*n2010-12-14 08:12

11 楼

I guess he's talking about how to get both max and min with minimun
comparisons. By using tournament comparison, that is f(x)=f(x/2)+2, f(x)=3x/
2-2

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

: Bless 楼主！
: 第一个题 3n/2，咋来的？怎么都得 n-1吧
: 另外在一个string里找另外一个string，有什么好办法吗？
:
: keyword

J*a2010-12-14 08:12

12 楼

for min only you need n-1 comparison, no best no worst, always need n-1
for min and max, every comparison for min entitle one element to be in the
set of candidates for max.
maxset = set();
min = a[0];
for ai in a[1:]:
if ai < min :
min = ai
maxset.add(min);
maxset.delete(ai);
else:
maxset.add(ai);
maxset.delete(min);
find max in maxset.
Best case is sorted array (either desendent or asendent), maxset has only
one element left. Worst case, every two time a new element is added to
maxset and it has [n/2] elements. So worst case is about 3n/2

3x/

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

: I guess he's talking about how to get both max and min with minimun
: comparisons. By using tournament comparison, that is f(x)=f(x/2)+2, f(x)=3x/
: 2-2

l*a2010-12-14 08:12

13 楼

could u write the code for 1?
u want to handle it n/2.n/4,n/8
but for each step,u need to use the same logic
how to not use recursion

bug-
consider
"aaf"

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

: some of them might be easy to give out idea, but a little hard to write bug-
: free code.
: 1 merge-sort without recursion
: we should use loop to sovle it. we could use loop to get n/2 sorted
: subarrays, then n/4 sorted arrays...I think we should be careful to consider
: the boundary conditions.
: 2 Find whether one string is a subset of another string (not need to be
: contiguous, but order should match).
: use the idea of hash, > is a pair. e.g. "abcaeaf", "aaf"
: a 0, 3, 5

b*h2010-12-14 08:12

14 楼

你的代码有问题， if里面刚add进去就被delete了。

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

: for min only you need n-1 comparison, no best no worst, always need n-1
: for min and max, every comparison for min entitle one element to be in the
: set of candidates for max.
: maxset = set();
: min = a[0];
: for ai in a[1:]:
: if ai < min :
: min = ai
: maxset.add(min);
: maxset.delete(ai);

d*a2010-12-14 08:12

15 楼

http://www.algorithmist.com/index.php/Merge_sort
Bottom-up merge sort is a non-recursive variant of the merge sort, in which
the array is sorted by a sequence of passes. During each pass, the array is
divided into blocks of size . (Initially, ). Every two adjacent blocks are
merged (as in normal merge sort), and the next pass is made with a twice
larger value of .
In pseudo-code:
Input: array a[] indexed from 0 to n-1.
m = 1
while m <= n do
i = 0
while i < n-m do
merge subarrays a[i..i+m-1] and a[i+m .. min(i+2*m-1,n-1)] in-place.
i = i + 2 * m
m = m * 2

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

: could u write the code for 1?
: u want to handle it n/2.n/4,n/8
: but for each step,u need to use the same logic
: how to not use recursion
:
: bug-
: consider
: "aaf"

b*y2010-12-14 08:12

16 楼

I think f(x) = 2*f(x/2)+1; so it should be logn.

3x/

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

: I guess he's talking about how to get both max and min with minimun
: comparisons. By using tournament comparison, that is f(x)=f(x/2)+2, f(x)=3x/
: 2-2

d*a2010-12-14 08:12

17 楼

To get min and max with least comparisons.
If n is odd then initialize min and max as first element.
If n is even then initialize min and max as minimum and maximum of the first
two elements respectively.
For rest of the elements, pick them in pairs and compare(one time) to get
bigger and smaller value. use the bigger value to update max when possible(
second time comparison), use the samller value to update min when possible(
third time comparison).
In total, it should be close to n / 2 * 3.

b*h2010-12-14 08:12

18 楼

根据master theorem:
f(x) = 2*f(x/2) + 1 ---> f(x) = O(n)

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

: I think f(x) = 2*f(x/2)+1; so it should be logn.
:
: 3x/

d*j2010-12-14 08:12

19 楼

我就把所有technical的题罗列下来吧。很多都是常见题。
1. 给一个array of integers, 需要多少个comparison能找到min? how about min and
max? what's the best worst-case? (3n/2)
====>
n-1 comparison to find min
两两比较之后再在大的一堆中找大的，小的一堆中找小的
n/2 + n/2 - 1 + n/2 -1 = 3n/2.
记得MIT Algorithm (CLRS)上面有提到这个。
2. 怎么merge两个sorted的array，n 个呢？
====>
两个很容易，n个的话，用每个array的第一个元素构建一个heap，再heap sort，每挑
出一个值，再去对应的array中取一个值添到heap中。具体实现可能要修改数据结构。
3. 给一个tree，把同层的nodes都连起来，assume每个node都有个指针，你要让它指向
下一个同层的node。
====>
见 ihas1337code 的blog：
http://www.ihas1337code.com/2010/03/first-on-site-technical-interview.html
4.count 1's in an integer.
====>
Bit manipulation, n&(n-1) 会快一些，n&1 n>>1 循环需要32/64步
5.mergeSort, mergeSort without recursion, why nlogn?
====>
上面伪代码不错。
6.Find whether one string is a subset of another string (not need to be
contiguous, but order should match).
====>
用LCS的方法，最后返回的结果必须substring。O(NM)复杂度，不知道是不是最优
7. Print the nodes on the exterior of a binary tree in a anti-clockwise
order,i.e., nodes on left edge, then leaf
nodes, then nodes on right edge.
====>
ihas1337code:
http://www.ihas1337code.com/2010/10/print-edge-nodes-boundary-of-binary.html
8. Find two integers in an array that sum to a target integer.
====>
常见的吧，hash table or sorting and two pointers

keyword

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

: 面的是business platform division 的SQL Server team。我简历上一个DB的keyword
: 都没有，我连DB的课都没上过，不
: 知道他们怎么选的。尽管这样，题目全是基本的算法和coding，没有考DB的任何问题。
: 可惜我还是表现很差，感觉脑子进
: 水了（或者是进seattle的雨了）。面试从12：30开始（本来说是10点，临时改了，说
: 是他们上午有会），见了4个人。3
: 个是印度人，还有一个不知道是什么国籍的。
: 我就把所有technical的题罗列下来吧。很多都是常见题。
: 给一个array of integers, 需要多少个comparison能找到min? how about min and
: max? what's the best worst-

b*y2010-12-14 08:12

20 楼

thanks, and the formula itself is incorrect. 【在 bladesmith (taichi) 的大
作中提到: 】

b*e2010-12-14 08:12

21 楼

关于这道题大家想多了。就是一个直接的依次找下一个字符吧
int check(char *p, char *s){ // p: pattern, s: string, both non-NULL
if (*p=='\0') return 1; // is subset
while (*s) {
if ( *p==*s++) p++;
if (*p=='\0') return 1;
}
return 0; // not subset
}
6)
Find whether one string is a subset of another string (not need to be
contiguous, but order should match).

b*e2010-12-14 08:12

22 楼

更新：这个不对，有人指出了，新解在后面一贴
3. 给一个tree，把同层的nodes都连起来，assume每个node都有个指针，你要让它指向
下一个同层的node。
====>
见 ihas1337code 的blog：
http://www.ihas1337code.com/2010/03/first-on-site-technical-interview.html
这个和blog里说的有点不一样，因为是tree,(不是 binary tree).
假设tree有个root node, 每个node 用一个 list 来存 children,
要把每个node的 nextsibling link 设置起来：
Java 代码：
void addNextSibling(Node root) {
if (root == null ) return null;
Node prev = null;
foreach (Node n in root.children) {
n.nextsibling = prev;
addNextSibling(n);
prev = n;
}
}
其实是DFS.

l*y2010-12-14 08:12

23 楼

Yes, SDE. No design questions. For some of the problems I mentioned, they
did ask "how would you test it?"

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

: LZ面的是SDE吗？完全没考oodesign和test的题？
:
: keyword

g*s2010-12-14 08:12

24 楼

yes, the idea is correct. but what does "if (*p) return 1" mean?

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

: 关于这道题大家想多了。就是一个直接的依次找下一个字符吧
: int check(char *p, char *s){ // p: pattern, s: string, both non-NULL
: if (*p=='\0') return 1; // is subset
: while (*s) {
: if ( *p==*s++) p++;
: if (*p=='\0') return 1;
: }
: return 0; // not subset
: }
: 6)

g*s2010-12-14 08:12

25 楼

isn't binary tree a special case of general tree?
how come linking sibling could be dfs? bfs for sure.

interview.html

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

: 更新：这个不对，有人指出了，新解在后面一贴
: 3. 给一个tree，把同层的nodes都连起来，assume每个node都有个指针，你要让它指向
: 下一个同层的node。
: ====>
: 见 ihas1337code 的blog：
: http://www.ihas1337code.com/2010/03/first-on-site-technical-interview.html
: 这个和blog里说的有点不一样，因为是tree,(不是 binary tree).
: 假设tree有个root node, 每个node 用一个 list 来存 children,
: 要把每个node的 nextsibling link 设置起来：
: Java 代码：

F*p2010-12-14 08:12

26 楼

题目都记不得，那肯定fail了。过去2年了，我还记得题目的。

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

: 题目都记得这么清楚，应该面的也不会差吧，bless

l*y2010-12-14 08:12

27 楼

你的假设和面试官的假设一样。但是你的code是不是把不同层的也连起来了？
我用了个嵌套2层的loop，外层loop iterate上层连好的nodes，内层loop iterate每个
上层node的children。需要记录下
每层建好的list的头。思路应该就这样，可是写出code 漏洞百出。

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

: 更新：这个不对，有人指出了，新解在后面一贴
: 3. 给一个tree，把同层的nodes都连起来，assume每个node都有个指针，你要让它指向
: 下一个同层的node。
: ====>
: 见 ihas1337code 的blog：
: http://www.ihas1337code.com/2010/03/first-on-site-technical-interview.html
: 这个和blog里说的有点不一样，因为是tree,(不是 binary tree).
: 假设tree有个root node, 每个node 用一个 list 来存 children,
: 要把每个node的 nextsibling link 设置起来：
: Java 代码：

s*t2010-12-14 08:12

28 楼

你被问的题貌似都是熟题，但code起来有几个还真不易。

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

: 你的假设和面试官的假设一样。但是你的code是不是把不同层的也连起来了？
: 我用了个嵌套2层的loop，外层loop iterate上层连好的nodes，内层loop iterate每个
: 上层node的children。需要记录下
: 每层建好的list的头。思路应该就这样，可是写出code 漏洞百出。

s*t2010-12-14 08:12

29 楼

我也觉得他思路是对的，code有问题。

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

: yes, the idea is correct. but what does "if (*p) return 1" mean?

g*s2010-12-14 08:12

30 楼

use a queue to do bfs, plus two counters to record the nodes in the
current level and the next level.

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

: 你的假设和面试官的假设一样。但是你的code是不是把不同层的也连起来了？
: 我用了个嵌套2层的loop，外层loop iterate上层连好的nodes，内层loop iterate每个
: 上层node的children。需要记录下
: 每层建好的list的头。思路应该就这样，可是写出code 漏洞百出。

b*e2010-12-14 08:12

31 楼

真的，是DFS, 不过改了一下，用个array存下各层里最近出现的：
void setNextSibling(Node node, int level, Node[] leftNodes) {
if (node == null ) return;
if ( leftNodes[level] != null ) leftNodes[level].nextSibling=node;
leftNodes[level]=node;
foreach (Node n in node.children) {
setNextSibling(n,level+1, leftnodes);
}
}
用的时候，call:
setNextSibling(root,0,new Node[MAXDEPTH]);
(假设MAXDEPTH 已知，或者够大。不然用 ArrayList 也行）。

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

: isn't binary tree a special case of general tree?
: how come linking sibling could be dfs? bfs for sure.
:
: interview.html

b*e2010-12-14 08:12

32 楼

嗯，错了，应该是
if (*p=='\0') return 1;
原贴改了。

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

: yes, the idea is correct. but what does "if (*p) return 1" mean?

g*s2010-12-14 08:12

33 楼

so you maintain an array of lists to trace the sibling list in every
level?
this may work. but bfs is more natural and only takes O(1) extra space,
which is a big plus if the tree is very deep.

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

: 真的，是DFS, 不过改了一下，用个array存下各层里最近出现的：
: void setNextSibling(Node node, int level, Node[] leftNodes) {
: if (node == null ) return;
: if ( leftNodes[level] != null ) leftNodes[level].nextSibling=node;
: leftNodes[level]=node;
: foreach (Node n in node.children) {
: setNextSibling(n,level+1, leftnodes);
: }
: }
: 用的时候，call:

g*s2010-12-14 08:12

34 楼

yes, it's correct and concise. good job.

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

: 嗯，错了，应该是
: if (*p=='\0') return 1;
: 原贴改了。

P*l2010-12-14 08:12

35 楼

#3. The next field can be simply linked together in BFS traversal. We need a
queue for BFS, and this 'next' pointer is just for that purpose.


    void getBFSLink(BNode tree) {
        if (tree == null)
            return;
        BNode qHead = null, qTail = null;
        qHead = qTail = tree;
        while (qHead != null) {
            if (qHead.left != null) {
                qTail.next = qHead.left;
                qTail = qTail.next;
            }
            if (qHead.right != null) {
                qTail.next = qHead.right;
                qTail = qTail.next;
            }
            qHead = qHead.next;
        }
    }

j*u2010-12-14 08:12

36 楼

写了个非递归的
void SetSibling(TreeNode root)
{
if (root == null) throw ArgumentNullException("root");
Queue queue = new Queue();
TreeNode splitter = null; // indicates layer ends
queue.Enqueue(root); queue.Enqueue(splitter);
while (queue.Count > 1)
{
TreeNode node = queue.Dequeue();
foreach (TreeNode child in node.Children)
queue.Enqueue(child);
if (queue.Peek() != splitter)
node.Next = queue.Peek(); // set sibling
else
queue.Enqueue(queue.Dequeue()); //layer ends, move splitter from b
eginning to the end.
}
}

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

: 真的，是DFS, 不过改了一下，用个array存下各层里最近出现的：
: void setNextSibling(Node node, int level, Node[] leftNodes) {
: if (node == null ) return;
: if ( leftNodes[level] != null ) leftNodes[level].nextSibling=node;
: leftNodes[level]=node;
: foreach (Node n in node.children) {
: setNextSibling(n,level+1, leftnodes);
: }
: }
: 用的时候，call:

b*e2010-12-14 08:12

37 楼

不是，就是每层记录下访问到的最右边的节点（the rightmost node visited).
这样的话，递归的时候遇到同层的新节点时就联上link，再更新 the rightmost node.
所以我这个 array 总共需要 O(depth) space 就可以了。
BFS 的 memory 要求比 DFS 要高好多，所以不建议。

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

: so you maintain an array of lists to trace the sibling list in every
: level?
: this may work. but bfs is more natural and only takes O(1) extra space,
: which is a big plus if the tree is very deep.

w*m2010-12-14 08:12

38 楼

weiguan

w*m2010-12-14 08:12

39 楼

weiguan

P*l2010-12-14 08:12

40 楼

做了一下这几道题，看看对不对。
http://www.sureinterview.com/swsmg2/720002
点next, show answer.
或
http://www.sureinterview.com/swsmg2/720002/7/1

y*a2010-12-14 08:12

41 楼

困惑为什么bfs比dfs的memory要求高很多，
bfs要一个queue，最大O(V)吧，dfs呢，看起来不需要，不过那个recursive stack
需要多大呢？最常的path那么大？
babbage (tm) 的大作中提到: 】
node.