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

g*d2011-01-28 08:01

1 楼

贡献一下我的面经吧，希望能有帮助。和大家碰到的题比，我的都很简单了，但是自己
水平真的太烂，一路下来，磕磕碰碰的。
电面是去年12月的，已经忘了什么题了，好像都是和data scaling/transformation有
关的，挺简单的，没有要我写code。所以没什么可说的了。
Onsite 1 上个礼拜二:
第一个：ABC mm，进来就直接往white board冲。让我写一个in order binary tree iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个很应该是feedback
最差的。
第二个：白人，很friendly。一半behavior，加两道题：test anagram和字典里找所有
anagrams，没要写code，就是在纸上描述一下步骤。这个感觉最好。
第三个：白人，hiring manager，很down to earth。问我怎么从一个机器传送一个很
大的文件到很多台很远的机器上。不太清楚他到底想问什么，所以这个问题来来去去交
流了很久。coding题是validate一个UTF-8格式的文件。中间给了我一些hint，然后写
完后指出了一个bug，我赶快插了一条code进去，就结束了。自己觉得还算顺利。本来
说好是recruiter带我去lunch的，hiring manager说还是他带我去吃吧，因为没给我时
间问问题。
第四个：南美裔，比较high的一个人。要求写一个production-quality stack class。
写完被指出很多问题，好像完全不够production-quality。。。。。然后告诉我该怎么
解决，该考虑什么，等等，还写sample code给我看，觉得像是老师在教学生。后来因
为时间不多了，他说就print一个fib series意思意思吧。也没讨论或检查。
午饭时，问了很多问题，HM回答的很认真。
两天后recruiter打电话竟然说feedback was positive，但是因为上次时间太短，还要
再加一轮面试。也不知道hiring committee 有没有meet过。
Onsite 2 这个礼拜二:
就一个三哥，没有前面几个friendly，但是还挺professional的。讨论了一道简单的
merge K-sorted arrays，每个array size 不一样。我给了brute force和merge的两种
解法，讨论了复杂度。他没提用heap，我也没想到。。。然后他让我自己选一种code。
知道自己水平烂，当然就选最保险的brute force了，没想到竟然还出状况。可能太紧
张了，写着写着中间脑子突然shutdown，导致逻辑混乱，有点写不下去，真是惭愧。。
。这里印度兄弟还不错，引导了我几步，也算勉强写下来了。然后指出几个问题，我都
赶快补救。完了他说，it works, but it’s a bit messy。我看着箭头满天飞的白板
，只能忙着擦汗了。
拿自己的面经和板上那些拿到offer的兄弟姐妹的面经比较下，感觉我根本就是在碰运
气。大家帮我分析一下，觉得我还有戏吗？还是就直接做好被拒的心理准备了？

g*s2011-01-28 08:01

2 楼

美女吗？
tree iterator干啥的？类似给定vector，写vector::iterator吗？

feedback

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

: 贡献一下我的面经吧，希望能有帮助。和大家碰到的题比，我的都很简单了，但是自己
: 水平真的太烂，一路下来，磕磕碰碰的。
: 电面是去年12月的，已经忘了什么题了，好像都是和data scaling/transformation有
: 关的，挺简单的，没有要我写code。所以没什么可说的了。
: Onsite 1 上个礼拜二:
: 第一个：ABC mm，进来就直接往white board冲。让我写一个in order binary tree iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个很应该是feedback
: 最差的。
: 第二个：白人，很friendly。一半behavior，加两道题：test anagram和字典里找所有
: anagrams，没要写code，就是在纸上描述一下步骤。这个感觉最好。
: 第三个：白人，hiring manager，很down to earth。问我怎么从一个机器传送一个很

g*d2011-01-28 08:01

3 楼

你这个美女是问谁，面试我的mm?
就是写constructor，hasNext()，getNext()等

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

: 美女吗？
: tree iterator干啥的？类似给定vector，写vector::iterator吗？
:
: feedback

