一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 503|回复: 3
收起左侧

Pure Storage 跪经

[复制链接] |试试Instant~ |关注本帖
alexzhang718 发表于 2017-10-13 03:37:02 | 显示全部楼层 |阅读模式

2018(10-12月) 码农类 本科 实习@Pure Storage - 校园招聘会 - Onsite 校园招聘会 |Fail其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
# Pure Storage Coding Challenge -- career fair
- Debug and implement a thread safe stack.
- 给了一个stack的半成品,debug部分 在add(或者是check size的时候)有个mutex lock加的太晚了,还有一个bound溢出了(时间太长忘掉了具体是哪一部分)
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴- 前面constructor中没有initialize一个常量的值 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
- class里面的两没有设成private,有的也没有加explicit,这些不写code没有错误,但是加上是加分. visit 1point3acres.com for more.
- copy constructor 也是加分项.1point3acres缃
- 在heap中存了个array最后没有在destructor中delete
- 最后自己要写个stack pop() , pop的时候要注意改size的时候要提前给size变量加mutex lock,还有在delete和unlock之前要copy那个值,这样就可以再delete之后return pop的那个值
# Pure Storage on campus Interview
- 如果题做的可以并且排队比较早的话就会拿到on campus,不过有的时候也是玄学
- Description: on campus 或者是 phone interview一般都会是一道多线程worker + callback的题,假如有n个worker,要你实现一个startwork的class,每个worker就是一个线程,startwork要实现non-block start,每个worker(线程)结束有要有一个callback,所有的worker都完结后还有一个总callback function,不管是开始还是结束都需要non-block,不能有busy waiting的情况出现. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
- 基本思路就是用个for loop把每个worker都加到一个data structure里,记一下size,然后call worker.start(callback func); 要有一个global变量记着完成worker的数量n_complete
- worker的callback function就是在结束时grab一个mutex 之后increment n_complete, 由于不知道那个线程是最后的那个线程,最后还要加一个if statement check一下n_complete是不是等于size,如果一样就去call一下startwork整个的callback function
- 之后还有一个follow up,问如果要想在startwork开始之前就直接先call worker.start(),这样就会更有效率,但有个问题就是有可能在startwork开始之前所有的线程就已经结束了,怎么解决这个问题
- 我当时灵光突现,用的是加一个empty worker,这样这个就是最后一个worker就可以take care of最后的那个callback了

# Pure Storage Onsite
- Buddy bitmap,一个full binary tree,tree里面只有1和0,如果parent的两个child都是1的话,parent就为1,否则就是0
- if (parent.left==1 && parent.right ==1) parent = 1; else parent = 0; //rule
- 这个bitmap可以用一个2d array表示,bits[level][pos], level指的是binary tree的层数,pos指的是在某一层的index
- 要implement一个clearbits(int start_pos, int len), 如果假设一个N level的binary tree,全是1,clearbits要做的就是把最底层的从start_pos开始到start_pos + len -1 index地leaf node全部变成0,leaf变成0之后,parent也要变
- 要注意的一点是,如果parent是bits[x][y]的话,left child就是bits[x+1][2*y], right child就是bits[x+1][2*y+1]
- 如果left child或者right child是bits[x][y], parents就是bits[x-1][y/2]
- 我开始想的方法是比较大众的DFS recursion,从第一个node开始逐层向上,找到parent,set parent = 0,一直到root node,中间如果碰见0直接break,避免重复计算. 1point 3acres 璁哄潧
- 在之后的follow up中得知这种dfs在存储的时候回掉cache,所以需要优化,BFS比DFS更适合这种场合,就要求写个BFS的algorithm
- 我开始用了个deque,从底层push_back,之后又不断地peek,层层向上,考官老印之前没见过这种方法,给他解释了一遍以后,他同意了,不过他说还有种更简单的办法,于是他就给了个hint,就是直接calculate每一层需要clearbits的start和end point。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
- 因为每上层的start point就是他下一层start point /2 ,end point也是同样的道理,这样一个while loop,从最底层loop到最上层,不断更新start和end point,完成了对于整个algorithm的优化。
- 之后的followup是setbits(),和clearbits相反,setbits是把从底层leaf node的bits全部变成1,也是逐层向上调整parents. visit 1point3acres.com for more.
- 唯一trick的地方就是要检查child的sibling, 要判断start和end点是不是包括了偶数个或者是奇数个,如果是奇数个,不是start没从leftchild开始,就是end没有end到rightchild,涉及到要检查他们的sibling,只有他的sibling和它都是1的时候才能把上层的parent搞成1,否则新的start pos就是 startpos/2 +1 (或者end是end_pos/2 -1)
- --------------End of first onsite round---------------.1point3acres缃
- 第二轮是画圆,中心假设是0,0,半径是R,给予plot(x,y)function
- 最简单的思路就是for loop,x从0到R/sqrt(2),y = sqrt(R^2 - x^2) plot(x,y), plot(y,x), plot(-x,y), plot(-y,x), plot(y,x), plot(-x,-y), plot(-y,-x), plot(x,-y),把圆分成1/8,之后根据镜像的原理来graph其他7部分的点
- follow up,因为像素点是discrete,所以有的时候不能找到perfect的点,怎样使这个圆变得连贯,没有空点
- 要用Bresenhams算法来画圆
- 核心思路就是每次的approx都会result in 一点点error,当error cumulate到一个threshold的时候,就应该修正
- 最后一步follow up就是怎样get rid of for loop中的sqrt,因为还是cost太多的计算cycle
- 解决的思路大体上就是因为只需要graph 1/8,截止到45度角(x = y,从 x < y 到 x = y)的地方,所以for loop条件换成x <= y就好,这样就不用计算sqrt了. more info on 1point3acres.com
- 这题做的比较磕绊,面试官给了不少hint并且介绍了那个画圆算法

# Pure Storage Timeline
- 9.19 校面(多线程),一小时1 on 1
- 9.21 接到onsite
- 10.5 mountain view onsite
- 10.12 rej

评分

1

查看全部评分

FF-Ti 发表于 2017-10-13 03:39:05 | 显示全部楼层
想问下lz,这公司是上来直接做题嘛 还是还聊一些项目简历呀
回复 支持 反对

使用道具 举报

 楼主| alexzhang718 发表于 2017-10-13 03:40:29 | 显示全部楼层
FF-Ti 发表于 2017-10-13 03:39
想问下lz,这公司是上来直接做题嘛 还是还聊一些项目简历呀

直接做题
回复 支持 反对

使用道具 举报

FF-Ti 发表于 2017-10-13 03:44:05 | 显示全部楼层

好的 谢谢lz
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-16 11:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表