Yelp Onsite 1-10
https://qiuzhihui.gitbooks.io/r-book/content/yp_design.html
P1 How do I find the greatest sum on a path from root to leaf (that can only touch one node per level—no going up and down) in this tree like structure?Question Quora link
class Solution {
public:
int maxPathSum(TreeNode* root) {
if (!root) return 0;
int l = maxPathSum(root->left);
int r = maxPathSum(root->right);
return max(l, r)+root->val;
}
};
这道题抽空写一下吧 124. Binary Tree Maximum Path Sum
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
int helper(TreeNode* root, int& res) {
if (!root) return 0;
int l = helper(root->left, res); l = l*(l>0);
int r = helper(root->right, res); r = r*(r>0);
res = max(res, l+r+root->val);
return max(l, r)+root->val;
}
public:
int maxPathSum(TreeNode* root) {
int res = INT_MIN;
helper(root, res);
return res;
}
};
P2 第一轮面，上来就问 why yelp，然后问简历的project。完了之后做题目，leetcode 121 best time to buy and sell stock 原题。我一上来居然想到了trapping water那题。。。用了两个数组来存某个位置其左边最小值，和其右边最大值。在面试官引导优化了空间，最后其实不用额外空间就可以的。。。
121. Best Time to Buy and Sell Stock
class Solution {
public:
int maxProfit(vector<int>& prices) {
int low = INT_MAX, res = 0;
for (int& p:prices) {
low = min(low, p);
res = max(res, p-low);
}
return res;
}
};
P3 第二轮面，还是问 why yelp，然后问简历的project。然后是一道 smallest k elements in an array的题，用个max heap搞定。我感觉挺满意。结果面试官又来一题。简易版的 lc 290 word pattern， 比如 foo 对应 app 就是对的，要是 foo 对应 apg 那就是错啦。很简单吧。结果我上来只用了一个HashMap，写完了后，他让我写test case，我自己写了下，发现不对，赶紧又加了一个HashMap.. 险过。
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
class Solution {
public:
vector<int> kthSmall(vector<int> nums, int k) {
priority_queue<int> pq;
for (int a: nums) {
if (pq.size() < k) pq.push(a);
else if (pq.top() > a){
pq.pop(); pq.push(a);
}
}
vector<int> res;
while (!pq.empty()) { res.push_back(pq.top()); pq.pop(); }
return res;
}
};
int main() {
Solution sol;
for (auto s: sol.kthSmall({10,9,8,7,6,5,4,3,2,1}, 3)) cout << s << " ";
cout << endl;
}
class Solution {
public:
bool wordPattern(string pattern, string str) {
istringstream is(str);
string chunk; int i = 0;
unordered_set<string> used;
unordered_map<char, string> m;
while (getline(is, chunk, ' ')) {
if (!m.count(pattern[i])) {
if (used.count(chunk)) return false;
used.insert(chunk);
m[pattern[i]] = chunk;
} else if (m[pattern[i]] != chunk) return false;
++i;
}
return i == pattern.size();
}
};
P4 第三轮面，还是问 why yelp，然后问简历的project。需要提一下，每轮面试官结束后，他会和下个面试官交流个两三分钟，然后下个面试官再进来。我前两轮介绍的project都是我最熟的那个，结果第三个面试官就直接问我，你咋总是讲那一个project。。。 好吧，换个project开始侃了。侃完了后，出一道题，懵了。
你们帮我看一看。题目是：给一串movie，假定每个movie都是一个小时，并且都在整点播放；给你一个List的movies，让你安排播放时间，如果没有答案throw一个exception。
比如
电影A: 14, 15, 16, 17
电影B: 14, 15, 16
电影C: 14, 15
电影D: 14, 15, 17
返回一个解就行，比如 A 14, B 16, C 15, D 17。 如果你要 A 14, B 15, 后面 C就没法看了。
发现了没，全是地里面yelp出现过的原题。要好好看面经啊，也要多来发面经啊，大家要团结。算法题都是讲完了思路，然后写白板code的，写完后带着对方walk through一下。讲思路的时候可以乱一点，先来个brute force也行。但开始写的时候就不能乱来了，要尽量别出错。哎，我平时题目刷的不不够熟，表现的一般吧。还跪了第三轮。。 面我的大多是做backend的，我正好最近在研究谷歌三剑客，把GFS, MapReduce和他们讲了一通，感觉还好。 面试结束后HR有和我聊了一阵，然后说负责我的HR没来，下周二她回来上班，然后如果positive的话，会问我要reference。不知道跪没跪。。哎，求人品~~~
#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;
class Solution {
void dfs(vector<vector<int>>& movies, vector<pair<int,int>>& out, int i, unordered_set<int> s, vector<vector<pair<int,int>>>& res) {
if (i == movies.size()) { res.push_back(out); return; }
for (int mt: movies[i]) { // movie time of current movie i
if (!s.count(mt)) {
out.push_back({i, mt});
s.insert(mt);
dfs(movies, out, i+1, s, res);
out.pop_back();
s.erase(mt);
}
}
}
public:
vector<vector<pair<int,int>>> movieSchedule(vector<vector<int>>& movies) {
vector<vector<pair<int,int>>> res;
vector<pair<int,int>> out;
unordered_set<int> s;
dfs(movies, out, 0, s, res);
return res;
}
};
int main() {
Solution sol;
vector<vector<int>> movies = {{14,15,16,17}, {14,15,16}, {14,15}, {14,15,17}};
for (auto& s: sol.movieSchedule(movies)) {
for (auto& m: s) {
cout << m.first << " " << m.second << ",";
}
cout << endl;
}
}
P5 还是问 why yelp，然后问还有什么feature可以加到yelp里。那好多feature啊，你yelp不能买票吧，你yelp不能叫外卖吧，你yelp不能直接付款吧，你yelp不能团购吧，你yelp没有饭店哭胖吧。。。
然后上题，设计一个Rate limitor。就是一小时内访问第六次时，就返回false。这也没啥算法啊，我没太明白，就是HashMap，存访问的IP和ArrayList，然后同一个IP一小时内访问第六次，那就返回 false呗。面试官说就是这样的，然后我用java把这个函数写出来。然后讨论了些他做的工作啊什么的，结束了
跟359. Logger Rate Limiter有点像
#include <deque>
#include <unordered_map>
#include <iostream>
using namespace std;
class RateLimiter {
public:
RateLimiter(int x): cap(x) {}
bool checkIP(int ip, int timestamp) {
if (m[ip].size() < cap) {
m[ip].push_back(timestamp);
return true;
} else {
if (timestamp - m[ip].front() >= 60) {
m[ip].pop_front();
m[ip].push_back(timestamp);
return true;
}
return false;
}
}
private:
int cap;
unordered_map<int, deque<int>> m;
};
int main() {
RateLimiter r(6);
cout << r.checkIP(1,1) << endl;
cout << r.checkIP(1,2) << endl;
cout << r.checkIP(1,3) << endl;
cout << r.checkIP(1,4) << endl;
cout << r.checkIP(1,5) << endl;
cout << r.checkIP(1,6) << endl;
cout << r.checkIP(1,7) << endl;
cout << r.checkIP(1,61) << endl;
cout << r.checkIP(1,62) << endl;
}
P6 1轮skype的美国大哥：聊简历，coding题是给你一群nodes，每一个node里有3个invariants: unique的id，可能重名的label，其parent的id。要求将一组乱序的nodes按照如下方式print出来：
Node A
Node B
Node C
Node D
Node E
这里BD的parent为A，C的为B，AE的为一个id=0的默认root（不print），也就是子node按照depth要缩进相应的空格。 这题不难，我是先遍历nodes重建了储存children关系的hash table，然后写了一个基于stack的方法，中间卡了下壳，还好大哥人很nice，提示了下，就“looks great to me”了。Follow up是“我看你写的是iteration，告诉我写成recursion的话pros和cons是啥”，我答了一些基本比较，他满意，后面就闲聊
思路：我觉得这道题还是有点意思的啊。
#include <vector>
#include <string>
#include <unordered_map>
#include <iostream>
using namespace std;
struct Node {
Node(int id_, int pid_, string label_): id(id_), pid(pid_), label(label_) {}
int id;
int pid;
string label;
};
class Solution {
void dfs(unordered_map<int, vector<Node*>>& m, Node* root, int depth) {
string indent(depth, ' ');
cout << indent << root->label << endl;
for (auto& a: m[root->id]) {
dfs(m, a, depth+1);
}
}
public:
void printNodes(vector<Node*>& nodes) {
unordered_map<int, vector<Node*>> m;
for (auto& n: nodes) {
m[n->pid].push_back(n);
}
for (auto& a: m[0]) {
dfs(m, a, 0);
}
}
};
int main() {
Node* a = new Node(1, 0, "A");
Node* b = new Node(2, 1, "B");
Node* c = new Node(3, 2, "C");
Node* d = new Node(4, 1, "D");
Node* e = new Node(5, 0, "E");
vector<Node*> nodes({a,b,c,d,e});
Solution s;
s.printNodes(nodes);
}
用stack的写法
#include <vector>
#include <string>
#include <unordered_map>
#include <stack>
#include <iostream>
using namespace std;
struct Node {
Node(int id_, int pid_, string label_): id(id_), pid(pid_), label(label_) {}
int id;
int pid;
string label;
};
class Solution {
public:
void printNodes(vector<Node*>& nodes) {
unordered_map<int, vector<Node*>> m;
stack<pair<Node*,int>> s;
for (auto& n: nodes) {
if (n->pid == 0) s.push({n,0});
else m[n->pid].push_back(n);
}
while (!s.empty()) {
auto t = s.top(); s.pop();
cout << string(t.second, ' ') << t.first->label << endl;
for (auto& a: m[t.first->id]) {
s.push({a, t.second+1});
}
}
}
};
int main() {
Node* a = new Node(1, 0, "A");
Node* b = new Node(2, 1, "B");
Node* c = new Node(3, 1, "C");
Node* d = new Node(4, 0, "D");
vector<Node*> nodes({a,b,c,d});
Solution s;
s.printNodes(nodes);
}
P7 2轮中国大哥：一个很典型的干瘦中国人，搞deep learning的，问题很尖锐。聊简历：问的很深，HMM,GMM,CNN,EM等。设计题：打开yelp，输入关键词restaurant返回一个附近restaurant的候选列表，问这一功能如何实现？答的search+filter+ranking，后来问我为何你用这种ranking方法不用其他的，这应该是一个开放性问题。coding：设计一个函数，给定一个list，能够返回一个内部元素random permutation过后的该list。很快写出一共不到10行，随后问一些基于permutation的概率题，最后说你如何测试该函数。楼主答的一测试edge cases，二测试overall results是否uniformly distributed。由于并不是很懂伪随机的原理，可能在这里答一些伪随机的内容会更好。
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
class Solution {
public:
void randomPermute(vector<int>& nums) {
int n = nums.size();
for (int i = n-1; i >= 0; --i) {
int j = rand() % (i+1);
swap(nums[i], nums[j]);
}
}
};
int main() {
vector<int> nums({1, 2, 3});
Solution s;
s.randomPermute(nums);
for (auto& a: nums) cout << a << " "; cout << endl;
map<vector<int>, int> m;
for (int i = 0; i < 1000; ++i) {
s.randomPermute(nums);
++m[nums];
}
for (auto& a: m) {
for (auto& b: a.first) cout << b << " ";
cout << "," << a.second << endl;
}
}
P8 3轮美国小哥：Physics PhD帅哥。聊简历，设计题：yelp现在要给附近一些新发掘的店铺定制category label，问你如何根据user对该新店铺的review得知该店铺属于restaurant, gas station,...的哪一个。classification问题，也是开放性的。Followup是如何对应“I just had a meal nextdoor”这种容易将一般店铺误判为restaurant的review。coding题出乎意料的简单。说是yelp每次有人访问会给一个临时id，6位digits，问你如何判断这6数字里有重复的…一行搞定，第二问是给了一个当天所有临时id的log，求今天id中带有重复数字的比率是多少…套用前问结果10行搞定，最后又来permutation相关的概率题，但都很简单。
#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;
class Solution {
public:
bool isDuplicate(int id) {
if (id <= 10) return true;
unordered_set<int> s;
int len = 0;
while (id) {
s.insert(id%10);
id /= 10;
++len;
}
return len == (int)s.size();
}
double percent(vector<int>& ids) {
int cnt = 0;
for (auto id: ids) {
if (isDuplicate(id)) ++cnt;
}
return 1.0*cnt/ids.size();
}
};
int main() {
Solution s;
vector<int> ids({1,2,3,4,5,6,7,8,9,10,11,100});
cout << s.percent(ids) << endl;
}
P9 4轮三哥：不好好听就提问打断，玩手机，全程站起来转椅子玩（醉了），不交流不帮助不给思考时间，楼主卡壳他就直接下一题。聊简历，coding题是leetcode原题longest palindromic substring，还问我之前见过这题没。我说没，然后想不起来O(n)的方法了就只好写了最土的从每个字符往两边搜的$$O(n^2)$$方法。Followup是我只有一个只能获得最长odd length palindrome的函数f_odd，问如何调用这个得到原函数，也就是 f (s) = g1(f_odd(g2(s)))，求g1，g2。楼主答了给原string插入#再处理，最后得到结果后每隔一个字去除#，被问原string含#怎么办，卡壳不到30秒就说算了我问你behavioral question，然后心不在焉地听了会就结束了。
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2) return s;
int l = 0, r = 0, n = s.size(), maxlen = 0, maxstart = 0;
for (int i = 0; i < n && n-i > maxlen/2;) {
l = r = i;
while (r < n-1 && s[r] == s[r+1]) ++r; // skip duplicates
i = r+1;
while (r < n-1 && l > 0 && s[l-1] == s[r+1]) {
++r; --l;
}
int len = r-l+1;
if (len > maxlen) {
maxlen = len;
maxstart = l;
}
}
return s.substr(maxstart, maxlen);
}
};
Manacher's Algorithm 6ms
class Solution {
string preProcess(string& s) {
string t("#");
for (auto c: s) {
t += c; t += "#";
}
return t;
}
public:
string longestPalindrome(string s) {
string t = preProcess(s);
// cout << t << endl;
int n = t.size(), C = 0, R = 0, mC = 0, mlen = 0;
vector<int> P(n, 0);
for (int i = 1; i < n-1; ++i) {
int i_mirror = 2*C-i; // equals to i' = C - (i-C)
P[i] = (R > i) ? min(P[i_mirror], R-i):0;
while (i-P[i]-1 >= 0 && i+P[i]+1 < n && t[i-P[i]-1] == t[i+P[i]+1]) ++P[i];
//cout << t[i] << " " << P[i] << endl;
if (i+P[i] > R) {
C = i; R = i+P[i];
}
if (mlen < P[i]) {
mC = i; mlen = P[i];
}
}
return s.substr((mC-mlen)/2, mlen);
}
};
哈哈谢谢clarification. 如果这样，好像并不需要考虑原str是否含#啊？ 因为对插入处理后str调用f_odd得到的最长子串substr_n，总是以#开头并且这个#一定是后来插入的（反证法）。去除idx = 0, 2, 4。。。上的#就可以了吧？
P10 TinyURL 用最简单的发号的方法写了一个
#include <string>
#include <unordered_map>
#include <exception>
#include <iostream>
using namespace std;
class TinyUrl {
public:
string longToShort(string url) {
if (l2s.count(url)) return prefix+to_string(l2s[url]);
int cnt = l2s.size();
l2s[url] = cnt;
s2l[cnt] = url;
return prefix+to_string(cnt);
}
string shortToLong(string url) {
if (url.substr(0,8) == prefix) {
int cnt = stoi(url.substr(8));
if (s2l.count(cnt)) return s2l[cnt];
throw exception();
}
throw exception();
}
private:
string prefix = "zach.cn/";
unordered_map<string, int> l2s;
unordered_map<int, string> s2l;
};
int main() {
TinyUrl so;
cout << so.longToShort("www.abc.com/sadjasnvxvx") << endl;
cout << so.shortToLong("zach.cn/0") << endl;
cout << so.longToShort("www.aaa.com/dsakhzxhvcx") << endl;
cout << so.shortToLong("zach.cn/1") << endl;
cout << so.longToShort("www.bbb.comwqruwqifqin") << endl;
cout << so.shortToLong("hihi") << endl;
}
P10 第二个是个印度manager，聊projects，让写merge interval，问了dns, tcp, 数据库等基本知识。
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end(), [](Interval&a, Interval&b){return a.start < b.start;});
vector<Interval> res = {intervals[0]};
for (int i = 1; i < intervals.size(); ++i) {
if (res.back().end < intervals[i].start) res.push_back(intervals[i]);
else {
res.back().end = max(intervals[i].end, res.back().end);
}
}
return res;
}
};