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

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

M家onsite面经

M家onsite面经# JobHunting - 待字闺中

P*y2013-03-30 07:03

1 楼

周四面的SDE, 面完就给口头offer了，没签啥保密协议，就分享一下面经。
运气比较好，五个人全是美国人
第一个人：1. two sum，很简单。 2. 一个人与人之间认识的关系网，单向的，就是我
认识你，你不一定认识我。每两个人之间至少有一种认识关系。如果一个人被别人认识
，但都不认识别人，叫做celebrity。问是否存在这样的celebrity，如果存在，可否存
在多于一个的celebrity。然后问怎么去represent这样的关系
第二个人：1. rotated数组找最小值，经典题。2.一堆六边形连成一片，每个六边形上
有字母B代表base或者数字代表资源数。需要解决的问题是为每个base分配资源，使得
每个base都可以分配的10个资源。每个base只能得到相邻的资源，如果取得某个资源后
，可以再去找这个资源相邻的资源。让设计API接口来解决这个问题。属于OOD的题
第三个人：1. 判断两个null结束的字符串是否anagram。里面有除字母外的其他字符，
但要skip这些字符。写完后让优化空间到最小。这个很喜欢问优化的问题。2. null结
束的字符串把空格替换成“%20”，in place。有告诉你字符串的memory大小，先判断
能否这样替换，如果能再进行替换。还问了判断是否为空格进行处理的条件if,else对
调的话对性能有啥影响。主要从architecture角度考虑。
第四个人：1. 先序中序恢复二叉树。这个比较狡猾。说完题目我讲思路的时候就问我
是否做过，我老实交待。然后就换题了。2. 双向链表swap pair。leetcode上的是单向
链接。这个双向有更多的指针，比较容易搞错。这就题被找到了两个bug。其他之前的
题都bug free.
第五个人：应该是manager。先问了research的项目和一些behavior的问题。之前前面
的人也都有问一些behavior的问题。然后做了一个关于DAG的BFS。
整体都不难，就是经常从每道题还扩展一些问题，有时候刚开始不知道他们想要啥答案
，好几个人都是在经过提示下最后说出了他们想要的，然后就很满意了。

G*A2013-03-30 07:03

2 楼

好人品。这几道真心简单啊

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

: 周四面的SDE, 面完就给口头offer了，没签啥保密协议，就分享一下面经。
: 运气比较好，五个人全是美国人
: 第一个人：1. two sum，很简单。 2. 一个人与人之间认识的关系网，单向的，就是我
: 认识你，你不一定认识我。每两个人之间至少有一种认识关系。如果一个人被别人认识
: ，但都不认识别人，叫做celebrity。问是否存在这样的celebrity，如果存在，可否存
: 在多于一个的celebrity。然后问怎么去represent这样的关系
: 第二个人：1. rotated数组找最小值，经典题。2.一堆六边形连成一片，每个六边形上
: 有字母B代表base或者数字代表资源数。需要解决的问题是为每个base分配资源，使得
: 每个base都可以分配的10个资源。每个base只能得到相邻的资源，如果取得某个资源后
: ，可以再去找这个资源相邻的资源。让设计API接口来解决这个问题。属于OOD的题

j*22013-03-30 07:03

3 楼

这俩题咋搞？大家说说？
2. 一个人与人之间认识的关系网，单向的，就是我
2.一堆六边形连成一片，每个六边形上

g*c2013-03-30 07:03

4 楼

这两个题目本身就不清楚

l*r2013-03-30 07:03

5 楼

cong

k*22013-03-30 07:03

6 楼

觉得还是要准备得很好才行啊。。。
敢问lz面的什么组？

A*u2013-03-30 07:03

7 楼

。2.一堆六边形连成一片，每个六边形上
有字母B代表base或者数字代表资源数。需要解决的问题是为每个base分配资源，使得
每个base都可以分配的10个资源。每个base只能得到相邻的资源，如果取得某个资源后
，可以再去找这个资源相邻的资源。让设计API接口来解决这个问题。属于OOD的题
这题啥意思
不用算法，只要接口？
像一个graph
class Polygon
{
public:
addEdge(int a, int b); // a,b node 相邻
void optimize() // 优化
private:
int numNode;
vector< vector >;
}
太简单啦, 一直不会这种ood

j*y2013-03-30 07:03

8 楼

每个六边形最多只有六个neighbor, 感觉要用到 dfs, 不是很好弄阿

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