g*s2011-01-28 08:01

4 楼

我是说你。听你的口气，好像女的对你一般，男的都不错。
你说的tree iterator是指向tree节点的smart pointer吗？没看懂那个问题。

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

: 你这个美女是问谁，面试我的mm?
: 就是写constructor，hasNext()，getNext()等

j*u2011-01-28 08:01

5 楼

iterator的用C#写就简单多了，不知道Java/C++有没有equivalent
任选一种traversal把print改成yield return就行了:P

feedback

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

: 贡献一下我的面经吧，希望能有帮助。和大家碰到的题比，我的都很简单了，但是自己
: 水平真的太烂，一路下来，磕磕碰碰的。
: 电面是去年12月的，已经忘了什么题了，好像都是和data scaling/transformation有
: 关的，挺简单的，没有要我写code。所以没什么可说的了。
: Onsite 1 上个礼拜二:
: 第一个：ABC mm，进来就直接往white board冲。让我写一个in order binary tree iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个很应该是feedback
: 最差的。
: 第二个：白人，很friendly。一半behavior，加两道题：test anagram和字典里找所有
: anagrams，没要写code，就是在纸上描述一下步骤。这个感觉最好。
: 第三个：白人，hiring manager，很down to earth。问我怎么从一个机器传送一个很

i*92011-01-28 08:01

6 楼

thanks for sharing and good luck!

j*u2011-01-28 08:01

7 楼

还真有：http://chaoticjava.com/posts/java-yield-return-code-published/

【在 j*****u 的大作中提到】

: iterator的用C#写就简单多了，不知道Java/C++有没有equivalent
: 任选一种traversal把print改成yield return就行了:P
:
: feedback

g*s2011-01-28 08:01

8 楼

到底啥iterator啊？

【在 j*****u 的大作中提到】

: iterator的用C#写就简单多了，不知道Java/C++有没有equivalent
: 任选一种traversal把print改成yield return就行了:P
:
: feedback

g*d2011-01-28 08:01

9 楼

我是男的
就是这个：
http://craicpropagation.blogspot.com/2009/10/binary-tree-iterat

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

: 我是说你。听你的口气，好像女的对你一般，男的都不错。
: 你说的tree iterator是指向tree节点的smart pointer吗？没看懂那个问题。

j*u2011-01-28 08:01

10 楼

Most simple (but not efficient) implementation:
static IEnumerable TreeIterator(TreeNode node)
{
yield return node;
foreach (var child in node.Children)
foreach (var n in TreeIterator(child))
yield return n;
}

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

: 到底啥iterator啊？

g*d2011-01-28 08:01

11 楼

这样应该不太能被接收吧。面试官可能主要是想看tree traverse logic

【在 j*****u 的大作中提到】

: Most simple (but not efficient) implementation:
: static IEnumerable TreeIterator(TreeNode node)
: {
: yield return node;
: foreach (var child in node.Children)
: foreach (var n in TreeIterator(child))
: yield return n;
: }

g*s2011-01-28 08:01

12 楼

i see. does she provide bt class to u, or u have to write it on ur own
first?

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

: 我是男的
: 就是这个：
: http://craicpropagation.blogspot.com/2009/10/binary-tree-iterat

g*d2011-01-28 08:01

13 楼

I just have to write the iterator class that takes bt as an input

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

: i see. does she provide bt class to u, or u have to write it on ur own
: first?

g*y2011-01-28 08:01

14 楼

it is not in order
it should be
static IEnumerable TreeIterator(TreeNode node)
{
if(node==null) yield break;
TreeNode[] temp = new TreeNode[3]{node.left, node, node.right};
foreach (var child in temp)
{
if(child != node)
{
foreach (var n in TreeIterator(child))
yield return n;
}
else
{
yield return node;
}
}
}

【在 j*****u 的大作中提到】

: Most simple (but not efficient) implementation:
: static IEnumerable TreeIterator(TreeNode node)
: {
: yield return node;
: foreach (var child in node.Children)
: foreach (var n in TreeIterator(child))
: yield return n;
: }

