Yelp Onsite 61-70
小弟在此奉上yelp on-site面經 攢攢人品先說yelp很喜歡 聊天問之前的project 因為我mapreduce, sql db, nosql db的經驗比較多, 所以他們一直問我之前的項目, 還有這些東西的相關知識 所以做題時間都不多, 一輪大概就一道coding題
P61 1. 是一個白人可愛的正妹, 先是一些知識性問題.
i. Difference between SQL v.s NoSQL, when to use each one? what is SQL’s index? ii. What is load balancer, why we need it? how to detect load balancer really work? iii. 接著要我實作Implement load balancer, 他給的code是c++, 包含幾個送資料給後端servers的function call, 會返回ok, busy, or offline(server 掛了), 我們必須根據這個去implement load balancer的mechanism, 當然這有很多種做法, 就是一陣討論跟分析
Load balancer有一下。具体怎么做，到时候具体分析吧。 Round Robin – Requests are distributed across the group of servers sequentially. Least Connections – A new request is sent to the server with the fewest current connections to clients. The relative computing capacity of each server is factored into determining which one has the least connections. IP Hash – The IP address of the client is used to determine which server receives the request.
P62 2. 一個臉很臭的白人manager, 感覺不大喜歡我, i. 先是一堆behavior 問題 previous project’s big challenge, and have you ever made wrong decision and how did you solve it, and have you ever disagreed with you team members’ idea and how did you solve it.
ii. coding question, Implement a package manager (topological sort)
Input :
{ p1 : {p2, p3},
p2 : {p3},
p3 : {}
}
p1 package is depend on p2, p3, and p2 package is depend on p3, and so on
Output :
Any valid installation order p3, p2, p1
估計就掛在他這, 這題一開始沒想到是topological sort, 卡了一下, 出了點小bug.
你看嘛，这些厂就是喜欢变着法子考toposort。
version 1: DFS
#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
class Solution {
bool dfs(unordered_map<string,vector<string>>& neigh, unordered_map<string,int>& visited,
string p, vector<string>& res) {
if (visited[p] == -1) return false; // cycle
if (visited[p] == 1) return true;
visited[p] = -1;
for (auto& n: neigh[p]) {
if (!dfs(neigh, visited, n, res)) return false;
}
visited[p] = 1;
res.push_back(p);
return true;
}
public:
vector<string> schedule(unordered_map<string,vector<string>>& package) {
unordered_map<string,int> visited;
unordered_map<string,vector<string>> neigh;
for (auto& a: package) {
visited[a.first] = 0;
for (auto& b: a.second) {
neigh[b].push_back(a.first);
}
}
vector<string> res;
for (auto& a: visited) {
// detect a cycle
if (!dfs(neigh, visited, a.first, res)) return {};
}
return vector<string>(res.rbegin(), res.rend());
}
};
int main() {
unordered_map<string,vector<string>> package = {
{"p1",{"p2", "p3"}},
{"p2",{"p3"}},
{"p3",{}}
};
Solution sol;
for (auto& p: sol.schedule(package)) cout << p << " ";
cout << endl;
return 0;
}
version 2: BFS
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <iostream>
using namespace std;
class Solution {
public:
vector<string> schedule(unordered_map<string,vector<string>>& package) {
unordered_map<string,int> in;
unordered_map<string,vector<string>> neigh;
queue<string> q;
for (auto& a: package) {
in[a.first] = a.second.size();
for (auto& b: a.second) {
neigh[b].push_back(a.first);
}
if (in[a.first] == 0) q.push(a.first);
}
vector<string> res;
while (!q.empty()) {
string pack = q.front(); q.pop();
res.push_back(pack);
for (auto& a: neigh[pack]) {
if (--in[a] == 0) q.push(a);
}
}
return res;
}
};
int main() {
unordered_map<string,vector<string>> package = {
{"p1",{"p2", "p3"}},
{"p2",{"p3"}},
{"p3",{}}
};
Solution sol;
for (auto& p: sol.schedule(package)) cout << p << " ";
cout << endl;
return 0;
}
P63 3. 也是一個白人妹子, 這一輪水過 i. Difference between process and thread ii. Ask me about my intern project iii. Add two big integers (follow up: support any base(各種進制) for many numbers’ sum up)
class Solution {
public:
string addStrings(string num1, string num2) {
string res;
int n1 = num1.size()-1, n2 = num2.size()-1;
int carrier = 0;
while (n1 >= 0 || n2 >= 0) {
if (n1 >= 0) carrier += num1[n1--]-'0';
if (n2 >= 0) carrier += num2[n2--]-'0';
res = to_string(carrier%10)+res;
carrier /= 10;
}
return carrier ? "1"+res:res;
}
};
P64 4. 一個叫duncan的, 人很有趣 i. What is MapReduce? ii. 問我雲計算的項目, 像是如何設計hbase的schema iii. Anagrams (Leetcode), can also be done by MapReduce.
class Solution {
void strSort(string& s) {
int count[26] = {0}, n = s.size();
for (int i = 0; i < n; ++i) ++count[s[i]-'a'];
int p = 0;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < count[i]; ++j) {
s[p++] = 'a'+i;
}
}
}
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> m;
for (string& s: strs) {
string tmp = s;
strSort(tmp);
m[tmp].push_back(s);
}
vector<vector<string>> res;
for (auto& a: m) res.push_back(a.second);
return res;
}
};
其實他們家題不難, 但是據說不少人答得好都被拒, 大家good luck
link 本来想在店面贴补充 结果字数超了 重开吧 店面贴Yelp店面面经 onsite攒RP onsite 面的是infrastructure team
coding题: leetcode anagram
P65 leetcode sort version number的一个变种
class Solution {
public:
int compareVersion(string version1, string version2) {
int n1 = version1.size(), n2 = version2.size();
int i = 0, j = 0, d1 = 0, d2 = 0;
while (i < n1 || j < n2) {
while (i < n1 && version1[i] != '.') {
d1 = d1 * 10 + version1[i++] - '0';
}
while (j < n2 && version2[j] != '.') {
d2 = d2 * 10 + version2[j++] - '0';
}
if (d1 > d2) return 1;
else if (d1 < d2) return -1;
d1 = d2 = 0;
++i; ++j;
}
return 0;
}
};
class Solution {
public:
int compareVersion(string version1, string version2) {
istringstream v1(version1 + "."), v2(version2 + ".");
int d1 = 0, d2 = 0;
char dot = '.';
while (v1 || v2) {
if (v1) v1 >> d1 >> dot;
if (v2) v2 >> d2 >> dot;
if (d1 > d2) return 1;
if (d1 < d2) return -1;
d1 = d2 = 0;
}
return 0;
}
};
P66 用随机方法(monte carlo)求Pi 怎么用mapreduce实现 (hadoop自带的example有)
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
const int MAX_TIMES = 2000000; // sample nunmber
srand(time(0));
int inside = 0;
for(int i = 0; i < MAX_TIMES; ++i) {
double x = (double)(rand())/ RAND_MAX;
double y = (double)(rand())/RAND_MAX;
if(x * x + y * y <= 1.0) ++inside;
// if(i % (MAX_TIMES / 100) == 0) cout << '.';
}
double pi = 4.0 * inside / MAX_TIMES;
cout << "/nPI = " << pi << endl;
return 0;
}
P67 给n个unique整数 实现一个iterator 每次next()返回从中随机抽取的k个不同的整数 不要求实现hasNext
如果是不重复的数字的话，返回res前 需要把随机到的int给delete掉。正常的delete是O(n)的。但是我们如果把需要delete的数字跟最后一个数字swap的话，那么这个delete就是O（1）的。科科
#include <vector>
#include <cstdlib>
#include <iostream>
using namespace std;
class randomGetK {
public:
randomGetK(int nin, int kin): n(nin), k(kin) {
for (int i = 0; i < n; ++i) nums.push_back(i);
}
vector<int> get() {
if (n <= k) { // return all in the array
int tmp = n; n = 0;
return vector<int>(nums.begin(), nums.begin()+tmp);
}
// random get k numbers from the array
vector<int> res;
for (int i = 0; i < k; ++i) {
int tmp = rand()%n; --n;
res.push_back(nums[tmp]);
swap(nums[tmp], nums[n]);
}
return res;
}
bool hasNext() {
return n > 0;
}
private:
int n, k;
vector<int> nums;
};
int main() {
randomGetK sol(10,1);
while (sol.hasNext()) {
for (auto& a: sol.get()) {
cout << a << " ";
}
cout << endl;
}
return 0;
}
系统设计和基础知识 设计一个load balancer 解释一个页面请求的全过程 解释java的垃圾回收机制 其他记不得了。。。
他家真心挺好的 挺想去的 比较geek那种 给的包裹也不差的 base比FLG高 后来出于其他因素 选了别家 但是真心推荐大家去面 bar略低于flg 性价比不错
昨天onsite，今天一大早就收到email挂了。。。我这是表现的有多差啊，都不需要讨论一下呵呵
P68 1, 白人大叔 谈project, 谈怎么改进yelp之类。 coding 题：算两个文本的cosin similarity
class Solution {
public:
/**
* @param A: An integer array.
* @param B: An integer array.
* @return: Cosine similarity.
*/
double cosineSimilarity(vector<int> A, vector<int> B) {
// write your code here
int AB = 0, n = A.size();
double normA = 0, normB = 0;
for (int i = 0; i < n; ++i) {
AB += A[i]*B[i];
normA += A[i]*A[i];
normB += B[i]*B[i];
}
if (normA == 0 || normB == 0) return 2.0;
return AB/(sqrt(normA)*sqrt(normB));
}
};
p69 2, 国人 问project，全程板个脸 一个dp, 不过写完有个bug Given a set of currency denominations, find the minimum number of coins needed to represent an amount. Return 0 if you can't use your coins to represent the target amount. For example: Suppose you have two kinds of coins: 1, 2. In order to represent 3, you have two options: 1 + 1 + 1 = 3 or 1 + 2 = 3 So the minimum number of coins is 2.
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int& a: coins) {
if (i >= a && dp[i-a] != INT_MAX) dp[i] = min(dp[i], dp[i-a]+1);
}
}
return dp[amount] == INT_MAX ? -1:dp[amount];
}
};
P70 ３，烙印女manager 问project lc Search a 2D Matrix II binary search, 就是每次扔掉1/4数据。然后她说这不是最优解。。。说复杂度还是$$n^2$$（应该是$$O(n)$$吧，如果是$$n*n$$的矩阵） 哪个大牛能说说还有什么更好的解法？
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;
}
};