半年前的面经了。找人做的内推。两轮店面：
第一轮店面：看名字听口音是硬度人。巫师那道题，网上能查到。因为相当于找最短路径，我用的是BFS。面试官提示能不能不用BFS，我当时想最短路径应该不能用DFS。后来想他可能希望Dijkstra。不过也没为难我，过了。
第二轮不记得了。难度和一面相当。做得不是很满意。也让过了。
然后约Onsite。早就听说他家非常注重culture fit，于是上网看了很多关于他家游记的文章。Onsite都是要现场跑Code跑面试官的test case的。我提前在VS Code上把程序框架准备好了。
第一轮：国人小哥
给一个数组，每个元素是某房东收到的订房check-in和check-out日期。求挑选出不重叠的订单获得最长的出租天数。DP。下面是我的code：
int maxProfit(vector<pair<int, int>> & req) {
int N = 31;
vector<int> dp(N);
sort(req.begin(), req.end(), [](auto const & a, auto const &b) {
return a.second != b.second ? a.second < b.second : a.first < b.first;
});
int idx = 0;
for (int i = 0; i < 31; i++) {
if (idx == int(req.size())) {
return dp[i - 1];
}
if (req[idx].second != i) {
if (i > 0) dp[i] = dp[i - 1];
}
else {
dp[i] = dp[i - 1];
for (int k = idx; idx<int(req.size()) && req[k].second == req[idx].second; idx++) {
int lastEnd = req[idx].first;
int x = req[idx].second - req[idx].first;
if (lastEnd >= 0) {
x += dp[lastEnd];
}
dp[i] = max(dp[i], x);
}
}
}
return dp.back();
}
小哥用email发来test case，测试通过。
(1, 3), (2, 5), (10, 17), (8, 11), (16, 21), (10, 11), (16, 17), (23, 26), (25, 30)
第二轮：国人小哥
第一题是经典的alien dictionary，很快秒了
string findOrder(vector<string> const & dict) {
if (dict.empty()) return "";
unordered_map<char, unordered_set<char>> edges;
unordered_set<char> ab;
unordered_map<char, int> degree;
ab.insert(dict[0].begin(), dict[0].end());
for (int i = 1; i<int(dict.size()); i++) {
auto& w1 = dict[i - 1];
auto& w2 = dict[i];
ab.insert(w2.begin(), w2.end());
int len = int(min(w1.size(), w2.size()));
for (int j = 0; j < len; j++) {
if (w1[j] != w2[j]) {
edges[w1[j]].insert(w2[j]);
degree[w2[j]]++;
break;
}
}
}
queue<char> q;
for (char c : ab) {
if (!degree.count(c)) {
q.emplace(c);
}
}
stringstream ss;
while (!q.empty()) {
char c = q.front();
q.pop();
ss << c;
for (char next : edges[c]) {
if (--degree[next] == 0) {
q.emplace(next);
}
}
}
string res = ss.str();
return res.size() == ab.size() ? res : "";
}
剩下时间还多，小哥又出了第二题，也是常见题，二维数组的iterator。也秒了。结束前5分钟，小哥让加remove。当时debug时有点小问题。他家面试时间45分钟时hard limit。小哥友好地又等了几分钟，终于搞定bug。
class Iter {
vector<vector<int>> & data;
int outer, inner;
void find() {
for (; outer < int(data.size()) && inner == int(data[outer].size()); outer++) {
inner = 0;
}
}
public:
Iter(vector<vector<int>> & data) : data(data), outer(0), inner(0) {
find();
}
int next() {
int val = data[outer][inner];
++inner;
find();
return val;
}
bool hasNext() {
return outer < int(data.size());
}
void remove() {
--inner;
while (inner <= 0 && outer > 0) {
inner = int(data[--outer].size()) - 1;
}
data[outer].erase(data[outer].begin() + inner);
while (inner == int(data[outer].size())) {
++outer;
inner = 0;
}
}
};
测试代码：
void test() {
vector<vector<int>> data{
{},
{1,2,3},
{},
{4},
{5,6}
};
Iter iter(data);
while (iter.hasNext()) {
int r = iter.next();
std::cout << r << ", ";
if (r == 2 || r == 3) {
iter.remove();
}
}
std::cout << std::endl;
Iter iter2(data);
while (iter2.hasNext()) {
int r = iter2.next();
std::cout << r << ", ";
}
}
- design. 本来时国人MM来的，结果临时有事，等了靠10分钟来了个硬度人。key-value storage。当时由于面试官在一个细节上纠缠太久导致最后几分钟草草把剩下部分都touch了一下。
午饭又国人小哥带着，讲英文，没有提问。
-
30分钟 culture fit。聊生活，人生，住airbnb经历。根据事先的功课，猛夸airbnb的local体验与众不同。有一问是说说你某一次一时兴起做过的事。
-
30分钟 culture fit
-
国人大哥，深挖以往project.
过了一周recruiter反馈说coding很好，需要加面design和一轮culture fit.
加面1. 国人大哥 设计translation system
加面2. 亚裔。准备了一个问题列表，每个问题必须简洁回答。整体感觉不太友好，有点刁难的感觉。
又过了一周，email告知被拒。回信问哪里可以改进，从此杳无音信。
总结：他家题库真的很小，花时间做熟了coding基本没问题。design题库也小，好好准备加上临场发挥。culture fit比较难搞。国人很多，很年轻。coding方面国人小哥们可能比较tough，但是能感觉到对同胞很友善。午饭很健康。