Yelp Onsite 51-60
P51 第三轮. Manager, 先说一下enter yelp.com会发生什么，说了整个过程以后他会挑了一些具体的细节继续问，例如get 之后返回什么之类的。 然后coding部分是toplogical 排序
我发现好像现在的弯曲公司，面试一般里面都会有一轮topological sort，然后另外一轮考一个trie的题。是弯曲标配么？
当你在浏览器中输入 google.com 并且按下回车之后发生了什么？
P52 第四轮. 美国小哥，先聊了一下project，然后就是coding，leetcode原题，Longest Substring Without Repeating Characters， follow up是如果一台机器的memory不够呢，再follow up就是如果用assii码表示呢
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int i = 0, res = 0;
vector<int> v(128, 0);
for (int j = 0; j < s.size(); ++j) {
i = max(i, v[s[j]]); // new start position
res = max(res, j-i+1);
v[s[j]] = j+1;
}
return res;
}
};
代码之前写过了，memory不够的话，我们可以切块来做。最差的情况是每一个char对应一个index，所以dict的size最多也就255。然后我们只用使用这个dict来更新longest就行了。
请问楼主 第四轮 memory不够怎么办呢？
楼主能否再解释下如何处理memory不够的情况呢？关键是分成pieces后在断裂处有可能有更长的结果怎么处理这个的呢？比如piece1: aaaaaa(40个不同)，piece2: (30个不同与前面40个也不同)bbbbb， 最终应该是70那怎么考虑这个不同机器上得到结果merge部分求大神能详细说下不？真的跪谢了！
分成不同的pieces，分开的时候相邻的两个piece有256个重复的character，character最多有256个，结果的长度不会超过256，所以这样最后就不需要再考虑merge不同peice的事情了
link 昨天面了y家的onsite，纠结了一下还是决定发个面经攒攒人品求保佑求保佑。
他家喜欢周五下午面试，中午有engineer的免费午餐和learning group然后下午一点四十五面试。午餐体验很好，感觉他家员工都好年轻，朝气蓬勃。
P53 一轮：主要聊一个分布式系统的project，问了下map和reduce分别做什么工作，算法的参数怎么选，还有一些behavior问题，coding是给n门课程，每个课程有k个timeslot，问能不能排出一个n门课都选的课程表，用dfs，中间出了个小bug，改对的，这面觉得一般。
这道题跟movie schedule一样的道理
#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;
class Solution {
public:
vector<vector<int>> courseSchedule(vector<vector<int>>& courses) {
vector<vector<int>> res;
unordered_set<int> used;
dfs(courses, {}, 0, used, res);
return res;
}
void dfs(vector<vector<int>>& courses, vector<int> out, int i, unordered_set<int>& used, vector<vector<int>>& res) {
if (i == courses.size()) {
res.push_back(out); return;
}
for (auto& a: courses[i]) {
if (!used.count(a)) {
out.push_back(a);
used.insert(a);
dfs(courses, out, i+1, used, res);
out.pop_back();
used.erase(a);
}
}
}
};
int main() {
vector<vector<int>> courses = {{14,15,16,17}, {14,15,16}, {14,15}, {14,15,17}};
Solution sol;
for (auto& s: sol.courseSchedule(courses)) {
for (auto& m: s) {
cout << m << ",";
}
cout << endl;
}
return 0;
}
P54 二轮：manager面 问网站慢什么原因，然后洋洋洒洒扯数据库，总之这轮聊天环节很不错，coding类似permutation，dfs，bug free但我觉得我的板书写得好乱，有一处中间箭头加进去一行那种。
46 Permutations
class Solution {
// permute num[begin..end]
// invariant: num[0..begin-1] have been fixed/permuted
void dfs(vector<int>& nums, int begin, vector<vector<int>>& res) {
if (begin == nums.size()) {
// one permutation instance
res.push_back(nums); return;
}
for (int i = begin; i < nums.size(); ++i) {
swap(nums[begin], nums[i]);
dfs(nums, begin+1, res);
swap(nums[begin], nums[i]); // reset
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
dfs(nums, 0, res);
return res;
}
};
47 Permutations II
class Solution {
void dfs(vector<int> nums, int i, vector<vector<int>>& res) {
if (i == nums.size()-1) {res.push_back(nums); return;}
for (int k = i; k < nums.size(); ++k) {
if (k != i && nums[k] == nums[i]) continue;
swap(nums[i], nums[k]);
dfs(nums, i+1, res);
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
dfs(nums, 0, res);
return res;
}
};
P55 三轮：问了web development经验， 如何维护streaming data 的top k， coding是longest prefix of strings，bug free，写得也算干净，之后还剩十分钟，他说比我预期快一点，问了几个问题结束了。这轮聊天一般，前面体力有点费太多，有点累。
哦，就是最简单的输入规模无限大，维护一个k个数的堆的做法，用min heap，每次来的数小于堆顶就舍弃，大于堆顶就替换堆顶然后heapify
14 Longest Common Prefix
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) return "";
string res;
for (int i = 0; i < strs[0].size(); ++i) {
char c = strs[0][i];
for (int j = 1; j < strs.size(); ++j) {
if (i >= strs[j].size() || c != strs[j][i]) return res;
}
res += c;
}
return res;
}
};
P56 四轮：manager 问一个网站可能受到哪些安全攻击，对答算顺利，但后面他说的一个csrf attack确实没印象了。coding是encode decode 二叉树，他说有点complex，不一定做完，边做边讲思路就好。我做完了小超了两分钟，基本bug free吧，中间一个地方map.get(preorder[cur]) 写成了map.get(cur)，他应该也没有发现。说了句did a good job之类。
写过了
总之题都很简单，很幸运算是遇到三个原题，觉得按照我的水平都一次bug free且clean有点难度，在stressful的环境下有时确实容易短路。但是并不知道他家如何评判candidate，与我同面的都是名校的大神，而且感觉他家题都做好都难有offer，聊天的重要性又和coding不相上下且headcount还少，哎，只能说一切都是命。。。求点大米。
link backend 的职位，一共四轮：
P57 java 基本概念问题：garbage collection hashmap list 和 javascript 区别（我的第二语言） 数据库问题： Nosql 和 mysql 的选择 （从 resume project 延伸） 文化问题： 对 yelp 的功能提建议 why yelp why cs why sde
请问一下garbage collection都问了些什么问题呢？
我就是分两heap 和 stack解释下机制~
肯定还有更好的！ps 问一下lz的resume 和数据库有关project 是什么样的呀？backend要怎么学啊？边找工作边学来得及么。。。
就是web application 涉及到存数据的问题 呃 backend没什么特别要学的吧= = 一般就是 prefer java
算法题：
P58 load balancer 就是一个地址轮询，最多就是轮询前检查一下healthy不。具体情况具体讨论吧
根据不同server的承载度算总权重再算各自的频数出来，然后用随机数选取。 大概就是这样，太久了也记不清了~
link backend 的职位，一共四轮：
P57 java 基本概念问题：garbage collection hashmap list 和 javascript 区别（我的第二语言） 数据库问题： Nosql 和 mysql 的选择 （从 resume project 延伸） 文化问题： 对 yelp 的功能提建议 why yelp why cs why sde
请问一下garbage collection都问了些什么问题呢？
我就是分两heap 和 stack解释下机制~
肯定还有更好的！ps 问一下lz的resume 和数据库有关project 是什么样的呀？backend要怎么学啊？边找工作边学来得及么。。。
就是web application 涉及到存数据的问题 呃 backend没什么特别要学的吧= = 一般就是 prefer java
算法题:
P58 load balancer 就是一个地址轮询，最多就是轮询前检查一下healthy不。具体情况具体讨论吧
根据不同server的承载度算总权重再算各自的频数出来，然后用随机数选取。 大概就是这样，太久了也记不清了~
class LoadBanlancer(object):
def __init__(self, ips):
self.ips = ips
self.index = 0
def getIP(self):
if self.ips:
ip = ips[self.index]
self.index = (self.index+1)%len(self.ips)
return ip
def checkHealth(self, ip):
pass
ips = ['1.0.0.1', '1.1.1.2', '1.0.0.2']
so = LoadBanlancer(ips)
a = so.getIP()
print(a)
a = so.getIP()
print(a)
a = so.getIP()
print(a)
a = so.getIP()
print(a)
a = so.getIP()
print(a)
a = so.getIP()
print(a)
P59 search matrix II 给你一串 string 里面一些小写字母可能原来是大写求所有可能解.
74. Search a 2D Matrix Add to List
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size(), n = matrix[0].size();
int i = 0, j = m*n-1;
while (i <= j) {
int mid = i+(j-i)/2;
int x = mid/n, y = mid%n;
if (matrix[x][y] == target) return true;
else if (target < matrix[x][y]) --j;
else ++i;
}
return false;
}
};
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int i = 0, j = matrix[0].size()-1;
while (i < matrix.size() && j >= 0) {
if (target == matrix[i][j]) return true;
else if (target < matrix[i][j]) --j;
else ++i;
}
return false;
}
};
P60 如何对ordered input stream 进行搜索（从搜索延伸开），不用写代码只讲四轮和画图~ 不太懂这道题木的意思。如果是stream data的话，一个一个进来就直接check就行了啊。一片一片进来，那么就先检查首尾两个，看target是否在里面。在的话就binary search
应该是 input stream 搜索没有答好吧~我当时优化到最后说用二叉树 他就问我怎么构建 我不是很确定自己的思路是不是最优