Yelp Onsite 71-80
P71 ４，白男 概率题，我的最恨！提示下写出来了。 然后是给４个点的坐标，判断能否构成一个正方形。正方形与坐标轴不一定平行。
面完感觉就不太好，虽然题都做出来了。 没想到这么快啊。。。move on吧
def S(A):c=sum(A)/4.0;return set(A)==set((A[0]-c)*1j**i+c for i in range(4))
#include <iostream>
#include <algorithm>
using namespace std;
struct Point {
double x, y;
Point(double x_, double y_) : x(x_), y(y_) {}
};
// the square of each distance
int dist(Point& a, Point& b) {
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool isSquare(const vector<Point>& points) {
// ...
Point A = points[0], B = points[1], C = points[2], D = points[3];
int AB = dist(A,B), AC = dist(A,C), AD = dist(A,D);
int BC = dist(B,C), BD = dist(B,D), CD = dist(C,D);
vector<int> edges({AB, AC, AD, BC, BD, CD});
sort(edges.begin(), edges.end());
// AB^2 + BC^2 == AC^2
if (2*edges[0] != edges[5]) return false;
for (int i = 0; i < 3; ++i) {
if (edges[i] != edges[i+1]) return false;
}
if (edges[4] != edges[5]) return false;
return true;
}
int main() {
vector<Point> points = {Point(0,0),Point(0,1),Point(1,1),Point(1,0)};
cout << isSquare(points) << endl;
vector<Point> points2 = {Point(1,0),Point(0,1),Point(1,1),Point(1,0)};
cout << isSquare(points2) << endl;
}
第二问 是 return 四个点围成的形状:
"rectangle", "square", "diamond", “parallelogram",. ...
一开始閒聊花太长时间了 最后没有写完
好像不用那么复杂，四个点我们可以得到C(4,2) = 6 条边。然后只要看看他们的长度关系就好，要是算角度就麻烦了。
先把6条边sort一下后面代码好写很多：
正方形：四个短边相等，两个长边彼此相等，并且长边刚好等于sqrt(2)*短边
菱形： 同正方形，但是不用符合根号二那个要求
长方形：边的长度两两相等，最长边的平方等于最短边和次短边的平方和
平行四边形： 同长方形，但不用符合平方和那个要求
几何忘的差不多了，大家看看有反例么？
import numpy as np
def damn(x, tol=1e-10):
edges = np.array([x[i] - x[j] for i in range(4) for j in range(i+1,4)])
equal = lambda x,y:np.sum(np.abs(x-y)) < tol
if any([equal(np.cross(edges[i],edges[j]),0) for i,j in zip([0,0,1,3],[1,2,2,4])]): # If cross product between two edges is 0, three points are aligned on the same line
return "Degenerate"
c, diag1, diag2 = (lambda(e):(0,1,2), lambda(e):(1,e[2],e[3]), lambda(e):(1,e[1],e[4]), lambda(e):(1,e[0],e[5]))[(equal(edges[0],edges[5]) or equal(edges[1],edges[4])) + (equal(edges[0],-edges[5])) * 2 + (equal(edges[1],-edges[4])) * 3](edges) # c=0 if not parallelogram
a = np.abs(np.dot(diag1,diag2)) < tol
b = np.abs(np.sum(diag1**2) - np.sum(diag2**2)) < tol
return ("Quadrilateral", "Parallelogram", "Rhombus", "Rectangle", "Square")[c + a + 2*b]
# edges[0]: x1-x2
# edges[1]: x1-x3
# edges[2]: x1-x4
# edges[3]: x2-x3
# edges[4]: x2-x4
# edges[5]: x3-x4
# Test if three points aligned: (x1,x2,x3): test edges 0 and 1; (x1,x2,x4): test 0 and 2; (x1,x3,x4): test 1 and 2; (x2,x3,x4): test 3 and 4
# If parallelogram, find diagonals: Edge 0 = edge 5 OR 1 = 4 -> diag = edges 2&3; 0 = -5 -> diag = 1&4; 1 = -4 -> diag = 0&5
x1 = np.array([0,0,2]); x2 = np.array([2,1,2]); x3 = np.array([0,np.sqrt(5),2]); x4 = np.array([2,1+np.sqrt(5),2])
damn(np.array([x1,x2,x3,x4])) # 'Rhombus'
x1 = np.array([1,2,3]); x2 = np.array([4,5,6]); x3 = np.array([2,3,1]); x4 = np.array([5,6,4])
damn(np.array([x1,x2,x3,x4])) # 'Rectangle'
x1 = np.array([1,2,3]); x4 = np.array([4,5,6]); x2 = x1 + np.array([1,1,-2])*np.sqrt(4.5); x3 = x4 + x2 - x1
damn(np.array([x1,x2,x3,x4])) # 'Square'
x1 = np.array([1,2,3]); x4 = np.array([4,5,6]); x2 = x1 + np.array([1,1,2])*np.sqrt(4.5); x3 = x4 + x2 - x1
damn(np.array([x1,x2,x3,x4])) # 'Rhombus'
x1 = np.array([1,2,3]); x4 = np.array([4,5,6]); x2 = x1 + np.array([1,1,2]); x3 = x4 + x2 - x1
damn(np.array([x1,x2,x3,x4])) # 'Parallelogram'
x1 = np.array([0,1,2]); x2 = np.array([1,3,5]); x3 = np.array([1,3,5]); x4 = np.array([3,7,11])
damn(np.array([x1,x2,x3,x4])) # 'Degenerate'
#### Easy version
import numpy as np
def damn(x, tol=1e-10):
edges = np.array([x[i] - x[j] for i in range(4) for j in range(i+1,4)])
equal = lambda x,y:np.sum(np.abs(x-y)) < tol
if any([equal(np.cross(edges[i],edges[j]),0) for i,j in zip([0,0,1,3],[1,2,2,4])]): # If cross product between two edges is 0, three points are aligned on the same line
return "Degenerate"
if equal(edges[0], edges[5]) or equal(edges[1],edges[4]):
diag1, diag2 = edges[2], edges[3]
elif equal(edges[0], -edges[5]):
diag1, diag2 = edges[1], edges[4]
elif equal(edges[1], -edges[4]):
diag1, diag2 = edges[0], edges[5]
else:
return "Quadrilateral"
a = np.abs(np.dot(diag1,diag2)) < tol
b = np.abs(np.sum(diag1**2) - np.sum(diag2**2)) < tol
return ("Parallelogram", "Rhombus", "Rectangle", "Square")[a + 2*b]
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
struct Point {
double x, y;
Point(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}
Point operator-() {
return Point(-x, -y);
}
};
bool operator==(Point a, Point b) {
return a.x == b.x && a.y == b.y;
}
int dot(Point& a, Point& b) {
return a.x*b.x+a.y*b.y;
}
// the square of each distance
int dist(Point& a, Point& b) {
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
/*
the slopes between point 1 and point 2 and point 1 and point 3 are the same
y1 - y2 y1 - y3
------- = --------
x1 - x2 x1 - x3
*/
bool collinear(Point& p1, Point& p2, Point& p3) {
return (p1.y - p2.y) * (p1.x - p3.x) == (p1.y - p3.y) * (p1.x - p2.x);
}
class Solution {
public:
string checkShape(vector<Point>& points) {
vector<Point> edges;
for (int i = 0; i < 4; ++i) {
for (int j = i+1; j < 4; ++j) {
edges.push_back(Point(points[i].x-points[j].x, points[i].y-points[j].y));
}
}
// If cross product between two edges is 0, three points are aligned on the same line
if (collinear(points[1], points[2], points[3])) return "Degenerate";
if (collinear(points[0], points[2], points[3])) return "Degenerate";
if (collinear(points[0], points[1], points[3])) return "Degenerate";
if (collinear(points[0], points[1], points[2])) return "Degenerate";
/*
# edges[0]: x1-x2
# edges[1]: x1-x3
# edges[2]: x1-x4
# edges[3]: x2-x3
# edges[4]: x2-x4
# edges[5]: x3-x4
# Test if three points aligned: (x1,x2,x3): test edges 0 and 1; (x1,x2,x4): test 0 and 2; (x1,x3,x4): test 1 and 2; (x2,x3,x4): test 3 and 4
# If parallelogram, find diagonals: Edge 0 = edge 5 OR 1 = 4 -> diag = edges 2&3; 0 = -5 -> diag = 1&4; 1 = -4 -> diag = 0&5
*/
Point diag1, diag2;
if (edges[0] == edges[5] || edges[1] == edges[4]) {
diag1 = edges[2], diag2 = edges[3];
} else if (edges[0] == -edges[5]) {
diag1 = edges[1], diag2 = edges[4];
} else if (edges[1] == -edges[4]) {
diag1 = edges[0], diag2 = edges[5];
} else return "Quadrilateral";
bool isPerp = (dot(diag1, diag2) == 0);
Point orign;
bool isEqual = (dist(diag1,orign) == dist(diag2,orign));
return v[isPerp+2*isEqual];
}
private:
vector<string> v = {"Parallelogram", "Rhombus", "Rectangle", "Square"};
};
int main() {
Solution sol;
vector<Point> points = {Point(0,0),Point(0,1),Point(1,1),Point(1,0)};
cout << sol.checkShape(points) << endl;
vector<Point> points2 = {Point(1,0),Point(0,0),Point(0,1),Point(1,0)};
cout << sol.checkShape(points2) << endl;
}
Coding:
P72 1. 写一个Iterator的类，实现Iterator相加，比如[1,2] + [0] -> [1,2,0]
P73 2. Word Ladder II
class Solution {
void dfs(unordered_map<string,vector<string>>& next, string& end, string prev, vector<string>& path, vector<vector<string>>& res) {
if (prev == end) { res.push_back(path); return;}
for (auto& cur: next[prev]) {
path.push_back(cur);
dfs(next, end, cur, path, res);
path.pop_back();
}
}
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict;
for (auto& w: wordList) dict.insert(w);
if (!dict.count(endWord)) return {};
unordered_map<string,vector<string>> next; // Neighbors for every node
unordered_map<string,int> dist; // Distance of every node from the start node
queue<string> q; q.push(beginWord);
dist[beginWord] = 0;
int n = beginWord.size();
while (!q.empty()) {
int cnt = q.size();
bool foundEnd = false;
for (int i = 0; i < cnt; ++i) { // curlevel
string curWord = q.front(); q.pop();
int curStep = dist[curWord]+1;
dict.erase(curWord);
bool foundEndwithCurWord = false;
for (int j = 0; j < n; ++j) {
string newWord = curWord;
for (char c = 'a'; c <= 'z'; ++c) {
newWord[j] = c;
if (dict.count(newWord)) {
if (!dist.count(newWord) || dist[newWord] == curStep)
next[curWord].push_back(newWord);
// found end -> shortest path, no need to loop the rest
if (curWord == endWord) {
foundEndwithCurWord = true;
foundEnd = true;
next[curWord] = {endWord};
break;
}
if (!dist.count(newWord)) { // internal node: Check if visited
dist[newWord] = curStep;
q.push(newWord);
}
}
}
if (foundEndwithCurWord) break;
}
}
if (foundEnd) break;
}
/*
for (auto& a: next) {
cout << a.first << ": ";
for (auto& b: a.second) {
cout << b << ", ";
}
cout << endl;
}*/
vector<vector<string>> res;
vector<string> path = {beginWord};
dfs(next, endWord, beginWord, path, res);
return res;
}
};
version 1: BFS
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_map<string, int> m;
for (string& w: wordList) m[w] = 0;
queue<string> q;
q.push(beginWord);
m[beginWord] = 1;
while (!q.empty()) {
string word = q.front(); q.pop();
if (word == endWord) return m[word];
for (int i = 0; i < word.size(); ++i) {
string newWord = word;
for (char c = 'a'; c <= 'z'; ++c) {
newWord[i] = c;
// new word exists and unvisited
if (m.count(newWord) && m[newWord] == 0) {
m[newWord] = m[word]+1;
q.push(newWord);
}
}
}
}
return 0;
}
};
version 2: 2end BFS
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict, begSet, endSet, *set1, *set2;
for (auto& w: wordList) dict.insert(w);
begSet.insert(beginWord);
endSet.insert(endWord);
if (!dict.count(endWord)) return 0;
int dist = 2;
while (!begSet.empty() && !endSet.empty()) {
if (begSet.size() <= endSet.size()) {
set1 = &begSet, set2 = &endSet;
} else {
set2 = &begSet, set1 = &endSet;
}
unordered_set<string> tmp;
for (auto it = set1->begin(); it != set1->end();it++) {
string w = *it;
for (int i = 0; i < w.size(); ++i) {
char letter = w[i];
for (char c = 'a'; c <= 'z'; ++c) {
w[i] = c;
if (set2->count(w)) return dist;
if (dict.count(w)) {
tmp.insert(w); dict.erase(w);
}
}
w[i] = letter;
}
}
++dist;
swap(*set1, tmp);
}
return 0;
}
};
P74 3. Anagrams, 跟leetcode上不同的是，输入的string长度不一定一样。LZ用hashmap做，给了O(n klogk)的解法，之后优化成O(nk);
P75 4. Yelp给个business_id，比如3Ed2fU。但是有的时候会被parse成全部小写，这样会导致返回一个无效link。问题是怎么根据给的link，返回所有可能的link。讲白了就是dfs把每个小写字母换成大写字母，看看有多少组合（2^n）;
Follow up, 假设找到了一堆合理的link，怎么知道哪个是user想要的？根据ip address返回user附近的business_id，也可以根据user的历史记录返回。
常识题：
- browser输入一个url后发生什么？
- 怎么优化网页loading速度？
- MySQL vs Mongo?
- iframe advantage vs disadvantage
- 假设向server发送请求只有90会成功，怎么提高成功率？
Yelp是python base的。
lc tag 题目
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> m;
for (int& i:nums) ++m[i];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // minheap
for (auto& a:m) {
pq.push({a.second, a.first});
if (pq.size() > k) pq.pop();
}
vector<int> res;
while (!pq.empty()) {
res.push_back(pq.top().second);
pq.pop();
}
return res;
}
};
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int,int>> lines;
for (auto&a: buildings) {
lines.push_back({a[0], -a[2]});
lines.push_back({a[1], a[2]});
}
sort(lines.begin(), lines.end());
int preheight = 0, curheight = 0;
multiset<int> heights; heights.insert(0);
vector<pair<int, int>> res;
for (auto& a: lines) {
if (a.second < 0) heights.insert(-a.second);
else heights.erase(heights.find(a.second));
curheight = *heights.rbegin();
if (curheight != preheight) {
res.push_back({a.first, curheight});
preheight = curheight;
}
}
return res;
}
};
151. Reverse Words in a String
class Solution {
public:
void reverseWords(string &s) {
istringstream is(s);
stack<string> st;
string tmp, res;
while (is >> tmp) st.push(tmp);
s.clear();
while (!st.empty()) {
s += st.top()+' ';
st.pop();
}
s.pop_back();
}
};
class Solution {
public:
void reverseWords(string &s) {
int n = s.size(), idx = 0;
reverse(s.begin(), s.end());
for (int i = 0; i < n; ++i) {
if (s[i] != ' ') {
if (idx != 0) s[idx++] = ' ';
int j = i;
while (i < n && s[i] != ' ') s[idx++] = s[i++];
reverse(s.begin()+idx-(i-j), s.begin()+idx);
// cout << s << endl;
}
}
s.resize(idx);
}
};
不考虑不规范的情况
class Solution {
public:
void reverseWords(string &s) {
reverse(s.begin(), s.end());
cout << s << endl;
int n = s.size(), l = 0;
for (int i = 0; i < n; ++i) {
while (i < n && s[i] != ' ') ++i;
reverse(s.begin()+l, s.begin()+i);
l = i+1;
}
}
};