由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - FB onsite面经加求bless
相关主题
● 谁能贴一下求nth permutation 和已知permutation 求rank的code● 我这个 4sum的解法是 o^3还是o^2? , xiexie
● 问道看到的面试题● 问个老问题 Longest palindrome in a string
● 请问我写的这个代码哪可以改进一下● Google Intern
● google phone interview question● 请教一道google的数组遍历题
● 问个array in place operation的题目● LC的题确实变难了。。。
● F家 一道LIS 的变种● google interview question
● 请教一题● 问个题
● MS a0, a1, ..., b0, b1... 问题● How to convert string to string array (or vector) (转载)
相关话题的讨论汇总
话题: string话题: vector话题: john话题: int话题: input
进入JobHunting版参与讨论
1 (共1页)
l********7
发帖数: 40
1
前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
一轮电面之后之后让去onsite
onsite是3轮面试，2轮coding加一轮的experience
coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
string大
第二题是有这么一个class Contact，里面有一个String的name，和一个List
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [j**[email protected]]
#2 Mary [m**[email protected]]
#3 John [j**[email protected]]
#4 John [j**[email protected], j**[email protected], j**[email protected]]
#5 Bob [b*[email protected]]
现在我们知道如果email address相同的话，那么就说明是同一个人，现在要做的是根
据这些email address，把同一个contact给group起来，生成一个List>
，比如我们就可以知道#1，#3，#4是同一个人。注意不能根据名字来group，因为有可
能有相同名字的人，或者同一个人有可能有不同的名字来注册之类的。我给出了一个类
似graph的解法。时间不够，就没有写code，只是把逻辑解释了一遍。
第二个人也是出了两道题目，第一题是给两个string，判断其中一个string能否对其中
的一个字符通过一次的insertion或者一次deletion或者一次replacement变成另外一个
string，比如
cat cast True #第一个string通过一次insertion可以变成第二个string
cat at True #deletion
cat cot True #replacement
cat dog False
cat cat False #因为这两个string相同，不需要任何的操作，要返回false
第二题是找出factorial(n)中有多少个0，我跟他说我做过
第三个人大部分时间都是问的experience，问为什么Facebook，对Facebook的哪个
feature最喜欢，为什么喜欢，然后这个feature还有什么不足。之后让给他一个非常
specific的例子说当你和同事出现技术上的冲突的时候，应该怎么解决，问的特别细，
特别深入。之后让写一道题，是leetcode上的，linux里面的cd命令那题，就是给定你
当前的系统路径比如/a/b，然后你要cd到另外一个目录，给你cd的输入比如cd ../pq/.
/r，那么最后的路径应该就是/a/pq/r，要求输出最后这个路径
facebook总体都不难，我觉得最多是leetcode中等难度的题，但是我也听说不同的人的
难度会差别很大。做的时候前两个人还比较顺，但是最后一个人我都没有怎么用过太多
的facebook，也就在那里瞎扯，写code的时候还被指出了一个非常低级的bug，听说F对
bugfree的要求特别高，所以求bless啊求bless啊
A*********c
发帖数: 430
2
这面经，太给力了，必须给力bless

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
c********e
发帖数: 186
3
Strong bless!!!!
y*****3
发帖数: 451
4
我感觉这些题不容易啊，bless!

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
w*****t
发帖数: 485
5
赞分享！
bless！
X*4
发帖数: 101
6
多谢分享
contact
string (delete, insert, replace)
都不会
lol

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
d**********x
发帖数: 4083
7
some people think they know a nlogn method
but they are wrong. of course including some... interviewers.

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
r*****t
发帖数: 68
8
Bless!!
v***n
发帖数: 562
9
BLESS!
w*******o
发帖数: 2
10
特地上来bless一下楼主~ 拿到fb请bg
相关主题
● F家 一道LIS 的变种● 我这个 4sum的解法是 o^3还是o^2? , xiexie
● 请教一题● 问个老问题 Longest palindrome in a string
● MS a0, a1, ..., b0, b1... 问题● Google Intern
进入JobHunting版参与讨论
c********p
发帖数: 1969
11
mark
J*******o
发帖数: 741
12
bless!
b*********s
发帖数: 115
13
bless
s*****p
发帖数: 108
14
lz有update吗？
l********7
发帖数: 40
15
另一个offer的deadline时间不够了，我后来把F给withdraw了