i*e2011-01-28 08:01

15 楼

其实那题 merge k sorted arrays 是再也经典不过的题。
还有，其实你选择用 brute force 来写反而更难，很多细节要处理，要一次写对比较
麻烦。
相反的，用 heap 来做就反而容易多了，而且解法更优。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的
hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便
吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个
很应该是feedback

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

: 贡献一下我的面经吧，希望能有帮助。和大家碰到的题比，我的都很简单了，但是自己
: 水平真的太烂，一路下来，磕磕碰碰的。
: 电面是去年12月的，已经忘了什么题了，好像都是和data scaling/transformation有
: 关的，挺简单的，没有要我写code。所以没什么可说的了。
: Onsite 1 上个礼拜二:
: 第一个：ABC mm，进来就直接往white board冲。让我写一个in order binary tree iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个很应该是feedback
: 最差的。
: 第二个：白人，很friendly。一半behavior，加两道题：test anagram和字典里找所有
: anagrams，没要写code，就是在纸上描述一下步骤。这个感觉最好。
: 第三个：白人，hiring manager，很down to earth。问我怎么从一个机器传送一个很

h*n2011-01-28 08:01

16 楼

UTF-8那题怎么弄？

iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的
hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便
吧。我最后把整个tree给

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

: 贡献一下我的面经吧，希望能有帮助。和大家碰到的题比，我的都很简单了，但是自己
: 水平真的太烂，一路下来，磕磕碰碰的。
: 电面是去年12月的，已经忘了什么题了，好像都是和data scaling/transformation有
: 关的，挺简单的，没有要我写code。所以没什么可说的了。
: Onsite 1 上个礼拜二:
: 第一个：ABC mm，进来就直接往white board冲。让我写一个in order binary tree iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个很应该是feedback
: 最差的。
: 第二个：白人，很friendly。一半behavior，加两道题：test anagram和字典里找所有
: anagrams，没要写code，就是在纸上描述一下步骤。这个感觉最好。
: 第三个：白人，hiring manager，很down to earth。问我怎么从一个机器传送一个很

l*a2011-01-28 08:01

17 楼

先顶后看

iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的
hint。后来觉
得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便吧。我最后把
整个tree给扒下
来放到了arraylist里，真的很dump的解法。。。。这个很应该是feedback

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

: 贡献一下我的面经吧，希望能有帮助。和大家碰到的题比，我的都很简单了，但是自己
: 水平真的太烂，一路下来，磕磕碰碰的。
: 电面是去年12月的，已经忘了什么题了，好像都是和data scaling/transformation有
: 关的，挺简单的，没有要我写code。所以没什么可说的了。
: Onsite 1 上个礼拜二:
: 第一个：ABC mm，进来就直接往white board冲。让我写一个in order binary tree iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个很应该是feedback
: 最差的。
: 第二个：白人，很friendly。一半behavior，加两道题：test anagram和字典里找所有
: anagrams，没要写code，就是在纸上描述一下步骤。这个感觉最好。
: 第三个：白人，hiring manager，很down to earth。问我怎么从一个机器传送一个很

h*d2011-01-28 08:01

18 楼

同问，楼主详细讲讲吧

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

: UTF-8那题怎么弄？
:
: iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的
: hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便
: 吧。我最后把整个tree给

s*y2011-01-28 08:01

19 楼

k-way merge, heap做 extractMin后，需要知道min来自于哪个数组，然后把那个数组
的下一个item再插入到heap。这一步怎么做比较好。难道是每个item都有个field记住
自己来自哪个数组？

g*d2011-01-28 08:01

20 楼

没错，特别在面试的时候，很容易昏头。
不知道是一道经典题，而且从来没用过heap，所以就没往那方面想，他也没提示。

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

