给一堆interval，一个target（float），此api会被多次
第一问，问target有没有被cover到
按起点sort，然后mege。每次api都2分查找
第二问，target被几个interval cover
把原interval数组按起点排序，遇到overlap的，split重新构造interval，加入count
1…3 2…5 --> 1…2 2…3 3…5, 每个interval都有对应的count，然后2分查找
interval都要先预处理
-----------------------------------------------------------------
REF: http://www.mitbbs.com/article_t/JobHunting/33021975.html
听起来像是欧洲人，accent听起来有点吃力，先上题目：
1.leetcode上原题 number of islands
LC
2.follow up：count rank 2 islands, where a rank 2 island is an island inside
a lake located on a continent. A continent is a piece of land located in
the ocean; the ocean is any body of water that touches the edges of the map.
Example:
000000000
000001100
001111100
011000100
001010100
001000100
001111100
000000000
上面这个例子里应该返回1.
从4个边开始走，将所有连接的0染色，标为A，1染色，标为B。
从A继续走，找到相连接的1，染成C。
从C继续有，找到相连接的0，染成D
从D开始走，开始数岛的个数，返回
3.If the input 2d array is too large to fit in memory, how to handle?
我从第二个follow up开始就回答的磕磕绊绊，最后也没写code，一直在跟面试官讨论
。后来思路终于讨论出来了，但第二个follow up面试官提示说water的那个dfs和第一
问里的dfs有什么不同，后来明白他想说water的dfs要考虑对角线情况。第三个follow
up更是不知道怎么回答，瞎扯了一通。
请教各位大侠们，第三问该怎么考虑？
------------------------------------------------------------------------
REF: http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid=33030297&ftype=0
producer / consumer 问题， 要求threadsafe, high throughput
https://en.wikipedia.org/wiki/Monitor_(synchronization)
如何提高满足high throughput？
lock free queue: https://github.com/fat-lobyte/atomic_queue
Mutex m;
queue<Message> que;
CV Full;
CV Empty;
void producer(Message msg) {
m.requireLock();
while (que.full()) {
wait(m,Full);
}
que.push(msg);
signify(Empty);
m.releaseLock();
}
Message consumer() {
m.requireLock();
while (que.empty()) {
wait(m,Empty);
}
Message msg = que.front();
que.pop();
signify(Full);
m.releaseLock();
return msg;
}
----------------------------------------------------------
REF: http://www.mitbbs.com/article_t/JobHunting/32939573.html
第一题merge n sorted list. 我用heap做,比较容易.
第二题
题目弄了半天大概搞清楚意思, 但是没做出来. 大家出来看一下怎么做.
有一个lock, 比如说1234
假设你要解锁, 你要尝试所有的combination来解锁, 怎么把这所有的combination存在
一个sequence里面使得sequence最短.
比如说锁只能是 0 1 2 组成的数字
锁是 1
012
锁是 12
sequence 可以是
000102101112202122
代表
00 01 02 10 11 12 20 21 22
也可以是, 如果你连着读的话
0011022120
可以代表
00
01
11
10
02
22
21
12
20
我觉得是怎么压缩这些candidate key到一个string里面
最优解巨难：
https://en.wikipedia.org/wiki/De_Bruijn_sequence
普通解：dfs + backtrack，map记录出现过的密码，一个全部变量记录最短sequence
----------------------------------------------------------------------------------
ref: http://www.mitbbs.com/article_t/JobHunting/33031045.html
Given a tree string expression in balanced parenthesis format:
(A(B(C)(D))(E)(F))
A
/ | \
B E F
/ \
C D
Return the corresponding tree (ie the root node). You can assume that the input is valid.
iterative的写法
struct TreeNode{
char val;
vector<TreeNode*> children;
TreeNode(char val) {
this->val = val;
}
};
TreeNode *buildTree(string s) {
stack<TreeNode *> st;
TreeNode *root = NULL;
for (int i = 0; i < s.length(); i++) {
if (s[i] >= 'A' && s[i] <= 'Z') {
TreeNode *node = new TreeNode(s[i]);
st.push(node);
}else if (s[i] == ')') {
TreeNode *cur = st.top();
st.pop();
if (st.empty()) root = cur;
else (st.top())->children.push_back(cur);
}
}
return root;
}
另一种方法：类似level order traversal的DFS解法，但这里是iterative。
vector里存的是每一层的最后一个node，碰到‘（’， level + 1， 如果是‘）’，level - 1，
TreeNode *buildTree(string s) {
vector<TreeNode *> ends;
int level = 0;
TreeNode *dummy = new TreeNode('d');
ends.push_back(dummy);
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
level++;
}else if (s[i] == ')') {
level--;
}else {
TreeNode *node = new TreeNode(s[i]);
if (level >= ends.size()) {
ends.push_back(node);
}else {
ends[level] = node;
}
ends[level - 1]->children.push_back(node);
}
}
return ends[1];
}
---------------------------------------------------------------------REF: http://www.mitbbs.com/article_t/JobHunting/32907123.html
1. Binary Search Tree, right next() function on each node
还有一个follow up question想不起来了
LC
2. Leetcode , merge interval 变种
find mean in two sorted list with same length
O(n) 扫一边
如果题目是find median in two sorted array with same length
http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
double helper(vector<int> &v1,vector<int> &v2,int s1,int e1,int s2,int e2) {
if (s1 == e1) return (v1[s1] + v2[s2]) / 2.0;
int mid1 = (s1 + e1) / 2, mid2 = (s2 + e2) / 2;
if (v1[mid1] == v2[mid2]) {
return double(v1[mid1]);
}
if (e1 - s1 == 1) {
return (max(v1[s1],v2[s2]) + min(v1[e1],v2[e2])) / 2.0;
}
if (v1[mid1] < v2[mid2]) {
return helper(v1,v2,mid1,e1,s2,mid2);
}else {
return helper(v1,v2,s1,mid1,mid2,e2);
}
}
double findMedian(vector<int> &v1,vector<int> &v2) {
return helper(v1,v2,0,v1.size() - 1,0,v2.size() - 1);
}
一个Design问题
3. 基本都是design的问题，design google recommendation
4. 设计/测试replicate cache的方法
5. 一个martrix，每行每列都是sorted，找到前kth 个
http://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise-and-column-wise-sorted-2d-array-set-1/
算法吊炸天！
#1 用一个大小为n的heap，初始存入第一行所有的值以及他们的row，col
#2 做一个长度为k的循环
每次弹出最小的值，之后压入被取出值的在同一列的下一个值
#3 heap里保存的是每一列的最小值，而且每次弹出的值是当前全局的最小值。所以k次之后出现的就是第k小的值
前四轮感觉都还可以，最后一轮是烙印，比较疲惫了，老觉得有一个什么最优解，后来
查了一下基本就是merge multiple sorted list的思路，做题的时候钻了牛角尖，老觉
得还有一个更好的解法。
---------------------------------------------------------
ref: http://www.mitbbs.com/article_t/JobHunting/33032299.html
一个matrix，每个matrix[i][j]有一个价格，给你一个budget，问如何求出最大面积的
子矩阵，使得子矩阵的价格之和不超过budget
没有想到特别好的解法
方法1：O(n^4), 枚举所有i, j为矩形的左右2列的矩阵
方法2：方法1的改进， O(n^3)
参考：http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/
int kardane(vector<int> &temp) {
int sum = temp[0];
int curSum = temp[0];
for (int i = 1; i < temp.size(); i++) {
curSum = max(temp[i],curSum + temp[i]);
sum = max(curSum,sum);
}
return sum;
}
int maxRectangles(vector<vector<int>> &matrix) {
int m = matrix.size(), n = matrix[0].size();
int largest = INT_MIN;
vector<int> temp(m,0);
for (int i = 0; i < n; i++) {
vector<int> temp(m,0);
for (int j = i; j < n; j++) {
for (int row = 0; row < m; row++) {
temp[row] += matrix[row][j];
}
largest = max(largest,kardane(temp));
}
}
return largest;
}
---------------------------------------------------------------------------
ref: http://www.mitbbs.com/article_t/JobHunting/32617501.html
跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
头上。问最少几步可以跳完整条河流。
给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
第一步先提速到2，再跳到R[2]；
第二步先提速到3，再跳到R[5]；
第三步保持速度3，跳出数组范围，成功过河。
假设有一方法 foo(int index，int speed) 返回从[index : ] 所需的最小步数
则：foo(index,speed) = 1 + min(foo(index + speed, speed), foo(index + speed + 1, speed + 1))
一些constraint：index需要为1，index + speed或+ 1也需要为1， index + speed + 1 < n
DP可解，O(N^2)
听说有更优解
听说有更优解
int crossRiver(vector<int> &river) {
int n = river.size();
vector<vector<int>> dp(n,vector<int>(n,1));
for (int i = n - 1; i >= 0; i--) {
if (river[i] == 0) continue;
for (int j = 1; j <= n; j++) {
if (i + j + 1 < n) {
if (river[i + j] == 0 && river[i + j + 1] == 0) {
dp[i][j] = INT_MAX;
}else if (dp[i + j][j] != INT_MAX && dp[i + j + 1][j + 1] != INT_MAX) {
dp[i][j] = 1 + min(dp[i + j][j],dp[i + j + 1][j + 1]);
}else if (dp[i + j][j] != INT_MAX) {
dp[i][j] = dp[i + j][j] + 1;
}else {
dp[i][j] = dp[i + j + 1][j + 1] + 1;
}
}
}
}
return dp[0][1];
}
No comments:
Post a Comment