又面了一上午，M家的，大家进来做题 - 未名空间MITBBS历史存档

又面了一上午，M家的，大家进来做题# JobHunting - 待字闺中

b*m2012-11-19 08:11

1 楼

只说一道吧（因为其它的有些简单，就不浪费大家时间了）：设计一个模块，包括类成
员和接口，不断receive一些package（从一个stream过来），每个package带一个
priority number，从1到100，1最低，100最高。有user从该模块不定时取package，要
求从priority number最高的package中取最先进来的一个发出去。要考虑时间和空间的
效率。

t*22012-11-19 08:11

2 楼

整100个queue?最直接了

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

: 只说一道吧（因为其它的有些简单，就不浪费大家时间了）：设计一个模块，包括类成
: 员和接口，不断receive一些package（从一个stream过来），每个package带一个
: priority number，从1到100，1最低，100最高。有user从该模块不定时取package，要
: 求从priority number最高的package中取最先进来的一个发出去。要考虑时间和空间的
: 效率。

b*e2012-11-19 08:11

3 楼

用100个list？
O(1)时间, O(n)空间：
list prio_lists[100];

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

: 只说一道吧（因为其它的有些简单，就不浪费大家时间了）：设计一个模块，包括类成
: 员和接口，不断receive一些package（从一个stream过来），每个package带一个
: priority number，从1到100，1最低，100最高。有user从该模块不定时取package，要
: 求从priority number最高的package中取最先进来的一个发出去。要考虑时间和空间的
: 效率。

x*s2012-11-19 08:11

4 楼

priority queue=>max heap

h*62012-11-19 08:11

5 楼

一个max heap应该可以了，比较时priority优先：(priority number, timestamp)

h*62012-11-19 08:11

6 楼

找第一个不为空的list时间不是O（1）吧？

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

: 用100个list？
: O(1)时间, O(n)空间：
: list prio_lists[100];

b*e2012-11-19 08:11

7 楼

总共100个list, 常数值是大了点，不过也算O(1).

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

: 找第一个不为空的list时间不是O（1）吧？

h*n2012-11-19 08:11

8 楼

agree

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

: 一个max heap应该可以了，比较时priority优先：(priority number, timestamp)

r*i2012-11-19 08:11

9 楼

Java:
class StreamPackage implements Comparable
{
int priority;
date receivedTime;
byte[] content;
public int compareTo()
{
//first sort by priority descending order, then received time
}
}
class PackageHandler
{
private PriorityBlockingQueue packages;

public PackageHandler()
{
packages=new PriorityBlockingQueue();
}
public void receivePackage(StreamPackage sp)
{
}
public void sendPackage()
{
StreamPackage sp= packages.poll();
if（null!=sp）
//send
}
}

d*i2012-11-19 08:11

10 楼

拿到OFFER了吗

h*n2012-11-19 08:11

11 楼

凑热闹写一个C++版本的
struct mycomparison
{
bool operator()(const Package * & p1, const Package * & p2) const
{
if(p1->getOrder() > p2->getOrder())
return true;
else if(p1->getOrder() < p2->getOrder())
return false;
else
{
return p1->getTimeStamp() < p2->getTimeStamp();
}
}
};
class PackageHandler
{
private:
priority_queue, mycomparison> pq;
Package* pac;
public:
void ReceivePac()
{
while(1)
{
pac = ReceivePacFromStream();
if(pac)
pq.push(pac);
}
}

Package* UserGetPackage()
{
if(!pq.empty())
{
pac = pq.top();
pq.pop();
return pac;
}
return NULL;
}
}
class Package
{
private:
int order;
double timestamp;
public:
Package(int o, double t)
{
order = o;
timestamp = t;
}
int getOrder()
{
return order;
}
double getTimeStamp()
{
return timeStamp;
}
}

b*m2012-11-19 08:11

12 楼

有人问起来其它的题，就说一道稍微不简单的吧（对于大牛们还是很简单）：Node这样
的structure，有next和down两个指针，给定一个head指针（就是说没有其它next和
down指向它），要求把这个类似二叉树的二维结构的数据组展平（flatten），最后成
为只有next指向的类似singly linked list的结构。

h*n2012-11-19 08:11

13 楼

这道题基本上和programming interview expose里面的题差不多
只不过里面的是要求flatten双向链表
我感觉双向链表更好做，占个位置，稍后上代码

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

: 有人问起来其它的题，就说一道稍微不简单的吧（对于大牛们还是很简单）：Node这样
: 的structure，有next和down两个指针，给定一个head指针（就是说没有其它next和
: down指向它），要求把这个类似二叉树的二维结构的数据组展平（flatten），最后成
: 为只有next指向的类似singly linked list的结构。

b*m2012-11-19 08:11

14 楼

双向链表、二叉树，意思都差不多。要求O(n)时间和O(1)空间。

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

: 这道题基本上和programming interview expose里面的题差不多
: 只不过里面的是要求flatten双向链表
: 我感觉双向链表更好做，占个位置，稍后上代码

h*n2012-11-19 08:11

15 楼

恩 O(n)时间 O（1）空间
typedef struct nodeT{
struct nodeT * next;
struct nodeT * down;
int value;
}node;
void FlattenSinglyList(node * head)
{
node*tail;
node* cur = head;
while(cur->next)
{
cur=cur->next;
}
tail = cur;
cur = head;
while(cur)
{
if(cur->down)
{
appendToTail(cur->down, tail);
}
}
}
void appendToTail(node* down, node* &tail)
{
node* cur = down;
tail->next = cur;
while(cur->next)
{
cur=cur->next;
}
tail = cur;
}

