P*******y
发帖数: 168 | 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****A
发帖数: 4160 | 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******2
发帖数: 362 | 3 这俩题咋搞？大家说说？
2. 一个人与人之间认识的关系网，单向的，就是我
2.一堆六边形连成一片，每个六边形上 |
g**c
发帖数: 2339 | |
l***r
发帖数: 241 | |
k*******2
发帖数: 84 | 6 觉得还是要准备得很好才行啊。。。
敢问lz面的什么组？ |
A**u
发帖数: 2458 | 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*****y
发帖数: 1071 | 8 每个六边形最多只有六个neighbor, 感觉要用到 dfs, 不是很好弄阿
【在 A**u 的大作中提到】
: 。2.一堆六边形连成一片，每个六边形上
: 有字母B代表base或者数字代表资源数。需要解决的问题是为每个base分配资源，使得
: 每个base都可以分配的10个资源。每个base只能得到相邻的资源，如果取得某个资源后
: ，可以再去找这个资源相邻的资源。让设计API接口来解决这个问题。属于OOD的题
: 这题啥意思
: 不用算法，只要接口？
: 像一个graph
: class Polygon
: {
: public:
|
A**u
发帖数: 2458 | 9 graphs + dfs
不是很标准吗？
不过我理解，这里不需要写代码 只写接口？
【在 j*****y 的大作中提到】
: 每个六边形最多只有六个neighbor, 感觉要用到 dfs, 不是很好弄阿
|
j*****y
发帖数: 1071 | 10 这里的两个 B 能获得共同的资源吗？ 如何获得资源没有排斥的话，还是比较easy
【在 A**u 的大作中提到】
: graphs + dfs
: 不是很标准吗？
: 不过我理解，这里不需要写代码 只写接口？
|
|
|
A**u
发帖数: 2458 | 11 肯定会排斥
算法不好写，所以我一直问，到底要不要写代码
还是写个接口就行了?
【在 j*****y 的大作中提到】
: 这里的两个 B 能获得共同的资源吗？ 如何获得资源没有排斥的话，还是比较easy
|
P*******y
发帖数: 168 | 12 会排斥
没写算法，说了下思路
他主要想考继承
六边形里有不同东西，要用继承和多态
【在 A**u 的大作中提到】
: 肯定会排斥
: 算法不好写，所以我一直问，到底要不要写代码
: 还是写个接口就行了?
|
A**u
发帖数: 2458 | 13 这为啥要继承
六边形里 -1 是base
0,1,2... 是资源数目
【在 P*******y 的大作中提到】
: 会排斥
: 没写算法，说了下思路
: 他主要想考继承
: 六边形里有不同东西，要用继承和多态
|
B********t
发帖数: 147 | 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*******y
发帖数: 168 | 15 base 要求用字母表示
【在 A**u 的大作中提到】
: 这为啥要继承
: 六边形里 -1 是base
: 0,1,2... 是资源数目
|
k****e
发帖数: 116 | 16 原来是这样，这个算法是不是NP hard啊
【在 P*******y 的大作中提到】
: 会排斥
: 没写算法，说了下思路
: 他主要想考继承
: 六边形里有不同东西，要用继承和多态
|
c********r
发帖数: 286 | 17 第一个人第二题是不是意思就是让球linkedlist是否有环来实现？
【在 P*******y 的大作中提到】
: 周四面的SDE, 面完就给口头offer了，没签啥保密协议，就分享一下面经。
: 运气比较好，五个人全是美国人
: 第一个人：1. two sum，很简单。 2. 一个人与人之间认识的关系网，单向的，就是我
: 认识你，你不一定认识我。每两个人之间至少有一种认识关系。如果一个人被别人认识
: ，但都不认识别人，叫做celebrity。问是否存在这样的celebrity，如果存在，可否存
: 在多于一个的celebrity。然后问怎么去represent这样的关系
: 第二个人：1. rotated数组找最小值，经典题。2.一堆六边形连成一片，每个六边形上
: 有字母B代表base或者数字代表资源数。需要解决的问题是为每个base分配资源，使得
: 每个base都可以分配的10个资源。每个base只能得到相邻的资源，如果取得某个资源后
: ，可以再去找这个资源相邻的资源。让设计API接口来解决这个问题。属于OOD的题
|
P*******y
发帖数: 168 | 18 不是
就是leetcode那道单向链接改成双向，有prev指针，swap pair
【在 c********r 的大作中提到】
: 第一个人第二题是不是意思就是让球linkedlist是否有环来实现？
|
j******2
发帖数: 362 | 19 graph+bfs也可以吧？
【在 A**u 的大作中提到】
: graphs + dfs
: 不是很标准吗？
: 不过我理解，这里不需要写代码 只写接口？
|
c********r
发帖数: 286 | 20 cool, make scene. 那个前序中序恢复BST是不是这个 Construct Binary Tree from
Preorder and Inorder Traversal？
【在 P*******y 的大作中提到】
: 不是
: 就是leetcode那道单向链接改成双向，有prev指针，swap pair
|
|
|
P*******y
发帖数: 168 | 21 嗯，就那题，后来不让写，说没意思了
【在 c********r 的大作中提到】
: cool, make scene. 那个前序中序恢复BST是不是这个 Construct Binary Tree from
: Preorder and Inorder Traversal？
|
c********r
发帖数: 286 | 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***y
发帖数: 203 | |
l*****a
发帖数: 14598 | 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********r
发帖数: 286 | 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*****0
发帖数: 452 | |
t*********h
发帖数: 941 | 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****A
发帖数: 4160 | 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*****a
发帖数: 14598 | 29 I used "at most"
),
【在 G****A 的大作中提到】
: 难道我理解错了？
: 原题说“每两个人之间至少有一种认识关系”， 就是说 for each node pair (A, b),
: either A knows B, or B knows A. 那怎么可能有1个以上的celebrity?
|
