Product Design + Engineering 相關MS@Harvard,MIT,CMU,Stanford

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
查看: 1064|回复: 3
收起左侧

Pure Storage 跪经

[复制链接] |试试Instant~
我的人缘0
alexzhang718 发表于 2017-10-13 03:37:02 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩

2018(10-12月) 码农类General 本科 实习@PureStorage - 校园招聘会 - 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没有错误,但是加上是加分项.留学论坛-一亩-三分地
- copy constructor 也是加分项
- 在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. 1point3acres
- 要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,避免重复计算
- 在之后的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.1point3acres网
- 唯一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---------------
- 第二轮是画圆,中心假设是0,0,半径是R,给予plot(x,y)function-google 1point3acres
- 最简单的思路就是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了
- 这题做的比较磕绊,面试官给了不少hint并且介绍了那个画圆算法

# Pure Storage Timeline.本文原创自1point3acres论坛
- 9.19 校面(多线程),一小时1 on 1
- 9.21 接到onsite
- 10.5 mountain view onsite. from: 1point3acres
- 10.12 rej. From 1point 3acres bbs

评分

参与人数 3大米 +10 收起 理由
ohshout + 3 给你点个赞!
tiesto1114 + 5 很有用的信息!
蜡笔小新 + 2 给你点个赞!

查看全部评分


上一篇:C一-店-跪
下一篇:Spotify 面筋
我的人缘0
FF-Ti 发表于 2017-10-13 03:39:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  75% (74)
 
 
24% (24)  踩
想问下lz,这公司是上来直接做题嘛 还是还聊一些项目简历呀
回复

使用道具 举报

我的人缘0
 楼主| alexzhang718 发表于 2017-10-13 03:40:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
FF-Ti 发表于 2017-10-13 03:39
想问下lz,这公司是上来直接做题嘛 还是还聊一些项目简历呀

直接做题
回复

使用道具 举报

我的人缘0
FF-Ti 发表于 2017-10-13 03:44:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  75% (74)
 
 
24% (24)  踩

好的 谢谢lz
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-20 18:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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