Chapter 66 Pure Storage
66.1 OA
http://www.1point3acres.com/bbs/thread-141842-1-1.html
http://www.1point3acres.com/bbs/thread-109109-1-1.html
http://www.1point3acres.com/bbs/thread-118986-1-1.html
刚刚做完Pure Storage的OA,谢谢论坛上的分享.
基本可以分为两套题库:1) 4A 版,8题版,稍微难点;2)Core 版,12题版,简单.从版上收集了一些信息,并做了一些答案.做一个集合希望对大家有所帮助.
第一次做OA…觉得值得提醒的点有:
0.开始之前要填写一些信息,比如你的recruiter name…注意查看邮箱的发件人.
1.前两道都是编程题,只有第一个可以选C / C++/ Java 7.有没有python没注意… 默认出来的好像是C.选择自己的惯用语言在左上角.倒计时在页面的上方.题目数在左侧.对应按钮可以点进去.
2.每道题都有一个submit and continue的链接.这个点完之后可以修改.
3.可以不用按照顺序做题,哪怕看一眼觉得麻烦可以点后面的题先做.
4.第二题的默认语言是C.无法修改,但是题目思想感觉像是变形版本的2 Sum.但是要求返回满足条件的pair数.题目考得很简单.时间复杂度是\(O(n^2)\)的样子而且两个循环题目已经写好了.改一下循环的条件就可以了. 5.编程题都是已经写了一堆代码初始化过很多东西,甚至也写好了main函数,你只需要run一下就知道了结果.甚至在写完一个.之后会弹出一些方法的提示…有点像IDE… 值得注意的地方是…你只需要写背景色空白的section就行,其他可以无视掉.
6.不少题目都是GRE CS sub里的.有兴趣的同学可以研究一下.
66.1.1 12 Questions
2015(1-3月) 码农类 硕士 全职 Pure Storage - 网上海投 - 在线笔试 |Other
大概一个月前做的Pure Storage的OA,想起来了分享一下面经,攒攒人品.
OA总共有12道题,时间是60分钟,其中第一道是代码题,第二道是代码改错题,剩下的10道都是多选题.
1,代码题:Remove nodes from a LinkedList that have the given value. 这题比较简单,就是给一个LinkedList和一个int值,去掉List里面所有包含这个值的节点.方法就不多说了,相信大家都是闭着眼睛秒杀的.这道题可以用C, C++或者Java做.默认的是Java.这个题是可以在线跑一下的,提交之前可以确保所有test case都通过.
linked-list.html#remove-linked-list-elements
2,代码改错题:给了一段很简单的C代码,说这个代码有错误,要求改正错误.题目大概就是给一个int数组和int diff,要求找到数组中的pair使得a-b=diff. 返回值是所有符合条件的pair的个数.给的有bug的代码也就5行左右,因为默认数组已经被sort过了.虽然是C写的,但没用到C的特性,而且错误很基础,一眼就看出来了.这个只能用C语言改,改完后也可以跑一下确保test case都通过就行了.
多选题:多选题有的稍微有点tricky, 好像很多都是跟GRE CS类似的题目.具体题目如下(具体选项记不清了,望谅解):
3,判断下列哪些小数有确定有限的(exact)二进制表示: A 0.1, B 0.2, C 0.3, D 0.4, E 0.5 这题只要会手动转换十进制到二进制就行了
It should be only 0.5!
00:01 # ./d2b 0.5
0 01111111110 0000000000000000000000000000000000000000000000000000
00:01 # ./d2b 0.4
0 01111111101 1001100110011001100110011001100110011001100110011010
00:01 # ./d2b 0.3
0 01111111101 0011001100110011001100110011001100110011001100110011
00:01 # ./d2b 0.2
0 01111111100 1001100110011001100110011001100110011001100110011010
00:02 # ./d2b 0.1
0 01111111011 10011001100110011001100110011001100110011001100110104,1-1000猜数字,你每次的提问对方只能用yes或no来回答,问最少需要猜多少次才能才出来 用binary search, 每次缩小一半范围
Answer: \(ceil(log(1000)) = 10\)
5,一个singly LinkedList, 给了指向头尾节点的指针,问以下哪个操作的时间复杂度依赖于list的长度(O(n))
Answer: Delete tail
6, 给了一个用array[1….N]和一个int i实现的Stack,并且给了POP和PUSH的伪代码,为应该如何初始化i的值才能保证Stack的实现是正确的
7, 给出word, pairlet, pairdig,letter, digit的产生规则(自动机), 问which of the following entities can be derived form <word>?
这题把每个选项带进去看看是否能符合自动机的规则就行了
8,给出一段关于p,k的代码(还有loop), 问以下哪种p,k之间的关系是在代码执行过程中始终成立的 代码好像是类似于这样的 (伪代码):
p=1,k=0
while (k <n) {
p=2*p;
k=k+1;
}9,给出一段递归的Function(int)代码,问Function(2)的值. 代码记不清楚了,但是很简单,直接代入计算就得出结果
10,给一个网格,其中每个格子有一个pixel值,是0-7中任意一个.然后规定两个相邻网格的差值不能大于2. 考虑两个相邻网格,总共有64种可能情况,问其中多少种情况满足要求. 这题纯粹是个概率计算问题,很简单
11,多线程的题.有个两个线程如下:
Task1: x=1; a=y
Task2: y=1; b=x两个线程的执行顺序是不确定的,问执行完之后a和b可能的结果???
Another version:
有个concurrent的题目 shared varibale x, y initialized with 0, thread A: x = 1; b = y thread B: y = 1, a = x, 问等程学跑完了哪种是对的 我选的是 (A) a == 0 => b == 1 (B) b == 0 => a == 1;
https://www.youtube.com/watch?v=6Sa4sr-EmU8
12,给出一段C#代码,问f(x)的时间复杂度 (which best describes the growth of f(X) as a function of X) 代码大概是这样的:
int f(int x) {
if(x<1) return 1;
else return f(x-1) +g(x/2);
}
int g(int x) {
if(x<2) return 2;
else return f(x-1) + g(x/2);
}把f(x)按照代码展开看看跟x的关系就可以了,要细心想,别弄错了..
Answer: Exponential!!!
Check Exercise 4.4-5 at: http://sites.math.rutgers.edu/~ajl213/CLRS/Ch4.pdf
Verify code:
static int count2=0;
int g(int);
int f(int x) {
count2++;
if(x<1) return 1;
else return f(x-1)+g(x/2);
}
int g(int x) {
if(x<2) return 2;
else return f(x-1) + g(x/2);
}
count2=0;f(10);cout<< count2 << endl;
count2=0;f(20);cout<< count2 << endl;
count2=0;f(40);cout<< count2 << endl;
count2=0;f(80);cout<< count2 << endl;66.2 Image Smoother
http://www.1point3acres.com/bbs/thread-138406-1-1.html
2015(4-6月) 码农类 硕士 全职 Pure Storage - 网上海投 - Onsite |Fail在职跳槽
版上列出过一些题目, 没见过的有:
- 实现不同的iterator, (sorted iterator(给定一个非sort的iterator), filter Iterator (给定一个predicate函数, 和一个iterator)
- 给定一些texbox, 里面有text(text box 的大小, text的相對偏移都給出了), 要求重新排列这些textbox, 这样text可以对齐, 这个讨论完了就是纯粹coding, 没啥特别
- Image smoother, 给定一个matrix, 要求输出一个matrix, 每个cell的值是原来3*3邻居的平均值, 要求in-place
66.3 task dispatch system
http://www.1point3acres.com/bbs/thread-181221-1-1.html
一个从coderpad链接开始…然后非常崩溃的面试过程…
首先上来复制一道题…实现一个callback机制,有Callback 类和Event类.Callback类里有call()方法.Event类里面有两个方法,一个是register_cb(),一个是fire().题目要求是实现regsiter_cb()和fire().找个数据结构把callback对象存进去,然后在某个时间点执行fire().之后再执行registe_cb(), 就不会放进某个数据结构了.我用List存的,应该也能用别的.
首先一上来看到题目非常蒙圈的我…看到这个好像在面经里出现过,但是考虑到复习多线程几天根本来不及…(我觉得涉及到底层的东西是抱佛脚抱不来的…)大概扫了一眼就接着看算法了…
说好的pure number呢…
然后follow up是这个code是线程安全的吗,我觉得不是,然后问我会有什么情况出现…然后他举个例子说有这样这样的情况你的callback会不能被call(),你知道为什么吗.我就说可能是什么什么…他说你知道race condition吗…这是个非常基础的CS知识…(听出了rej的节奏…)
然后我说用synchronized关键字可以加锁…然后他说如果我不用synchronized,给你一个lock类呢.然后lock类有acquire和release…然后怎么用lock…(叫你本科不好好学OS…现在多线程这么弱)
然后时间差不多了…说你有啥问题吗…
(4)MultiThread
http://www.1point3acres.com/bbs/thread-124049-1-1.html
本来以为第二次电面会是多线程的问题,没想到HappyNumber了,比较幸运,但是多线程的这个问题还是准备了很久, 我把当初整理的资料发上来:https://www.evernote.com/shard/s260/sh/a01e5b26-d3eb-44c0-8ef4-01086605f675/da31dd196df57906d67ab4ea189304f1
笔记里有题目的原题截图,后来这个题在我onsite的时候问了,貌似这个体和网上面经里的task dispatch是类似的,相互替代 回答的时候先写简单的单线程的,再写个最简单的给整个函数body加锁的版本
再指出问题在哪儿(当callback是register_cb的时候会导致程序死锁),再针对的改一改代码,时间过去了很久,我就不回忆代码怎么写的了,
大概思路是用一个全局的flag来表征是不是已经trigger过了,用一个Queue来存task,trigger之后也要注意检查Queue的size是不是0,因为多线程的时候可能导致有些callback加到队列的同时,flag被翻转了,如果不检查可能会导致有些callback没有被执行
/*
event_fired()
|
|
------------------------------------------------------------------->time
| | cb1() |
| | cb2() |
reg_cb(cb1) reg_cb(cb2) reg_cb(cb3)
cb3()
*/
// what if cb calls reg_cb()?
/*
void cb99() {
reg_cb(cb101);
}
reg_cb(cb99); ???
*/
atomic<bool> is_fired{false}; // thread-safe
vector<callback_t> v; // thread-safe
mutex m; // m.lock(), m.unlock()
void reg_cb(callback_t cb){ // register_callback
if(!is_fired){
m.lock();
if(!is_fired){
// event_fired() - pause here temp...
v.push_back(cb);
m.unlock();
return;
}
m.unlock();
}
cb.execute(); // reg_cb invoked
}
void event_fired(){
m.lock();
is_fired=true;//
m.unlock();
while(!v.empty()){
v.return_and_remove_back().execute(); // return v[v.size()-1] and remove v[v.size()-1]
}
}http://softwarecareerup.blogspot.com/2015/03/pure-storage-interview.html
66.4 202. Happy Number
https://leetcode.com/problems/happy-number/
struct Solution {
bool isHappy(int n) {
unordered_set<int> si={n};
while(1){
int t=0, x=0;
while(n) x=n%10, t+=x*x, n=n/10;
if(t==1) return true;
if(si.count(t)) return false;
si.insert(t), n=t;
}
return false;
}
};Proof: https://en.wikipedia.org/wiki/Happy_number#Sequence_behavior
66.5 buddy system bitmap
https://github.com/jasonfeng1989/Tech_Interviews/blob/master/others/buddy_bitmap.py
Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold:
- a node’s value is 1 if and only if all its subtree nodes’ values are 1
- a leaf node can have value either 1 or 0
Implement the following 2 APIs:
- set_bit(offset, length), set the bits at range from offset to
offset+length-1
- clear_bit(offset, length), clear the bits at range from offset to offset+length-1
i.e. The tree is like:
0
/ \
0 1
/ \ / \
1 0 1 1
/\ / \ /
1 1 1 0 1
Since it's complete binary tree, the nodes can be stored in an array:
[0,0,1,1,0,1,1,1,1,1,0,1] My Solution:
// clear all descendants
// 这里有个问题,就是设置当前点为0,的时候只要下面的两个child点不都是1,
// 应该就ok,但是如果都是1,就说明下面的点应该至少有一个是0,但是是左孩
// 子还是右孩子呢?这个不好决定,所以这里干脆就都设置为0
// set all descendants to x
void set_desc(vector<int>&v, int i, int x=1){
if(i<v.size() && v[i]!=x) v[i]=x, _set(v,2i+1), _set(v,2i+2);
}
void clearb(vector<int>& v, int f, int l){
int L=v.size();
int t=f+l-1;
for(int i=f;i<=min(t,L-1);++i){
if(v[i]==0) continue;
set_desc(v, i, 0);
int z=(i-1)/2;// clear ancestors
while (z>=0 && v[z]){v[z]=0, z=(z-1)/2;}
}
}
void setb(vector<int>& v, int f, int l){
int L=v.size();
int t=f+l-1;
for(int i=f;i<=min(t,L-1);++i){
if(v[i]) continue;
set_desc(v,i);
int z=(i-1)/2; // set ancestors
while (z>=0 && v[z]==0){v[z]=1, z=(z-1)/2;}
}
}http://www.1point3acres.com/bbs/thread-192327-1-1.html
这是一个二维数组,不是一个heap(heap就是说这个树存在一个一维数组里,满足A的child是A[2i+1]和A[2i+2]),问题背景起源于内存分配问题
比如有N个level,第一个level有一个bit,第二个level有2个bit,第三个level有四个bit,调用第x个level的第y个bit直接用A[x][y]
那么A[x][y]的孩子包括A[x+1][2y] 和 A[x+1][2y+1]
题目要求完成的是:
例如ClearBits(A, 4, 9) => 把第N个level的第4位到第9位清0. 当child清0之后, parent也要跟着清0,一直到root
Urumic 发表于 2016-6-9 01:32 想问一下楼主buddy system 的资料里说的level update
而不是heap like update是什么意思啊
heap就是说这个树存在一个一维数组里,满足A的child是A[2i+1]和A[2i+2] level update:
比如有N个level,第一个level有一个bit,第二个level有2个bit,第三个level有四个
bit,调用第x个level的第y个bit直接用A[x][y] 那么A[x][y]的孩子包括A[x+1][2y] 和
A[x+1][2y+1]http://www.mitbbs.com/article_t1/JobHunting/32702941_0_2.html
--- clearBits(int offset, int len);里面的len是啥意思?
这个函数都是从最下面一层开始clear. 将offset到(offset+len-1)设置为0.
这个题目假设bit存储在bits[level][number]里.因为是从最底层开始set和clear,所以我们这里只考虑ancestors,不考虑descendants!
void clearb(vector<vector<bool>>& v, int f, int l){
int R=v.size(), C=v[0].size(), c=R-1, t=min(f+l-1, C-1);
while(c>=0){
int m=0;
for(int k=f;k<=t;++k)
if(v[c][k])
m++, v[c][k]=0;
if(!m) return;
c--, f>>=1, t>>=1; // clear ancestors
}
}
void setb(vector<vector<bool>>& v, int f, int l){
int R=v.size(), C=v[0].size(), c=R-1, t=min(f+l-1, C-1);
while(c>=0){
int m=0;
for(int k=f;k<=t;++k)
if(v[c][k]==0)
if(c==R-1 || v[c+1][2*k] && v[c+1][2*k+1])//Donot forget this condition
m++, v[c][k]=1;
if(!m) return;
c--, f>>=1, t>>=1;
}
}66.6 Virtual Function and Table
http://www.1point3acres.com/bbs/thread-117854-1-1.html
2015(1-3月) 码农类 硕士 全职 Pure Storage - 网上海投 - 技术电面 |Other 今天下午的PureStorage电面,希望对后来的同学有所帮助. 这家的电面是碰到的第一家提前就给code的.面试之前HR发来一个C++的代码,关于virtualfunction和mutipleinheritance的.代码看起来很简单. 1. 一个基类Base1,有一个Virtualfunction virt1(). 一个子类Derived:Base1,override了这个函数. 另一个全局函数Global1,输入是Base1指针,返回这个指针指向的virt1. 在main里,定义一个Derived指针 d,然后输出,d->virt1(), Global1(d)
- 一个基类Base2,有一个Virtualfunction virt2(). 一个子类MultipleDerived:Base1, Base2,override了两个函数.
另一个全局函数Global2,输入是Base2指针,返回这个指针指向的virt2.
在main里,定义一个MultipleDerived指针 md,然后输出,md->virt1(), Global1(md), md->virt2(),Glbal2(md)
之前看到地里同学们的面经对这个问题有所准备,但是不清楚到底会问到什么程度.果然到后来都傻眼了.基本上是在讨论compiler应该怎么处理虚函数.
首先问两个输出结果是什么.如果要写一个编译器,应该怎么处理虚函数.当然按照网上能查到的知识说了一通.
接下来,如果编译器MultipleDerived的data member跟父类的data member对调一下会有什么问题?
再改,原来virt2是返回一个常数,如果返回的是MultipleDerived的datamember, 然后在Global2里面传入一个Base2的指针,会怎么样?到这基本上就晕了.其实意思可能是,编译器是通过offset来找到datamember的,如果来了个base2指针,那么this会指向Base2开始的地方,也就是第二个vptr的位置,那么再用相同的offset就会跳出去了.然后就讨论怎么解决这个问题,提示了一个办法,又问还有没有别的办法.又顺得他的话讨论了一下.
最后轻松的问答时间完全毫无压力了…
66.7 593. Valid Square
https://leetcode.com/problems/valid-square
struct Solution {
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
unordered_set<int> si;
si.insert(dis2(p1,p2)),si.insert(dis2(p1,p3)),si.insert(dis2(p1,p4));
si.insert(dis2(p2,p3)),si.insert(dis2(p2,p4)),si.insert(dis2(p3,p4));
return si.size()==2 && !si.count(0);
}
int dis2(vector<int>& x, vector<int>& y){
int t1=abs(x[0]-y[0]), t2=abs(x[1]-y[1]);
return t1*t1+t2*t2;
}
};https://stackoverflow.com/questions/18198314/what-is-the-override-keyword-in-c-used-for
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=192290
2016(4-6月) 码农类 硕士 全职Pure Storage - 内推 - 技术电面 Onsite |Failfresh grad应届毕业生 刚又收到Pure Storage拒信,来发个面经.不得不说他家bar真是高…而且换新题了!
电面1:task dispatch system, event fire call register那个,老四题其中一道
电面2:给四点判断是否form a square
follow up 是一堆点里找square的个数,也是老题.
4-combination. Check 77. Combination (DFS)
int dis2(vector<int>& x, vector<int>& y){...}// return distance square
// [....] ; [..]--[..], [..]-[.]-[.], square
bool is_sqaure(vector<int>& p1, vector<int>& p3, vector<int>& p3, vector<int>& p4){...}
// T: O(4 * N Choose 4)
using point=vector<int>;
void dfs(vector<point>& v,vector<vector<point>>& r, vector<point>& p, int hd){
if(p.size()==4) { r.push_back(p);return;}
for(int i=hd; i<v.size(); ++i){
p.push_back(v[i]);
dfs(v,r,p,i+1);
p.pop_back();
}
}
// T: O(4*N choose 4)
int count_square(vector<point> v){
sort(v.begin(), v.end());
// http://en.cppreference.com/w/cpp/algorithm/unique
v.erase(unique(v.begin(), v.end()), v.end());
vector<vector<point>> r;
vector<point> p;
dfs(v,r,p,0); // To get 4 comb
int count=0;
for(auto& e: r)
count+=is_square(e[0],e[1],e[2],e[3]); // O(1)
return count;
}Onsite:
- buddy system,也是老题,但只考了clear bits().
follow up是最小化访问读取该树的次数,并且一次clear一层level,以前有人提到的
- 新题,一个disk有很多chunks,但只有三种类型称为A,B,C.要求把乱序的disk chunks重排为[A A A B B B B C C],所有A在前面,C在后面,B在中间,只能通过1) read某个index的chunk 2) swap两个chunk的data 这两个操作来实现.follow up是尽量减少2)的次数
Check solution here: array
- 新题,已知一个叫get_ids()的API能够耗时1s并返回100个各不相同的id(第二次call返回的和第一次的也不会有任何重复),有个待实现的函数叫get_one_id(),每秒最多被call 100次,每次call要能返回一个新的id.题目就是利用get_ids()实现get_one_id()
follow up是保证每次call get_one_id()不能等待超过1s
- manager吹逼
说实话楼主自我感觉面得不错的.第一轮老题因为给的数据结构和准备的不一样,所以慌了下被指出2个小bug,但很快就改正,最后也一起讨论出了他满意的follow up的解法;第二轮题目简单发挥最好,全程无bug,从基本解到follow up毫无停顿,最后人家还说u did a good job的;第三轮是个刚来1年不到的新人,在交流和引导上并不是很专业,但我还是和他一路积极讨论下最后在他的提示下写出了他想要的解法.老实说这题很非主流,应该算是实际问题而非算法题;最后的manager也是全程吹逼很开心.然而过两天还是被拒.HR说’‘Although everyone enjoyed talking with you, we do not see a strong match’’.楼主猜测要不就是第一轮小bug(while语句里多余的一个条件,>=写错成>),要不就是这一轮解决follow up的速度太慢,要不就是第三轮里没有不经提示解决follow up,当然最有可能的还是背景不符.楼主推荐要面的小伙伴对system level的storage以及database management最好还是强化下…
第三轮:产生一个圆上的所有坐标.不用sqrt, sin, cos等内建函数.
提示:所有的点都是整点.首先我们可以利用对称性把圆分成8块,先画出0-45度角内
的点,然后映射之.对于其中0-45度角中的点,当X＋1时,Y的值或者不变或者-1,然
后放入圆方程中看哪一个是对的.
66.8 Draw a Circle
Given a parameter r2, where the equation \(x^2+y^2=r2\) holds.
Return a list of points that
(1) x and y are both integers
(2) fits the circle equation
When r2=1000000, in the first half quadrant, we can find four points:
800 600, 936 352, 960 280, 1000 0
For a point where x or y not equal to 0, there are 8 different mirrors including itself. But for {1000,0} there are only 4!!!!
T: \(O(r2)\)
// input is r square; draw arc in the 1st half quadrant
vector<pair<int,int>> draw_circle(int r2){
vector<pair<int,int>> r;
for(int x=1; x*x <= r2; ++x){
for(int y=0;y<=x;++y)// y<=x in first half quadrant
if(x*x+y*y==r2){
r.push_back({x,y});
break;
}
}
int l=r.size();
while(l--){
int x=r[l].first, y=r[l].second;
if(y) r.emplace_back(x,-y);
if(x) r.emplace_back(-x,y);
if(x && y) r.emplace_back(-x,-y); //!
r.emplace_back(y,x);
if(y) r.emplace_back(-y,x);
if(x) r.emplace_back(y,-x);
if(x && y) r.emplace_back(-y, -x); //!
}
return r;
};Use binary search to find y at speed of \(LogN\).
T: \(O(\sqrt{r2} Log\sqrt {r2})\)
vector<pair<int,int>> draw_circle2(int r2){
vector<pair<int,int>> r;
for(int x=1; x*x <= r2; ++x){
int y0=0, y1=x, T=r2-x*x;
while(y0<=y1){
int m=y0+(y1-y0)/2, t=m*m;
if(t==T){
r.emplace_back(x,m);
break;
}else if(t<T)
y0=m+1;
else y1=m-1;
}
}
int l=r.size();
while(l--){
int x=r[l].first, y=r[l].second;
if(y) r.emplace_back(x,-y);
if(x) r.emplace_back(-x,y);
if(x && y) r.emplace_back(-x,-y);
r.emplace_back(y,x);
if(y) r.emplace_back(-y,x);
if(x) r.emplace_back(y,-x);
if(x && y) r.emplace_back(-y, -x);
}
return r;
};http://www.1point3acres.com/bbs/thread-206999-1-1.html
- 用户会随机call int get_call_id(), 已经有 get_ids(int num_of_id, int *buf),get ids from disk or database,consume 1s per call.实现get_call_id(),我是一步一步来的,先实现一个单线程的,满足average小于要求的,然后多线程,然后improve,用了mutex和condition variable.最后还用到了tcp congestion control(1. slow start 2. congestion avoid 3. congestion recovery, 有兴趣的可以网上查一下) 的机制来处理动态分配buf的要求.
static const int BATCHNUM=4;
mutex m;
condition_variable cv;
vector<int> buf(BATCHNUM*2);
atomic<int> cur{-1};
int INVALID_ID=INT_MIN;
void get_ids(int num_of_id, int* buf){}
void fill_ids(){
while(1){
if(cur==-1){
get_ids(BATCHNUM, &buf.front()); // 1 second
get_ids(BATCHNUM, &buf.front()+BATCHNUM); // 1 second
cur=0;
cv.notify_all();
}else{
unique_lock<mutex> ul(m);
while(cur!=BATCHNUM && cur!=BATCHNUM*2
&& buf[BATCHNUM-1]!=INVALID_ID
&& buf[BATCHNUM*2-1]!=INVALID_ID)
cv.wait(ul);
if(buf[BATCHNUM-1]==INVALID_ID)
get_ids(BATCHNUM,&buf.front()); // 1 second
if(buf[BATCHNUM*2-1]==INVALID_ID)
get_ids(BATCHNUM,&buf.front()+BATCHNUM); // 1 second
}
}
}
int get_call_id(){
unique_lock<mutex> ul(m);
while(cur==-1)
cv.wait(ul);
if(cur==BATCHNUM || cur==BATCHNUM*2)
cv.notify_one();
if(cur==BATCHNUM*2)
cur=0;
int t=buf[cur];
buf[cur++]=INVALID_ID;
return t;
}Version 2:
static const int BATCHNUM=4;
mutex m;
condition_variable cv;
vector<int> buf(BATCHNUM*2);
atomic<int> cur{-1};
atomic<short> update{0};
void get_ids(int num_of_id, int* buf){}
void fill_ids(){ // one thread to write
while(1){
if(cur==-1){
get_ids(BATCHNUM, &buf.front()); // 1 second
get_ids(BATCHNUM, &buf.front()+BATCHNUM); // 1 second
cur=0;
cv.notify_all();
}else{
unique_lock<mutex> ul(m);
while(update==0)
cv.wait(ul); // unlock ul/m
if(update==1) // update first part
update=0, cv.notify_all(), get_ids(BATCHNUM,&buf.front()); // 1 second
if(update==2) // update second part
update=0, cv.notify_all(), get_ids(BATCHNUM,&buf.front()+BATCHNUM); // 1 second
}
}
}
int get_call_id(){ // multiple threads to read
unique_lock<mutex> ul(m);
while(cur==-1)
cv.wait(ul);
if(cur==BATCHNUM)
update=1, cv.notify_one();
if(cur==BATCHNUM*2)
cur=0, update=2, cv.notify_one();
while(update) cv.wait(ul); // make sure fill thread get notified
return buf[cur++];
}version2仍然有一个bug,line 16的lock范围到函数结束为止.所以会在line 20或者22结束之后才释放.而这个lock是get_call_id需要的,所以这里必须要在notify之后及时unlock. 所以有了下面的代码:
Version 3:
static const int BATCHNUM=10;
mutex m;
condition_variable cv;
vector<int> buf(BATCHNUM*2);
atomic<int> cur{-1};
atomic<short> update{0};
void get_ids(int num_of_id, int* b);
void fill_ids(){ // one thread to write
while(1){
if(cur==-1){
get_ids(BATCHNUM, &buf.front()); // 1 second
get_ids(BATCHNUM, &buf.front()+BATCHNUM); // 1 second
cur=0;
cv.notify_all();
}else{
unique_lock<mutex> ul(m);
while(update==0)
cv.wait(ul); // unlock ul/m
int* t=NULL;
if(update>0){
t=&buf.front()+(update-1)*BATCHNUM;
update=0;
cv.notify_all(), ul.unlock(); //!
}
get_ids(BATCHNUM, t); // 1 second
}
}
}
int get_call_id(){ // multiple threads to read
unique_lock<mutex> ul(m);
while(cur==-1) cv.wait(ul);
if(cur==BATCHNUM) update=1, cv.notify_one();
if(cur==BATCHNUM*2) cur=0, update=2, cv.notify_one();
while(update) cv.wait(ul);
return buf[cur++];
}