: 。2.一堆六边形连成一片，每个六边形上
: 有字母B代表base或者数字代表资源数。需要解决的问题是为每个base分配资源，使得
: 每个base都可以分配的10个资源。每个base只能得到相邻的资源，如果取得某个资源后
: ，可以再去找这个资源相邻的资源。让设计API接口来解决这个问题。属于OOD的题
: 这题啥意思
: 不用算法，只要接口？
: 像一个graph
: class Polygon
: {
: public:

A*u2013-03-30 07:03

9 楼

graphs + dfs
不是很标准吗？
不过我理解，这里不需要写代码只写接口？

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

: 每个六边形最多只有六个neighbor, 感觉要用到 dfs, 不是很好弄阿

j*y2013-03-30 07:03

10 楼

这里的两个 B 能获得共同的资源吗？如何获得资源没有排斥的话，还是比较easy

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

: graphs + dfs
: 不是很标准吗？
: 不过我理解，这里不需要写代码只写接口？

A*u2013-03-30 07:03

11 楼

肯定会排斥
算法不好写，所以我一直问，到底要不要写代码
还是写个接口就行了?

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

: 这里的两个 B 能获得共同的资源吗？如何获得资源没有排斥的话，还是比较easy

P*y2013-03-30 07:03

12 楼

会排斥
没写算法，说了下思路
他主要想考继承
六边形里有不同东西，要用继承和多态

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

: 肯定会排斥
: 算法不好写，所以我一直问，到底要不要写代码
: 还是写个接口就行了?

A*u2013-03-30 07:03

13 楼

这为啥要继承
六边形里 -1 是base
0,1,2... 是资源数目

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

: 会排斥
: 没写算法，说了下思路
: 他主要想考继承
: 六边形里有不同东西，要用继承和多态

B*t2013-03-30 07:03

14 楼

正在学OOD, 大家看看有什么问题：
class Polygon
{
public:
char type;
virtual bool requestResource();
virtual bool acceptRequest(int num);
virtual ~Polygon();
};
class Resource : public Polygon
{
pthread_mutex_t lock;
int numOfResources;
Polygon *neighbour;
public:
Resource();
bool acceptRequest(int num)
{
//lock
//if no resource, unlock, return false
//otherwise, assign, unlock, return true
}
Polygon *nextNeighbour();
};
class Base : public Polygon
{
Polygon *neighbour;
public:
bool requestResource()
{
//DFS to get resources
//return true if abtain 10 resources
//return false otherwise
}
Polygon *nextNeighbour();
};

P*y2013-03-30 07:03

15 楼

base 要求用字母表示

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

: 这为啥要继承
: 六边形里 -1 是base
: 0,1,2... 是资源数目

k*e2013-03-30 07:03

16 楼

原来是这样，这个算法是不是NP hard啊

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

: 会排斥
: 没写算法，说了下思路
: 他主要想考继承
: 六边形里有不同东西，要用继承和多态

c*r2013-03-30 07:03

17 楼

第一个人第二题是不是意思就是让球linkedlist是否有环来实现？

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

P*y2013-03-30 07:03

18 楼

不是
就是leetcode那道单向链接改成双向，有prev指针，swap pair

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

: 第一个人第二题是不是意思就是让球linkedlist是否有环来实现？

j*22013-03-30 07:03

19 楼

graph+bfs也可以吧？

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

: graphs + dfs
: 不是很标准吗？
: 不过我理解，这里不需要写代码只写接口？

c*r2013-03-30 07:03

20 楼

cool, make scene. 那个前序中序恢复BST是不是这个 Construct Binary Tree from
Preorder and Inorder Traversal？

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

: 不是
: 就是leetcode那道单向链接改成双向，有prev指针，swap pair

P*y2013-03-30 07:03

21 楼

嗯，就那题，后来不让写，说没意思了

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

: cool, make scene. 那个前序中序恢复BST是不是这个 Construct Binary Tree from
: Preorder and Inorder Traversal？

c*r2013-03-30 07:03

22 楼

M现在问题还问的挺新。。
那个六边形的是这个意思不？
public class Unit implements IUnit{
private final int MAX_NEIGHBOR = 6;
private final int MAX_RESOURCE = 10;
private int nNeighbor = 0;
private int nResource = 0;
Unit[] neighbors;
Unit[] resources;
public Unit(){
neighbors = new Unit[MAX_NEIGHBOR];
resources = new Unit[MAX_RESOURCE];
}
@Override
public boolean findRecource(){
if(neighbors == null || nNeighbor == MAX_NEIGHBOR){
return false;
}
boolean added = false;
for(Unit u: neighbors）{
if(nNeighbor <= MAX_NEIGHBOR){
res[nNeighbors-1] = u;
added = true;
}else{
break;
}
}
return added;
}
// other override methods ..
}
//Interface
public interface IUnit{
public boolean findResource();
public boolean deleteResource();
public addNeighbor（ Unit u);
public addResource( Unit u);
// as so on.....
}

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

: 嗯，就那题，后来不让写，说没意思了

s*y2013-03-30 07:03

23 楼

Cong!LZ面的哪个组？

l*a2013-03-30 07:03

24 楼

没那么复杂
a know b then a is not celebrity
b know a then b is not
u can skip one each time,so u can get the result with O(n) and at most
1 celebrity

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

: 第一个人第二题是不是意思就是让球linkedlist是否有环来实现？

c*r2013-03-30 07:03

25 楼

This is a cool answer, thanks man,
and I did some research on it and it seems that this answer is preferred by
most of the people

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

: 没那么复杂
: a know b then a is not celebrity
: b know a then b is not
: u can skip one each time,so u can get the result with O(n) and at most
: 1 celebrity

x*02013-03-30 07:03

26 楼

mark

t*h2013-03-30 07:03

27 楼

celebrity需要被所有人认识吗

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

: 没那么复杂
: a know b then a is not celebrity
: b know a then b is not
: u can skip one each time,so u can get the result with O(n) and at most
: 1 celebrity

G*A2013-03-30 07:03

28 楼

难道我理解错了？
原题说“每两个人之间至少有一种认识关系”，就是说 for each node pair (A, b),
either A knows B, or B knows A. 那怎么可能有1个以上的celebrity?

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

: 没那么复杂
: a know b then a is not celebrity
: b know a then b is not
: u can skip one each time,so u can get the result with O(n) and at most
: 1 celebrity

l*a2013-03-30 07:03

29 楼

I used "at most"

),

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

: 难道我理解错了？
: 原题说“每两个人之间至少有一种认识关系”，就是说 for each node pair (A, b),
: either A knows B, or B knows A. 那怎么可能有1个以上的celebrity?