: 其实那题 merge k sorted arrays 是再也经典不过的题。
: 还有，其实你选择用 brute force 来写反而更难，很多细节要处理，要一次写对比较
: 麻烦。
: 相反的，用 heap 来做就反而容易多了，而且解法更优。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的
: hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便
: 吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个

g*d2011-01-28 08:01

21 楼

UTF-8是variable length的字符encoding，是backward compatible with ASCII。
这里有很好的解释：
http://en.wikipedia.org/wiki/UTF-8
我刚开始也并不知道UTF-8是什么东西，他给我解释了半天。
要求就是查这个文件里没有invalid character sequence。

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

: 同问，楼主详细讲讲吧

g*d2011-01-28 08:01

22 楼

我觉得这个heap的node必须也记录来自哪个array吧，不然要去重新查的话，不是变成
brute force了嘛。

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

: k-way merge, heap做 extractMin后，需要知道min来自于哪个数组，然后把那个数组
: 的下一个item再插入到heap。这一步怎么做比较好。难道是每个item都有个field记住
: 自己来自哪个数组？

g*s2011-01-28 08:01

23 楼

vector, comp > my_heap
pair.first: the value; pair.second: the ownership.
bool comp(const pair& p1, const pair& p2) {
return p1.first < p2.first;
}

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

: 我觉得这个heap的node必须也记录来自哪个array吧，不然要去重新查的话，不是变成
: brute force了嘛。

A*H2011-01-28 08:01

24 楼

Use Regular Expression?

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

: UTF-8是variable length的字符encoding，是backward compatible with ASCII。
: 这里有很好的解释：
: http://en.wikipedia.org/wiki/UTF-8
: 我刚开始也并不知道UTF-8是什么东西，他给我解释了半天。
: 要求就是查这个文件里没有invalid character sequence。

d*e2011-01-28 08:01

25 楼

"coding题是validate一个UTF-8格式的文件"
请说说这道题具体是个什么要求？

iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的
hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便
吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个
很应该是feedback

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

: 贡献一下我的面经吧，希望能有帮助。和大家碰到的题比，我的都很简单了，但是自己
: 水平真的太烂，一路下来，磕磕碰碰的。
: 电面是去年12月的，已经忘了什么题了，好像都是和data scaling/transformation有
: 关的，挺简单的，没有要我写code。所以没什么可说的了。
: Onsite 1 上个礼拜二:
: 第一个：ABC mm，进来就直接往white board冲。让我写一个in order binary tree iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个很应该是feedback
: 最差的。
: 第二个：白人，很friendly。一半behavior，加两道题：test anagram和字典里找所有
: anagrams，没要写code，就是在纸上描述一下步骤。这个感觉最好。
: 第三个：白人，hiring manager，很down to earth。问我怎么从一个机器传送一个很

z*s2011-01-28 08:01

26 楼

楼主好运！

j*u2011-01-28 08:01

27 楼

先check BOM
然后每次read一个byte，可以确定当前的char有几个byte，然后读这些个byte并verify

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

: "coding题是validate一个UTF-8格式的文件"
: 请说说这道题具体是个什么要求？
:
: iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的
: hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便
: 吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个
: 很应该是feedback

y*e2011-01-28 08:01

28 楼

关于那个iterator的东西，若是用C#来yield return最是简单了。
using System;
using System.Collections.Generic;
public class InOrderTraverse
{
private BTree tree;
private Stack stack;
public InOrderTraverse(BTree tree) {
this.tree = tree;
this.stack = new Stack();
}
public IEnumerable GetEnumerator() {
BTree current = this.tree;

while (true) {
while (current != null) {
stack.Push(current);
current = current.Left;
}
if (stack.Count == 0)
yield break;
current = stack.Pop();
yield return current;

current = current.Right;
}
}
}
测试了下，还真能通过。
不过若是我做面官遇到这样的解法，肯定会让面试者解释yield是如何实现的。:P
所以还是逃不掉老实的记住状态，然后每被call一次然后返回当前的状态。这样写
就麻烦多了。
这个是我当初写的Java版本：
import java.util.*;
public class InOrderIterator
{
private BTree tree;
private BTree current;
private BTree next;
private boolean done;
private Stack stack;
public InOrderIterator(BTree tree) {
this.tree = tree;
this.stack = new Stack();
}
public void begin() {
this.stack.clear();
this.current = null;
this.next = this.tree;
this.done = false;
this.next();
}
public boolean end() {
return this.done;
}
public void next() {
this.current = this.next;
while (current != null) {
stack.push(current);
current = current.left;
}

if (!stack.isEmpty()) {
this.current = stack.pop();
this.next = current.right;
} else {
this.done = true;
}
}
public int current() {
return current.value;
}
public static void main(String[] args) {
BTree tree = BTree.createSample();
InOrderIterator it = new InOrderIterator(tree);
for (it.begin(); !it.end(); it.next()) {
System.out.println(it.current());
}
}
}

