Yelp Onsite 11-20
P11 最后一个中国大哥萌萌哒，跟我聊了半个小时的天，然后让我design yelp's most recent reviews of your friends的API，然后一些简单的runtime问题，最后大哥还非常贴心地介绍了一下Yelp整个的构架。 直接根据timestamp来sort?用一个max heap？然后根据最近的一个一个Pop出来。
P12 第一轮白人大叔还是小哥来着。先让我讲讲我实习的project，然后是coding题目是 leetcode 03 其实我觉得这道题有点难啊
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0, cnt = 0, start = 0;
vector<int> v(128,-1);
for (int i = 0; i < s.size(); ++i) {
if (v[s[i]] != -1 && start <= v[s[i]]) {
start = v[s[i]]+1;
v[s[i]] = i;
} else {
v[s[i]] = i;
res = max(res, i-start+1);
}
}
return res;
}
};
P13 第四轮白人小哥直接做题，leetcode 212 word sarch II
class Solution {
vector<int> dirs = {0,-1,0,1,0};
bool dfs(vector<vector<char>>& board, string& word, int pos, int row, int col) {
if (pos == word.size()) return true;
for (int i = 0; i < 4; ++i) {
int x = row+dirs[i], y = col+dirs[i+1];
if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] == word[pos]) {
board[x][y] = '\0';
if (dfs(board, word, pos+1, x, y)) return true;
board[x][y] = word[pos];
}
}
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
if (board[i][j] == word[0]) {
board[i][j] = '\0';
if (dfs(board, word, 1, i, j)) return true;
board[i][j] = word[0];
}
}
}
return false;
}
};
class Solution {
struct TreeNode {
bool isWord;
vector<TreeNode*> children;
TreeNode(): isWord(false), children(26,NULL) {}
};
void addWord(string& word) {
TreeNode* cur = root;
for (auto& c: word) {
if (!cur->children[c-'a']) cur->children[c-'a'] = new TreeNode();
cur = cur->children[c-'a'];
}
cur->isWord = true;
}
void dfs(vector<vector<char>>& board, int row, int col, TreeNode* p, string path, vector<string>& res) {
if (p->isWord) {
p->isWord = false;
res.push_back(path);
}
for (int i = 0; i < 4; ++i) {
int x = row+dir[i], y = col+dir[i+1];
if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] != '#') {
char c = board[x][y];
if (p->children[c-'a']) {
board[x][y] = '#';
dfs(board, x, y, p->children[c-'a'], path+c, res);
board[x][y] = c;
}
}
}
}
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
root = new TreeNode();
for (auto& w: words) addWord(w);
vector<string> res;
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
char c = board[i][j];
if (root->children[c-'a']) {
board[i][j] = '#';
dfs(board, i, j, root->children[c-'a'], string(1,c), res);
board[i][j] = c;
}
}
}
return res;
}
private:
TreeNode* root;
vector<int> dir = {0,-1,0,1,0};
};
P14 273. Integer to English Words https://leetcode.com/problems/integer-to-english-words/ 难倒不难，就是写起来呀。有点恶心
class Solution {
private:
vector<string> less20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
vector<string> tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
vector<string> thousands = {"", " Thousand", " Million", " Billion" };
string helper(int num) {
if (num == 0) return "";
else if (num < 20) return less20[num];
else if (num < 100) return tens[num/10] + (num%10 ? " "+helper(num%10):"");
else return less20[num/100] + " Hundred" + (num%100 ? " "+helper(num%100):"");
}
public:
string numberToWords(int num) {
if (num == 0) return "Zero";
string res;
int idx = 0;
while (num) {
if (num%1000) res = helper(num%1000)+thousands[idx]+(res.size() ? " "+res:"");
num /= 1000;
++idx;
}
return res;
}
};
P15 regular expression matching
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m+1, vector<bool>(n+1,false));
dp[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j-1] == '*')
dp[i][j] = dp[i][j-2] || (i > 0 && (s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j]);
else
dp[i][j] = i > 0 && dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
}
}
return dp[m][n];
}
};
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;
}
};
class Solution {
void dfs(vector<int>& nums, int begin, vector<vector<int>>& res) {
if (begin == nums.size()) {
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]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
dfs(nums, 0, res);
return res;
}
};
P17 第一轮：why yelp，improvement。题是address similarity，follow up很多
P18 332. Reconstruct Itinerary
version 1: DFS, Recursion
class Solution {
void dfs(unordered_map<string,multiset<string>>& m, string cur, vector<string>& res) {
while (m[cur].size()) {
string t = *m[cur].begin();
m[cur].erase(m[cur].begin());
dfs(m, t, res);
}
res.push_back(cur);
}
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
unordered_map<string,multiset<string>> m;
for (auto& a: tickets) m[a.first].insert(a.second);
vector<string> res;
dfs(m, "JFK", res);
return vector<string>(res.rbegin(), res.rend());
}
};
version 2: DFS, Iteration
class Solution {
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
// unordered_map<string, vector<string>> m;
unordered_map<string, multiset<string>> m;
for (auto& a: tickets) m[a.first].insert(a.second);
// m[a.first].push_back(a.second);
stack<string> s; s.push("JFK");
int idx = tickets.size();
vector<string> res(idx+1);
while (!s.empty()) {
string airport = s.top();
if (m[airport].empty()) {
res[idx--] = airport;
s.pop();
} else {
// s.push(m[airport].back());
// s.pop_back();
s.push(*m[airport].begin());
m[airport].erase(m[airport].begin());
}
}
return res;
}
};
P19 第二轮：印度男谈一个project谈到了loadbalancer的调度，让实现了一个roundrobin。第二题给你一堆 work (1,3) (2,4) (3,5) (4,8)，怎样选择work能做更多的小时数同时没有冲突。按起始时间sort然后backtraking
version 1: return working hours
#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;
class Solution {
void dfs(vector<vector<int>>& tasks, int pos, int hour, int& res) {
if (pos == tasks.size()) {
if (hour > res) res = hour;
return;
}
for (int i = pos; i < tasks.size(); ++i) {
if (pos == 0) dfs(tasks, i+1, tasks[i][1]-tasks[i][0], res);
else {
if (tasks[i][0] >= tasks[pos-1][1]) { // prev task: tasks[pos-1]
dfs(tasks, i+1, hour+tasks[i][1]-tasks[i][0], res);
}
}
}
}
public:
int mostWork(vector<vector<int>>& tasks) {
sort(tasks.begin(), tasks.end(),
[](vector<int>& a, vector<int>& b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
});
int res = INT_MIN;
dfs(tasks, 0, 0, res);
return res;
}
};
int main() {
Solution s;
vector<vector<int>> tasks = {{1,3},{2,4},{3,5},{4,8}};
cout << s.mostWork(tasks) << endl;
}
version 2: return work schedule
#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;
class Solution {
void dfs(vector<vector<int>>& tasks, int pos, vector<vector<int>> path, int hour, vector<vector<int>>& res, int& maxhour) {
if (pos == tasks.size()) {
if (hour > maxhour) {
maxhour = hour;
res = path;
}
return;
}
for (int i = pos; i < tasks.size(); ++i) {
if (pos == 0) {
path.push_back(tasks[i]);
dfs(tasks, i+1, path, tasks[i][1]-tasks[i][0], res, maxhour);
path.pop_back();
} else {
if (tasks[i][0] >= tasks[pos-1][1]) { // prev task: tasks[pos-1]
path.push_back(tasks[i]);
dfs(tasks, i+1, path, hour+tasks[i][1]-tasks[i][0], res, maxhour);
path.pop_back();
}
}
}
}
public:
vector<vector<int>> mostWork(vector<vector<int>>& tasks) {
sort(tasks.begin(), tasks.end(),
[](vector<int>& a, vector<int>& b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
});
vector<vector<int>> res;
int maxhour = INT_MIN;
dfs(tasks, 0, {}, 0, res, maxhour);
return res;
}
};
int main() {
Solution s;
vector<vector<int>> tasks = {{1,3},{2,4},{3,5},{4,8}};
for (auto& a:s.mostWork(tasks)) {
cout << a[0] << " " << a[1] << endl;
}
}
P20 第四轮：白男。给你两个词语，如何根据第一个找到第二个。每个词语你会打开维基百科，然后里面有link指向其他词语。 bfs搞定。follow up：如果分布式系统怎么找。 第二题设计一个类，并且能把这个类generate成json。dfs因为json里可能嵌套json。
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <iostream>
using namespace std;
class Solution {
public:
bool canFind(unordered_map<string,vector<string>>& dict, string w1, string w2) {
queue<string> q; q.push(w1);
while (!q.empty()) {
string t = q.front(); q.pop();
for (string& a: dict[t]) {
if (a == w2) return true;
q.push(a);
}
}
return false;
}
};
int main() {
Solution s;
unordered_map<string,vector<string>> dict = {{"A",{"B","C"}},{"B",{"D","E"}},{"E",{"H","G"}}};
string word1 = "A", word2 = "G";
cout << s.canFind(dict, word1, word2) << endl;
}
class Node(object):
def __init__(self, val):
self.val = val
self.children = []
class Solution(object):
def class2json(self, node):
if not node:
return {}
res = {}
if not node.children:
res[node.val] = None
else:
children = []
for c in node.children:
children.append(self.class2json(c))
res[node.val] = children
return res
a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
a.children.append(b)
b.children.append(c)
b.children.append(d)
so = Solution()
ans = so.class2json(a)
print(ans)