【在 s*****p 的大作中提到】
: lz有update吗？
c********s
发帖数: 817
16
Bless!
z***e
发帖数: 209
17
赞,有空学习一下.
m******s
发帖数: 1469
18
Bless

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
P****9
发帖数: 177
19
多谢分享！
祝拿到offer！
A*****o
发帖数: 284
20
祝LZ拿到offer ~~
顺便献丑贴个email那题自己的完整代码，真心觉得不简单．．．　我是用了并查集来
统计合并，
请大牛给个简单点的解法吧，面试中是不可能有时间写这种代码的感觉．．．
#include
#include
#include
#include
#include
using namespace std;
/*
第二题是有这么一个class Contact，里面有一个String的name，和一个List
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [j**[email protected]]
#2 Mary [m**[email protected]]
#3 John [j**[email protected]]
#4 John [j**[email protected], j**[email protected], j**[email protected]]
#5 Bob [b*[email protected]]
现在我们知道如果email address相同的话，那么就说明是同一个人，现在要做的是根
据这些email address，把同一个contact给group起来，生成一个List>
，比如我们就可以知道#1，#3，#4是同一个人。注意不能根据名字来group，因为有可
能有相同名字的人，或者同一个人有可能有不同的名字来注册之类的。我给出了一个类
似graph的解法。时间不够，就没有写code，只是把逻辑解释了一遍
*/
struct record {
string name;
vector emails;
};
// email -> input vector index
map > htable;
// union-find set
vector father;
vector ranks;
int find(int x) {
if (x == father[x]) return x;
return father[x] = find(father[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (ranks[x] < ranks[y]) {
father[x] = y;
}
else {
father[y] = x;
if (ranks[x] == ranks[y]) {
ranks[y]++;
}
}
}
vector > groupContact(vector & input) {
vector > res;
int n = input.size();
int k, i;
// hash stat email -> name index
for (k = 0; k < input.size(); k++) {
for (i = 0; i < input[k].emails.size(); i++) {
string email = input[k].emails[i];
htable[email].push_back(k);
}
}
father.resize(n);
ranks.resize(n);
for (i = 0; i < n; i++) {
father[i] = i;
ranks[i] = 0;
}
// union all names which has same email
map >::iterator it;
for (it = htable.begin(); it != htable.end(); it++) {
vector & v = it->second;
for (i = 0; i < v.size()-1; i++) {
unite(v[i], v[i+1]);
}
}
// all names which has the same father should be grouped together
map > m;
for (i = 0; i < n; i++) {
m[find(i)].push_back(i);
}
map >::iterator it2;
for (it2 = m.begin(); it2 != m.end(); it2++) {
vector & v = it2->second;
vector vs;
for (i = 0; i < v.size(); i++) {
vs.push_back(input[v[i]].name);
}
res.push_back(vs);
}
return res;
}
/*
#1 John [j**[email protected]]
#2 Mary [m**[email protected]]
#3 John [j**[email protected]]
#4 John [j**[email protected], j**[email protected], j**[email protected]]
#5 Bob [b*[email protected]]
*/
void run() {
vector input(5);
input[0].name = "John";
input[0].emails.push_back("j**[email protected]");
input[1].name = "Mary";
input[1].emails.push_back("m**[email protected]");
input[2].name = "John";
input[2].emails.push_back("j**[email protected]");
input[3].name = "John";
input[3].emails.push_back("j**[email protected]");
input[3].emails.push_back("j**[email protected]");
input[3].emails.push_back("j**[email protected]");
input[4].name = "Bob";
input[4].emails.push_back("b*[email protected]");
// algo impl here
vector > res = groupContact(input);
for (int k = 0; k < res.size(); k++) {
printf("group %d: ", k+1);
for (int i = 0; i < res[k].size(); i++) {
cout << res[k][i] << " ";
}
cout << endl;
}
}
int main() {
run();
return 0;
}
相关主题
● 请教一道google的数组遍历题● 问个题
● LC的题确实变难了。。。● How to convert string to string array (or vector) (转载)
● google interview question● 一道有关String的面试题
进入JobHunting版参与讨论
w*****d
发帖数: 105
21
bless，请问3sum原题是怎样的？
l*****a
发帖数: 14598
22
估计是：给定数组中找出三个数的和为给定值

【在 w*****d 的大作中提到】
: bless，请问3sum原题是怎样的？
z*******1
发帖数: 18
23
这第二题应该是想让用mapreduce吧？
p******d
发帖数: 63
24
第二题用map可以做。
struct Contact {
string name;
vector emails;
};
vector> sanitizeContacts(vector &contacts) {
int id = 0;
map M;
for (auto &each : contacts) {
int myId = -1;
for (auto &email : each.emails) {
if (M.find(email) != M.end()) {
if (myId < 0) {
myId = M[email];
} else {
M[email] = myId;
}
}
}
if (myId < 0) {
myId = id++;
}
for (auto &email : each.emails) {
if (M.find(email) == M.end()) {
M[email] = myId;
}
}
}
vector> output(id);
for (auto &each : M) {
output[each.second].emplace_back(each.first);
}
return output;
}


【在 A*****o 的大作中提到】
: 祝LZ拿到offer ~~
: 顺便献丑贴个email那题自己的完整代码，真心觉得不简单．．．　我是用了并查集来
: 统计合并，
: 请大牛给个简单点的解法吧，面试中是不可能有时间写这种代码的感觉．．．
: #include
: #include
: #include
: #include
: #include
: using namespace std;
e*******u
发帖数: 109
25
这样做的话， 有的id会对应empty的email list
当然可以后续再去除这种id

【在 p******d 的大作中提到】
: 第二题用map可以做。
: struct Contact {
: string name;
: vector emails;
: };
: vector> sanitizeContacts(vector &contacts) {
: int id = 0;
: map M;
: for (auto &each : contacts) {
: int myId = -1;
b****f
发帖数: 138
26
Mark
s***y
发帖数: 7
27
恭喜楼主，看来另一个offer也相当不错哦~

【在 l********7 的大作中提到】
: 另一个offer的deadline时间不够了，我后来把F给withdraw了
h*d
发帖数: 19309
28
Bless!

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
w***y
发帖数: 6251
29
赞 lz面经！
l********7
发帖数: 40
30
前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
一轮电面之后之后让去onsite
onsite是3轮面试，2轮coding加一轮的experience
coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
string大
第二题是有这么一个class Contact，里面有一个String的name，和一个List
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [j**[email protected]]
#2 Mary [m**[email protected]]
#3 John [j**[email protected]]
#4 John [j**[email protected], j**[email protected], j**[email protected]]
#5 Bob [b*[email protected]]
现在我们知道如果email address相同的话，那么就说明是同一个人，现在要做的是根
据这些email address，把同一个contact给group起来，生成一个List>
，比如我们就可以知道#1，#3，#4是同一个人。注意不能根据名字来group，因为有可
能有相同名字的人，或者同一个人有可能有不同的名字来注册之类的。我给出了一个类
似graph的解法。时间不够，就没有写code，只是把逻辑解释了一遍。
第二个人也是出了两道题目，第一题是给两个string，判断其中一个string能否对其中
的一个字符通过一次的insertion或者一次deletion或者一次replacement变成另外一个
string，比如
cat cast True #第一个string通过一次insertion可以变成第二个string
cat at True #deletion
cat cot True #replacement
cat dog False
cat cat False #因为这两个string相同，不需要任何的操作，要返回false
第二题是找出factorial(n)中有多少个0，我跟他说我做过
第三个人大部分时间都是问的experience，问为什么Facebook，对Facebook的哪个
feature最喜欢，为什么喜欢，然后这个feature还有什么不足。之后让给他一个非常
specific的例子说当你和同事出现技术上的冲突的时候，应该怎么解决，问的特别细，
特别深入。之后让写一道题，是leetcode上的，linux里面的cd命令那题，就是给定你
当前的系统路径比如/a/b，然后你要cd到另外一个目录，给你cd的输入比如cd ../pq/.
/r，那么最后的路径应该就是/a/pq/r，要求输出最后这个路径
facebook总体都不难，我觉得最多是leetcode中等难度的题，但是我也听说不同的人的
难度会差别很大。做的时候前两个人还比较顺，但是最后一个人我都没有怎么用过太多
的facebook，也就在那里瞎扯，写code的时候还被指出了一个非常低级的bug，听说F对
bugfree的要求特别高，所以求bless啊求bless啊
相关主题
● 请教c++的string vector问题，谢谢！● 问道看到的面试题
● 关于c++ new 的用法● 请问我写的这个代码哪可以改进一下
● 谁能贴一下求nth permutation 和已知permutation 求rank的code● google phone interview question
进入JobHunting版参与讨论
A*********c
发帖数: 430
31
这面经，太给力了，必须给力bless

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
c********e
发帖数: 186
32
Strong bless!!!!
y*****3
发帖数: 451
33
我感觉这些题不容易啊，bless!

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
w*****t
发帖数: 485
34
赞分享！
bless！
X*4
发帖数: 101
35
多谢分享
contact
string (delete, insert, replace)
都不会
lol

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
d**********x
发帖数: 4083
36
some people think they know a nlogn method
but they are wrong. of course including some... interviewers.

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
r*****t
发帖数: 68
37
Bless!!
v***n
发帖数: 562
38
BLESS!
w*******o
发帖数: 2
39
特地上来bless一下楼主~ 拿到fb请bg
c********p
发帖数: 1969
40
mark
相关主题
● google phone interview question● 请教一题
● 问个array in place operation的题目● MS a0, a1, ..., b0, b1... 问题
● F家 一道LIS 的变种● 我这个 4sum的解法是 o^3还是o^2? , xiexie
进入JobHunting版参与讨论
J*******o
发帖数: 741
41
bless!
b*********s
发帖数: 115
42
bless
s*****p
发帖数: 108
43
lz有update吗？
l********7
发帖数: 40
44
另一个offer的deadline时间不够了，我后来把F给withdraw了

【在 s*****p 的大作中提到】
: lz有update吗？
c********s
发帖数: 817
45
Bless!
z***e
发帖数: 209
46
赞,有空学习一下.
m******s
发帖数: 1469
47
Bless

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
P****9
发帖数: 177
48
多谢分享！
祝拿到offer！
A*****o
发帖数: 284
49
祝LZ拿到offer ~~
顺便献丑贴个email那题自己的完整代码，真心觉得不简单．．．　我是用了并查集来
统计合并，
请大牛给个简单点的解法吧，面试中是不可能有时间写这种代码的感觉．．．
#include
#include
#include
#include
#include
using namespace std;
/*
第二题是有这么一个class Contact，里面有一个String的name，和一个List
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [j**[email protected]]
#2 Mary [m**[email protected]]
#3 John [j**[email protected]]
#4 John [j**[email protected], j**[email protected], j**[email protected]]
#5 Bob [b*[email protected]]
现在我们知道如果email address相同的话，那么就说明是同一个人，现在要做的是根
据这些email address，把同一个contact给group起来，生成一个List>
，比如我们就可以知道#1，#3，#4是同一个人。注意不能根据名字来group，因为有可
能有相同名字的人，或者同一个人有可能有不同的名字来注册之类的。我给出了一个类
似graph的解法。时间不够，就没有写code，只是把逻辑解释了一遍
*/
struct record {
string name;
vector emails;
};
// email -> input vector index
map > htable;
// union-find set
vector father;
vector ranks;
int find(int x) {
if (x == father[x]) return x;
return father[x] = find(father[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (ranks[x] < ranks[y]) {
father[x] = y;
}
else {
father[y] = x;
if (ranks[x] == ranks[y]) {
ranks[y]++;
}
}
}
vector > groupContact(vector & input) {
vector > res;
int n = input.size();
int k, i;
// hash stat email -> name index
for (k = 0; k < input.size(); k++) {
for (i = 0; i < input[k].emails.size(); i++) {
string email = input[k].emails[i];
htable[email].push_back(k);
}
}
father.resize(n);
ranks.resize(n);
for (i = 0; i < n; i++) {
father[i] = i;
ranks[i] = 0;
}
// union all names which has same email
map >::iterator it;
for (it = htable.begin(); it != htable.end(); it++) {
vector & v = it->second;
for (i = 0; i < v.size()-1; i++) {
unite(v[i], v[i+1]);
}
}
// all names which has the same father should be grouped together
map > m;
for (i = 0; i < n; i++) {
m[find(i)].push_back(i);
}
map >::iterator it2;
for (it2 = m.begin(); it2 != m.end(); it2++) {
vector & v = it2->second;
vector vs;
for (i = 0; i < v.size(); i++) {
vs.push_back(input[v[i]].name);
}
res.push_back(vs);
}
return res;
}
/*
#1 John [j**[email protected]]
#2 Mary [m**[email protected]]
#3 John [j**[email protected]]
#4 John [j**[email protected], j**[email protected], j**[email protected]]
#5 Bob [b*[email protected]]
*/
void run() {
vector input(5);
input[0].name = "John";
input[0].emails.push_back("j**[email protected]");
input[1].name = "Mary";
input[1].emails.push_back("m**[email protected]");
input[2].name = "John";
input[2].emails.push_back("j**[email protected]");
input[3].name = "John";
input[3].emails.push_back("j**[email protected]");
input[3].emails.push_back("j**[email protected]");
input[3].emails.push_back("j**[email protected]");
input[4].name = "Bob";
input[4].emails.push_back("b*[email protected]");
// algo impl here
vector > res = groupContact(input);
for (int k = 0; k < res.size(); k++) {
printf("group %d: ", k+1);
for (int i = 0; i < res[k].size(); i++) {
cout << res[k][i] << " ";
}
cout << endl;
}
}
int main() {
run();
return 0;
}
w*****d
发帖数: 105
50
bless，请问3sum原题是怎样的？
相关主题
● 问个老问题 Longest palindrome in a string● LC的题确实变难了。。。
● Google Intern● google interview question
● 请教一道google的数组遍历题● 问个题
进入JobHunting版参与讨论
l*****a
发帖数: 14598
51
估计是：给定数组中找出三个数的和为给定值

【在 w*****d 的大作中提到】
: bless，请问3sum原题是怎样的？
z*******1
发帖数: 18
52
这第二题应该是想让用mapreduce吧？
p******d
发帖数: 63
53
第二题用map可以做。
struct Contact {
string name;
vector emails;
};
vector> sanitizeContacts(vector &contacts) {
int id = 0;
map M;
for (auto &each : contacts) {
int myId = -1;
for (auto &email : each.emails) {
if (M.find(email) != M.end()) {
if (myId < 0) {
myId = M[email];
} else {
M[email] = myId;
}
}
}
if (myId < 0) {
myId = id++;
}
for (auto &email : each.emails) {
if (M.find(email) == M.end()) {
M[email] = myId;
}
}
}
vector> output(id);
for (auto &each : M) {
output[each.second].emplace_back(each.first);
}
return output;
}


【在 A*****o 的大作中提到】
: 祝LZ拿到offer ~~
: 顺便献丑贴个email那题自己的完整代码，真心觉得不简单．．．　我是用了并查集来
: 统计合并，
: 请大牛给个简单点的解法吧，面试中是不可能有时间写这种代码的感觉．．．
: #include
: #include
: #include
: #include
: #include
: using namespace std;
e*******u
发帖数: 109
54
这样做的话， 有的id会对应empty的email list
当然可以后续再去除这种id

【在 p******d 的大作中提到】
: 第二题用map可以做。
: struct Contact {
: string name;
: vector emails;
: };
: vector> sanitizeContacts(vector &contacts) {
: int id = 0;
: map M;
: for (auto &each : contacts) {
: int myId = -1;
b****f
发帖数: 138
55
Mark
s***y
发帖数: 7
56
恭喜楼主，看来另一个offer也相当不错哦~

【在 l********7 的大作中提到】
: 另一个offer的deadline时间不够了，我后来把F给withdraw了
h*d
发帖数: 19309
57
Bless!

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
w***y
发帖数: 6251
58
赞 lz面经！
z****u
发帖数: 41
59
并查集中rank的更新是不是有问题啊？ 在unite函数里面的else里面，因为这个时候x
是root了，所以应该更新x的rank吧，所以应该是ranks[x]++; instead of ranks[y]++。

【在 A*****o 的大作中提到】
: 祝LZ拿到offer ~~
: 顺便献丑贴个email那题自己的完整代码，真心觉得不简单．．．　我是用了并查集来
: 统计合并，
: 请大牛给个简单点的解法吧，面试中是不可能有时间写这种代码的感觉．．．
: #include
: #include
: #include
: #include
: #include
: using namespace std;
R*******d
发帖数: 13640
60
bless
相关主题
● How to convert string to string array (or vector) (转载)● 关于c++ new 的用法
● 一道有关String的面试题● 谁能贴一下求nth permutation 和已知permutation 求rank的code
● 请教c++的string vector问题，谢谢！● 问道看到的面试题
进入JobHunting版参与讨论
m*******f
发帖数: 17
61
/*
第二题是有这么一个class Contact，里面有一个String的name，和一个List
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [j**[email protected]]
#2 Mary [m**[email protected]]
#3 John [j**[email protected]]
#4 John [j**[email protected], j**[email protected], j**[email protected]]
#5 Bob [b*[email protected]]
现在我们知道如果email address相同的话，那么就说明是同一个人，现在要做的是根
据这些email address，把同一个contact给group起来，生成一个List>
，比如我们就可以知道#1，#3，#4是同一个人。注意不能根据名字来group，因为有可
能有相同名字的人，或者同一个人有可能有不同的名字来注册之类的。我给出了一个类
似graph的解法。时间不够，就没有写code，只是把逻辑解释了一遍
*/
弱问...
会有可能
#1 Jonathan [j**[email protected]]
#3 Johnny [j**[email protected]]
#4 John [j**[email protected], j**[email protected], j**[email protected]]
这种input 但是同时Jonathan, Johnny & John是同一个人
所以输出的时候要把作为一个group放进List里?
k****i
发帖数: 128
62
这个解法是错的吧
john1 (email1, email2)
john2 (email3, email4)
john3 (email1, email3, email7)
最后email4的id是和email3不同的

【在 p******d 的大作中提到】
: 第二题用map可以做。
: struct Contact {
: string name;
: vector emails;
: };
: vector> sanitizeContacts(vector &contacts) {
: int id = 0;
: map M;
: for (auto &each : contacts) {
: int myId = -1;
f*****6
发帖数: 61
63

请问下大牛你面的是什么level的职位？
谢谢

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
c******n
发帖数: 4965
64
多谢！

【在 l********7 的大作中提到】
: 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
: 我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
: 出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
: 一轮电面之后之后让去onsite
: onsite是3轮面试，2轮coding加一轮的experience
: coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
: 两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
: 的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
: string大
: 第二题是有这么一个class Contact，里面有一个String的name，和一个List
1 (共1页)
进入JobHunting版参与讨论
相关主题
● How to convert string to string array (or vector) (转载)● 问个array in place operation的题目
● 一道有关String的面试题● F家 一道LIS 的变种
● 请教c++的string vector问题，谢谢！● 请教一题
● 关于c++ new 的用法● MS a0, a1, ..., b0, b1... 问题
● 谁能贴一下求nth permutation 和已知permutation 求rank的code● 我这个 4sum的解法是 o^3还是o^2? , xiexie
● 问道看到的面试题● 问个老问题 Longest palindrome in a string
● 请问我写的这个代码哪可以改进一下● Google Intern
● google phone interview question● 请教一道google的数组遍历题
相关话题的讨论汇总
话题: string话题: vector话题: john话题: int话题: input

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