Yelp Onsite 41-50
P41 印度女 algo: Why developer over data scientist a long sentence, find the shortest distance between two words, duplicated word may appear
并没有看懂，我猜可能是这个
243 Shortest Word Distance
class Solution {
public:
int shortestDistance(vector<string>& words, string word1, string word2) {
int p1 = -1, p2 = -1, res = INT_MAX;
for (int i = 0; i < words.size(); ++i) {
if (words[i] == word1) p1 = i;
else if (words[i] == word2) p2 = i;
if (p1 != -1 && p2 != -1) res = min(res, abs(p1-p2));
}
return res;
}
};
244 Shortest Word Distance II
class WordDistance {
public:
WordDistance(vector<string> words) {
for (int i = 0; i < words.size(); ++i) {
m[words[i]].push_back(i);
}
}
int shortest(string word1, string word2) {
int i = 0, j = 0, res = INT_MAX;
while (i < m[word1].size() && j < m[word2].size()) {
if (m[word1][i] > m[word2][j]) {
res = min(res, m[word1][i]-m[word2][j++]);
} else {
res = min(res, m[word2][j]-m[word1][i++]);
}
}
return res;
}
private:
unordered_map<string, vector<int>> m;
};
245 Shortest Word Distance III
class Solution {
public:
int shortestWordDistance(vector<string>& words, string word1, string word2) {
int p1 = -1, p2 = -1, res = INT_MAX;
for (int i = 0; i < words.size(); ++i) {
if (words[i] == word1) p1 = (word1 == word2) ? p2:i;
if (words[i] == word2) p2 = i;
if (p1 != -1 && p2 != -1) res = min(res, abs(p1-p2));
}
return res;
}
};
class Solution {
public:
int shortestWordDistance(vector<string>& words, string word1, string word2) {
int idx = -1, res = INT_MAX;
for (int i = 0; i < words.size(); ++i) {
if (words[i] == word1 || words[i] == word2) {
if (idx != -1 && (word1 == word2 || words[idx] != words[i])) {
res = min(res, i-idx);
}
idx = i;
}
}
return res;
}
};
P42 白人男： 背景出身后端， 现在全栈 algo: architecture: talking about the Amazon Internship Project longest substring with no duplicated characters 可能没回答好的地方：
1. architecture
2. API
3. design pattern
3 Longest Substring Without Repeating Characters
#include <vector>
#include <string>
#include <iostream>
using namespace std;
class Solution {
public:
string lengthOfLongestSubstring(string s) {
int i = 0, maxlen = 0, maxstart = 0;
vector<int> v(128, 0);
for (int j = 0; j < s.size(); ++j) {
i = max(i, v[s[j]]); // new start position
if (j-i+1 > maxlen) {
maxlen = j-i+1;
maxstart = i;
}
v[s[j]] = j+1;
}
return s.substr(maxstart, maxlen);
}
};
int main() {
Solution s;
cout << s.lengthOfLongestSubstring("abcabcbb") << endl;
cout << s.lengthOfLongestSubstring("bbbb") << endl;
cout << s.lengthOfLongestSubstring("pwwkew") << endl;
cout << s.lengthOfLongestSubstring("") << endl;
}
P43 俄罗斯男 algo: tireTree + DFS, search in a 2-d matrix, talks about idea how it works 可能没回答好的地方：
1. 深度算法 DFS，data structure
2. side project
这道题我写过。 https://leetcode.com/problems/word-search-ii/
P44 印度男 algo: programming language: java vs python copy a linked list with random pointer, the random pointer pointing to an external object that can be any type 可能没回答好的地方：
1. API
2. programming language: how to choose language; compare different PL
3. design pattern
https://leetcode.com/problems/copy-list-with-random-pointer/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
unordered_map<RandomListNode*, RandomListNode*> m;
RandomListNode* node = head;
while (node) {
m[node] = new RandomListNode(node->label);
node = node->next;
}
node = head;
while (node) {
m[node]->next = m[node->next];
m[node]->random = m[node->random];
node = node->next;
}
return m[head];
}
};
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if (!head) return NULL;
RandomListNode* cur = head;
while (cur) {
RandomListNode* node = new RandomListNode(cur->label);
node->next = cur->next;
cur->next = node;
cur = node->next;
}
cur = head;
while (cur) {
if (cur->random) cur->next->random = cur->random->next;
cur = cur->next->next;
}
cur = head;
RandomListNode* res = head->next;
while (cur) {
RandomListNode* node = cur->next;
cur->next = node->next;
if (node->next) node->next = node->next->next;
cur = cur->next;
}
return res;
}
};
P45（1）美国小哥，面善，健谈 why yelp ? 果然问了！ 谈project， 谈趣点 what's the reason a page is loading slow? How can we improve? coding: business id那道题，之前有人po过的，给你一个字符串小写的带数字，比如 asd7d2c，在所有字母大小写组合的可能性中，返回所有是valid的 id，没啥难度，但是已经是一天里最有难度的题了T^T 为了更省时间，其实可以建trie。这样prefix没有match到的，就不用继续往下recurse了。
#include <vector>
#include <string>
#include <unordered_set>
#include <iostream>
using namespace std;
class Solution {
public:
vector<string> validID(string s, vector<string> words) {
vector<string> res;
unordered_set<string> dict;
for (auto& w: words) dict.insert(w);
dfs(s, 0, dict, res);
return res;
}
void dfs(string s, int pos, unordered_set<string>& dict, vector<string>& res) {
if (pos == s.size()) {
if (dict.count(s)) res.push_back(s);
return;
}
if (s[pos] >= '0' && s[pos] <= '9') dfs(s, pos+1, dict, res);
else {
s[pos] = toupper(s[pos]);
dfs(s, pos+1, dict, res);
s[pos] = tolower(s[pos]);
dfs(s, pos+1, dict, res);
}
}
};
int main() {
Solution s;
vector<string> words = {"aS4bc", "As4bC"};
for (auto& w: s.validID("as4bc", words)) cout << w << endl;
}
P46（2）棕色小哥，面善，不健谈 why yelp ? 又问！ 谈 project，谈难点 how will you want to improve yelp? 我说的都是用户体验 coding: given a text file, print them out line by line in a random order
请问一下你是怎么处理随机打印某一行这种操作的吗？ 比如把每行都放在了array里面的话，直接 int id = random() * array.size(); 然后去打印 坐标在 id 的内容就可以
#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <iostream>
using namespace std;
class Solution {
public:
void randomPrint(string filename) {
vector<string> lines;
string line;
ifstream fin(filename.c_str());
while (getline(fin, line)) {
lines.push_back(line);
}
int n = lines.size();
for (int i = 0; i < lines.size(); ++i) {
int pos = rand() % n;
cout << lines[pos] << endl;
swap(lines[pos], lines[--n]);
}
}
};
int main() {
Solution s;
s.randomPrint("test.txt");
}
P47（3）美国小叔，面不善不恶，健谈 why yelp ? 还问！！ 谈project， 谈印象深刻 pick two languages you are comfortable with, talk about their difference. (选了 C++ and Java 因为经常与人议论)
system design : a library database system that has entity Book and Reader, 要调查某个读者度过的所有书，或所有读过某本书的读者，如何设计？于是设计了新的entity Log
follow up (1) 如果一个读者反复读了很多次书呢？（要unique pair） follow up (2) 如果要获得读者读书的时间的记录呢？(多一个属性) follow up (3) 要查看一个读者读一本书的所有记录？(时间，读者，书 三个的组合要unique)
三个table, book, user, readingrecord tables.然后设计几个query就行了 我心中已有丘壑。
coding: 给一个数组，一个target， 返回所有加起来sum是target的pair，不重复。好吧这题算碾压，因为leetcode随便一个3sum, 4sum都能做了，这个只是其中的一部分
P26 每个数都是unique,这里可以可能有重复的num
#include <vector>
#include <unordered_set>
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<int>> twoSum(vector<int>& nums, int target) {
vector<vector<int>> res;
unordered_set<int> m;
for (auto& n: nums) {
if (m.count(n)) continue;
if (m.count(target-n)) res.push_back({n, target-n});
m.insert(n);
}
return res;
}
};
int main() {
vector<int> nums = {1,1,2,3,4,5,6,6,7,7,7,7,7};
Solution s;
vector<vector<int>> res = s.twoSum(nums, 8);
for (auto& a: res) cout << a[0] << " " << a[1] << endl;
return 0;
}
P48（4）美国大叔，面不善不恶，不健谈 why yelp ? 问了四遍啊！！！ 谈project， 谈细节，谈优化，谈设想 问了一个蛮蠢的问题，过一个文件，打其中一行，求复杂度？我很莫名，说过一遍是O(n), 打一行是O(1)。大叔居然执着地问一句：所以总共的复杂度是？丫的看不起我个子矮呢
coding 1 给个文件，读一遍以后把每行以 string 形式存在 array 中，随机打出所有 coding 2: 给个文件，能 O(1) 返回文件长度，以及某个位置的数据，要求随机打出一行。 这题就是用文件长度随机定点，然后移动坐标找到 '\n' 也就是前一行的行末，打到本行的行末。 缺陷呢？每行长短不同会引起被选中的概率不同。 好处呢？时间空间复杂度都低
最后一个问题读文件的时候同时更新总行数，最后通过总行数去取随机行就不会因为每一行长短影响概率啦。
所以这部分很快跳过了，然后用随即定位，再打出本行那个就不占空间，但是概率不平均
file = open(filename, "rb", 0)
# Read in the file once and build a list of line offsets
line_offset = []
offset = 0
for line in file:
line_offset.append(offset)
offset += len(line)
file.seek(0)
# Now, to skip to line n (with the first line being line 0), just do
file.seek(line_offset[n])
c++ I know the following:
1) seekg method actually moves the file pointer. The g stands for “get” so it moves the get pointer. It takes two arguments. The first parameter is an offset that determines how many bytes to move the file pointer. The second parameter is an ios flag that specifies what the offset parameter should be offset from.
2) tellg() get the position of the get pointer and tellp() gets the position of the put pointer. So tellg() is the place where you read in the file.
Given that knowledge, I have the following line of code:
Link P49 第一轮. 美国小哥，先自我介绍一下，然后要我选择一个project，假定给一个非CS的朋友讲一下，还问了word count怎么用mapreduce实现，接下来就是coding了 给一个map， 里面包含了{"Monday" : 200 - 300, 500 - 700, 300 - 500, "Tuesday", 300 - 500, 700 - 900 ......}, 把value里面重叠的部分合并，仍然输出一个map
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
class Solution {
public:
unordered_map<string,vector<vector<int>>> mergeTime(unordered_map<string,vector<vector<int>>>& days) {
for (auto& d: days) {
days[d.first] = mergeIntervals(d.second);
}
return days;
}
vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.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;
for (auto& a: intervals) {
if (res.empty() || a[0] > res.back()[1]) res.push_back(a);
else {
res.back()[1] = max(res.back()[1], a[1]);
}
}
return res;
}
};
int main() {
unordered_map<string,vector<vector<int>>> nums = {
{"Monday",{{200,300},{500,700},{300,500}}},
{"Tuesday",{{300,500},{700,900}}}
};
Solution s;
for (auto& a: s.mergeTime(nums)) {
cout << a.first << " ";
for (auto& b: a.second) {
cout << ", {" << b[0] << "," << b[1] << "}";
}
cout << endl;
}
return 0;
}
P50 第二轮. 亚裔小哥， 先自我介绍，简单聊了一下project，然后就是coding，给一个任意的binary tree， encode成string，再decode成tree
297 Serialize and Deserialize Binary Tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (!root) return "#";
return to_string(root->val)+" "+serialize(root->left)+" "+serialize(root->right);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
return buildtree(data);
}
TreeNode* buildtree(string& s) {
if (s[0] == '#') {
if (s.size() > 1) s = s.substr(2);
return NULL;
}
TreeNode* node = new TreeNode(helper(s));
node->left = buildtree(s);
node->right = buildtree(s);
return node;
}
int helper(string& s) {
int pos = s.find(' ');
int val = stoi(s.substr(0,pos));
s = s.substr(pos+1);
return val;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (!root) return "#";
// pre-order traverse
return to_string(root->val)+" "+serialize(root->left)+" "+serialize(root->right);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
istringstream in(data);
return deserialize(in);
}
private:
TreeNode* deserialize(istringstream &in) {
string val;
in >> val;
if (val == "#") return NULL;
TreeNode* node = new TreeNode(stoi(val));
node->left = deserialize(in);
node->right = deserialize(in);
return node;
}
};