i*e2012-11-19 08:11

16 楼

讨论一下用两种数据结构实现的时间、空间复杂度：
1）priority_queue (max heap)
2) 100个元素的链表数组
- 使用1）和2）的getPackage() 的时间复杂度都是O(1)
- 对于receive()，使用priority_queue，插入是O(lgN), 使用链表数组如果维护一
个指向每个priority链表结尾的指针，插入是O(1)操作。
- 使用1）和2）空间复杂度都是O(N)
- 使用2）查找当前最高priority 链表也是O(1)操作。
所以2）比1）更有效？这样分析对吗？

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

: 只说一道吧（因为其它的有些简单，就不浪费大家时间了）：设计一个模块，包括类成
: 员和接口，不断receive一些package（从一个stream过来），每个package带一个
: priority number，从1到100，1最低，100最高。有user从该模块不定时取package，要
: 求从priority number最高的package中取最先进来的一个发出去。要考虑时间和空间的
: 效率。

h*n2012-11-19 08:11

17 楼

我的感觉吧，这两种方法效率都可以，但是两者各有侧重
时间上list array方法占优，特别是插入的时候
但是空间上占劣势，想想很多bucket你没用上的情况，如果所有的优先级都是同一种优
先级的话
那么你就白allocate了其他99个cell

b*m2012-11-19 08:11

18 楼

你这个程序貌似有点儿问题？

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

: 恩 O(n)时间 O（1）空间
: typedef struct nodeT{
: struct nodeT * next;
: struct nodeT * down;
: int value;
: }node;
: void FlattenSinglyList(node * head)
: {
: node*tail;
: node* cur = head;

p*22012-11-19 08:11

19 楼

二叉树按照inorder变成single linkedlist?

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

: 有人问起来其它的题，就说一道稍微不简单的吧（对于大牛们还是很简单）：Node这样
: 的structure，有next和down两个指针，给定一个head指针（就是说没有其它next和
: down指向它），要求把这个类似二叉树的二维结构的数据组展平（flatten），最后成
: 为只有next指向的类似singly linked list的结构。

h*n2012-11-19 08:11

20 楼

我画个图你就明白了
比如：
head---->node--->node----->node----->node----->NULL
| |
node--->node-->NULL node--->NULL
|
node->NULL
第一次append之后变成：
head---->node--->node----->node----->node--->node--->node---NULL
| |
node--->NULL node-->NULL
第二次append之后变成
head-->node-->node-->node-->node-->node-->node-->node--->NULL
|
node-->NULL
第三次append之后搞定
大概思路就是
遍历list，如果遇到有down指针的就把down指针指向的链表头append到当前list的tail
并更新tail
然后继续往前走，不断这么做，直到走到头

b*m2012-11-19 08:11

21 楼

思路是这样，我刚才可能看得有些眼花。

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

: 我画个图你就明白了
: 比如：
: head---->node--->node----->node----->node----->NULL
: | |
: node--->node-->NULL node--->NULL
: |
: node->NULL
: 第一次append之后变成：
: head---->node--->node----->node----->node--->node--->node---NULL
: | |

e*o2012-11-19 08:11

22 楼

leetcode的原题吧

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

: 有人问起来其它的题，就说一道稍微不简单的吧（对于大牛们还是很简单）：Node这样
: 的structure，有next和down两个指针，给定一个head指针（就是说没有其它next和
: down指向它），要求把这个类似二叉树的二维结构的数据组展平（flatten），最后成
: 为只有next指向的类似singly linked list的结构。

b*m2012-11-19 08:11

23 楼

LC上的题我做得不全。

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

: leetcode的原题吧

f*42012-11-19 08:11

24 楼

会不会重复append？
n0 - n1 - n2 - 0
| | |
0 n3 - n4 - 0
\__/ |
0

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

: 我画个图你就明白了
: 比如：
: head---->node--->node----->node----->node----->NULL
: | |
: node--->node-->NULL node--->NULL
: |
: node->NULL
: 第一次append之后变成：
: head---->node--->node----->node----->node--->node--->node---NULL
: | |

j*62012-11-19 08:11

25 楼

问下不用把down指针置为null吗？

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

: 恩 O(n)时间 O（1）空间
: typedef struct nodeT{
: struct nodeT * next;
: struct nodeT * down;
: int value;
: }node;
: void FlattenSinglyList(node * head)
: {
: node*tail;
: node* cur = head;

A*u2012-11-19 08:11

26 楼

这不是对fresh的问题吧..

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

: 只说一道吧（因为其它的有些简单，就不浪费大家时间了）：设计一个模块，包括类成
: 员和接口，不断receive一些package（从一个stream过来），每个package带一个
: priority number，从1到100，1最低，100最高。有user从该模块不定时取package，要
: 求从priority number最高的package中取最先进来的一个发出去。要考虑时间和空间的
: 效率。

b*m2012-11-19 08:11

27 楼

我不知道呀。

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

: 这不是对fresh的问题吧..

I*e2012-11-19 08:11

28 楼

大牛拿到Offer没？什么时候给通知？

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

: 我不知道呀。

b*m2012-11-19 08:11

29 楼

可能要感恩节后了吧。

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

: 大牛拿到Offer没？什么时候给通知？