l*y2011-01-28 08:01

29 楼

请教以下， vector constructor 中可以定义comp 函数吗?
有什么document可以参考?

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

: vector, comp > my_heap
: pair.first: the value; pair.second: the ownership.
: bool comp(const pair& p1, const pair& p2) {
: return p1.first < p2.first;
: }

S*I2011-01-28 08:01

30 楼

of course not; if you want to make heap, what you should do is
vector > my_heap;
make_heap(my_heap.begin(), my_heap.end(), comp);
bool comp(const pair& p1, const pair& p2) {
return p1.first < p2.first;
}

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

: 请教以下， vector constructor 中可以定义comp 函数吗?
: 有什么document可以参考?

i*92011-01-28 08:01

31 楼

在java code里是不是有一行写反了?
begin()里头
应该是
current=tree;
next=null

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

: 关于那个iterator的东西，若是用C#来yield return最是简单了。
: using System;
: using System.Collections.Generic;
: public class InOrderTraverse
: {
: private BTree tree;
: private Stack stack;
: public InOrderTraverse(BTree tree) {
: this.tree = tree;
: this.stack = new Stack();

g*s2011-01-28 08:01

32 楼

c#很牛嘛。这个yield return是啥新概念？

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

: 关于那个iterator的东西，若是用C#来yield return最是简单了。
: using System;
: using System.Collections.Generic;
: public class InOrderTraverse
: {
: private BTree tree;
: private Stack stack;
: public InOrderTraverse(BTree tree) {
: this.tree = tree;
: this.stack = new Stack();

y*e2011-01-28 08:01

33 楼

呵, 我的代码写了有点confusing, 其实上没有写反.
我把代码修改下,还是一样的,不过容易懂多了:
public void begin() {
/*
this.stack.clear();
this.current = null;
this.next = this.tree;
this.done = false;
*/
this.reset(); // added
this.next();
}
private void reset() {
this.stack.clear();
this.current = null;
this.next = this.tree;
this.done = false;
}

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

: 在java code里是不是有一行写反了?
: begin()里头
: 应该是
: current=tree;
: next=null

g*u2011-01-28 08:01

34 楼

用stl的priority_queue写了下multi-way merge，请大家拍砖。
其中： myPair的第一个就是要存储的值，第二个表示ownership.
/*
*multiple way merge using the priority_heap
*/
#include "vector"
#include "queue"
class myPair{
friend std::ostream & operator<{
out<return out;
}
public:
myPair(int x, int y):_first(x),_second(y)
{
}
bool operator >(const myPair & p)const
{
return this->_first>p._first;
}
int first()const
{
return _first;
}
int second()const
{
return _second;
}
private:
int _first;
int _second;
};
void mergeMultiSorted(std::vector< std::vector > & sortedList, std:
element from the vector
{
int size=sortedList.size();
std::priority_queue, std::greater >
my_queue;
//build the heap
for(int i=0;i{
my_queue.push(*(sortedList.at(i).begin()));
sortedList.at(i).erase(sortedList.at(i).begin());
}
int index;
while(!my_queue.empty())
{
//here first pop out top element, and put into the result, then
insert into another element into the heap while not empty
myPair temp=my_queue.top();
my_queue.pop();
result.push_back(temp);
index=temp.second();

if(!sortedList.at(index).empty())
{
my_queue.push(*sortedList.at(index).begin());
sortedList.at(index).erase(sortedList.at(index).begin());
}
}
//now output the sorted data
std::cout<for(unsigned int i=0;istd::cout<}
void testMerge()
{
std::vector< std::vector > mySorted;
//to create the sorted list1
myPair pair1_1(23,0);
myPair pair1_2(32,0);
myPair pair1_3(33,0);
myPair pair1_4(34,0);

std::vector< myPair> list1;
list1.push_back(pair1_1);
list1.push_back(pair1_2);
list1.push_back(pair1_3);
list1.push_back(pair1_4);
//to create the sorted list 2
myPair pair2_1(2,1);
myPair pair2_2(4,1);
myPair pair2_3(45,1);
myPair pair2_4(48,1);

std::vector< myPair> list2;
list2.push_back(pair2_1);
list2.push_back(pair2_2);
list2.push_back(pair2_3);
list2.push_back(pair2_4);
//to make the sorted list 3
myPair pair3_1(-10,2);
myPair pair3_2(12,2);
myPair pair3_3(14,2);
myPair pair3_4(100,2);
myPair pair3_5(123,2);

std::vector< myPair> list3;
list3.push_back(pair3_1);
list3.push_back(pair3_2);
list3.push_back(pair3_3);
list3.push_back(pair3_4);
list3.push_back(pair3_5);
//end of preparing the sorted lists
mySorted.push_back(list1);
mySorted.push_back(list2);
mySorted.push_back(list3);
std::vector result;
mergeMultiSorted(mySorted,result);
}
测试的话，直接调用testMerge()即可，在visual studio 2008测试通过。

y*e2011-01-28 08:01

35 楼

这个yield return只是一个syntax sugar, 只能用于来写iterator.
尤其是这个面试题,要记住状态,满麻烦的.若是只是想,我就写一个inorder traversal,
那就容易多啦!yield return就是让开发者只需要按照traversal的思路写,然后在访问
每一个节点的时候,yield return下便是了!
比如,这个很简单的例子.给定一个array,来写一个iterator:
int[] intArray;
.......
for (int i = 0; i < intArray.Length; i++)
yield return intArray[i];
编译器会自动把如上的代码转换成,创建一个iterator,然后每执行current()一次,就从
array里面提取一个对象,如下:
class __intArrayEnumerator // C#里面把iterator叫Enumerator
{
private int[] __object;
private int __state;
public int Next {
if (__state < __object.Length)
return __object[__state++];
else
throw new InvalidStateException();
}
.....
}

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

: c#很牛嘛。这个yield return是啥新概念？

g*s2011-01-28 08:01

36 楼

why use priority_q? just use std::make_heap() on a vector.

&p)

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

: 用stl的priority_queue写了下multi-way merge，请大家拍砖。
: 其中： myPair的第一个就是要存储的值，第二个表示ownership.
: /*
: *multiple way merge using the priority_heap
: */
: #include "vector"
: #include "queue"
: class myPair{
: friend std::ostream & operator<: {

g*u2011-01-28 08:01

37 楼

could you please elaborate more?
I notice that the std::make_heap() offeres the functionality to create a
heap between vector.begin() and vector.begin()+index. But in this multi-
merge, how can we build the heap and dynamically update the elements in the
heap if we use the make_heap()...

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

: why use priority_q? just use std::make_heap() on a vector.
:
: &p)

g*s2011-01-28 08:01

38 楼

there are also std::push_heap() and std::pop_heap().

the

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

:
: could you please elaborate more?
: I notice that the std::make_heap() offeres the functionality to create a
: heap between vector.begin() and vector.begin()+index. But in this multi-
: merge, how can we build the heap and dynamically update the elements in the
: heap if we use the make_heap()...