一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3221|回复: 21
收起左侧

Pure Storage OA 11/8/2015 Due

[复制链接] |试试Instant~ |关注本帖
romanchelsea 发表于 2015-11-9 12:46:24 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Pure Storage - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
刚做完pure storage的online challenge 4A, 所以来写一些面经。已经不记得是什么时候投的了,大概一两个月前海投的吧。

这是8题版本的,做之前参考了朋友的面经;地里搜了一半天,只有这三个帖子跟我是一个版本的吧,贴在这里供后来的人参考。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
http://www.1point3acres.com/bbs/ ... 7&fromuid=63593
http://www.1point3acres.com/bbs/ ... 9&fromuid=63593
http://www.1point3acres.com/bbs/ ... 5&fromuid=63593
-google 1point3acres
一共八道题,5道多选题或者填空(计算)题,1道binary search找错题,不是改错,两道coding。coding的题目,好像可以用java/c++/python, 好像还看到了php, 不过没看到ruby, javasccript等等。既然以上三个帖子里面,大致所有的题目都cover到了,我就尽我所能补充一下一些不明确的地方。题目的顺序记不太清了。-google 1point3acres

1. 有个人有7块硬盘,每个容量513GB,他把所有硬盘放在一起,现在他往硬盘里写东西,每秒200,000个operation。其中20%每次写入人512B, 30% 1024B, 40% 4096B, 10% 16384B。
问,多少分钟后写满了7%,结果精确到分钟。

2. DFS那题,给的只有 C/C++的代码,用DFS找一个tree里面有没有一个value。DFS的方式是,先打印出当前node,然后标记当前node为visited,然后考虑node->right, node->parent, node->left,如果没有visited。
问题大概就是打印出遍历的顺序。我同学说他记得的是,按便利顺序打印出所有的value。我可能做的时候看错了,或者是我的题目跟他略有不用,我记得的题目是,打印出便利到11之前所有的值。
这题关键就是记住DFS顺序,先right child,然后parent,最后left child。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
3. 需要多少byte那题没什么好说的。3个状态,需要2bit;0~31****, 需要19bit;6个状态,需要3bit;又是0~多少,需要10还是16bit(草稿上的数字看不清,不记得了 - -|)。所以总共多少byte可以算一下,也许是5byte吧。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
4. 5 都是多选题。
4 是设计一种数据结构,好像是存{key: value}, key是32bit-integer, 的数量保证小于1billion( < 2 ^32, - -|),经常insert,occasionally iterate through。说说选项吧,
有说用array 存,要iterate的时候用merge sort排序;
用array存, ..... 用quicksort排序。
用array存, insert的时候找好位置再insert,
用linkedlist 存,然后mergesort排序
用balanced tree....1point3acres缃
还有个选项记不清了。。. 鍥磋鎴戜滑@1point 3 acres


第5题主要考到multithreading,代码只有c++的,用了c++里面的lock,本人主要用java,不过大概也就用到了lock.acquire(), lock.release()吧,. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
定义的一个class是一个可以resize的array。lock就是防止读写array的时候一些concurrency issue。. 1point 3acres 璁哄潧
做之前可以搜一搜c++的一些terminology: resource leak, memery corruption, 都是多线程的基础。

6, Binary search那题给了java, c++, python 版本的代码,这题的任务是,自己给一个testcase, 然后打印出给的testcase 数组的长度,内容 和结果。。。. 1point 3acres 璁哄潧
Binary search 的代码有很多flaw,求mid的时候 没考虑overflow, 找target的时候,没有先考虑当前index的数是不是target。。。这题妥妥的,[1,2,3]找2,就过不了。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
7. 求一个string的所有substring中,palindrome的数量,妥妥的。各种方法都可以,刷过leetcode的都应该没问题。

8,第八题说是bonus,主要原因就是整个oa只有一个小时,时间比较紧张。所以说,以后拿到oa的同学,不妨先把扣腚题目做了。
这题就是升级版的 valid parentheses,Stack + Set完破。题目的描述套上了一层OS的外衣, 所以看起来有点吓人,其实还好。输入是一个String[]
比如
1. aquire 123. visit 1point3acres.com for more.
2. release 123
3. aquire 345
4. release 345
这是合法的,return 0

1. aquire 123
2. aquire 345

3. release 123
4. release 345

这样就不合法, return 3. From 1point 3acres bbs
要这样才行, 后aquire的先release.鐣欏璁哄潧-涓浜-涓夊垎鍦
1. aquire 123
2. aquire 345
3. release 345. more info on 1point3acres.com
4. release 123

.鐣欏璁哄潧-涓浜-涓夊垎鍦
这样 也不对, 没有release 123, return 4
1. aquire 123
2. aquire 345
3. release 345

.鐣欏璁哄潧-涓浜-涓夊垎鍦

这样也不对,return 3. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1. aquire 123
2. release 123. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
3. release 345





.鏈枃鍘熷垱鑷1point3acres璁哄潧
值得注意的是,这题,每行string之前的1,2,3,4都是没有的,每个string都只包含aquire/release 和后面的数字。
当时做的时候以为前面有index number,所以一直没跑成功。

所以,不要被有的帖子里说时间不够,没做,吓到了。都是bullshit。

评分

6

查看全部评分

Zek_W 发表于 2016-3-4 05:12:11 | 显示全部楼层
请问第四题多选怎么做啊?为什么?.鐣欏璁哄潧-涓浜-涓夊垎鍦

我只知道考虑worst case的时候,quick sort, insertion sort是不行的,in-place mergesort和后面四个选项怎么分析呢? 感觉好像都可以啊
回复 支持 1 反对 0

使用道具 举报

Andrew007 发表于 2015-11-9 12:58:09 | 显示全部楼层
顶一个,挺详细的,结合前面的帖子就很完美了。谢谢啦。
回复 支持 反对

使用道具 举报

Andrew007 发表于 2015-11-9 14:06:50 | 显示全部楼层
第8题那个为什么需要一个set啊?

补充内容 (2015-11-9 14:09):
知道了。。。
回复 支持 反对

使用道具 举报

attractor 发表于 2015-11-9 14:10:41 | 显示全部楼层
Andrew007 发表于 2015-11-9 14:06. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第8题那个为什么需要一个set啊?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
因为需要处理lock被acquire两次和lock没被acquire却被release的情况,用个hash_set就可以记录或者消除这些信息
回复 支持 反对

使用道具 举报

attractor 发表于 2015-11-9 14:17:00 | 显示全部楼层
还蛮同意楼主的,其实仔细想想并不复杂,只是我multi-thread有点弱,做那题找不着北导致bonus没写完T T
回复 支持 反对

使用道具 举报

Andrew007 发表于 2015-11-9 14:20:28 | 显示全部楼层
attractor 发表于 2015-11-9 14:10
因为需要处理lock被acquire两次和lock没被acquire却被release的情况,用个hash_set就可以记录或者消除这 ...

-google 1point3acres如果不用set的话, 检查其中的每个string元素,如果包含“acquire”的话,就放到stack里,如果是“release”就看能不能消除。这样可以吗?
回复 支持 反对

使用道具 举报

attractor 发表于 2015-11-9 14:56:24 | 显示全部楼层
Andrew007 发表于 2015-11-9 14:20-google 1point3acres
如果不用set的话, 检查其中的每个string元素,如果包含“acquire”的话,就放到stack里,如果是“releas ...

好像楼主的题目描述没贴全。原题里还有这种情况: acquire 123 acquire 456 acquire 123 ...,123被acquire了两次,也不合法,每个ID都必须是唯一的。所以最好用个set记录是否已经acquire过了
回复 支持 反对

使用道具 举报

Andrew007 发表于 2015-11-9 15:33:38 | 显示全部楼层
attractor 发表于 2015-11-9 14:56
好像楼主的题目描述没贴全。原题里还有这种情况: acquire 123 acquire 456 acquire 123 ...,123被acquir ...

谢谢你的讨论和帮忙
回复 支持 反对

使用道具 举报

cathycat 发表于 2015-11-10 02:59:46 | 显示全部楼层
楼主好牛逼,我也做了一样的oa没有做完,很早就做了,到现在没有给我消息,估计是跪了,你收到店面邀请了吗?
回复 支持 反对

使用道具 举报

liu.haonan 发表于 2016-3-3 09:33:40 | 显示全部楼层
请问4A就会是这个版本吗
回复 支持 反对

使用道具 举报

hotinherre 发表于 2016-3-4 08:12:49 | 显示全部楼层
liu.haonan 发表于 2016-3-3 09:33
请问4A就会是这个版本吗
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
是这个版本 我投的实习 表示这些题 根本不会做。。。 我进去溜达一圈 关了 不做了。。 太难了。。
回复 支持 反对

使用道具 举报

y2323k23 发表于 2016-3-4 22:02:00 | 显示全部楼层
请问下楼主, 第七题返回所有的回文串个数, 单个字符也算是回文串么
回复 支持 反对

使用道具 举报

liu.haonan 发表于 2016-3-5 03:00:02 | 显示全部楼层
y2323k23 发表于 2016-3-4 22:02
请问下楼主, 第七题返回所有的回文串个数, 单个字符也算是回文串么

单个字符也算的
回复 支持 反对

使用道具 举报

redzqb 发表于 2016-3-5 05:45:25 | 显示全部楼层
谢谢楼主 非常详细
回复 支持 反对

使用道具 举报

c00der 发表于 2016-3-5 07:50:22 | 显示全部楼层
是否有人可以分享OA的照片吗?
回复 支持 反对

使用道具 举报

y2323k23 发表于 2016-3-7 12:06:39 | 显示全部楼层

也就是说里边出现多种重复情况么,  比如  aabbaa  包含 aabbaa 也包含 abba   还包含 a , a, b,b,a,a 也包含 aa, bb, aa这个样子么
回复 支持 反对

使用道具 举报

liu.haonan 发表于 2016-3-7 13:21:27 | 显示全部楼层
y2323k23 发表于 2016-3-7 12:06
也就是说里边出现多种重复情况么,  比如  aabbaa  包含 aabbaa 也包含 abba   还包含 a , a, b,b,a ...

记得应该是重复的只算一次
回复 支持 反对

使用道具 举报

y2323k23 发表于 2016-3-7 21:58:46 | 显示全部楼层
liu.haonan 发表于 2016-3-7 13:21
记得应该是重复的只算一次

非常感谢, 我今天做OA
回复 支持 反对

使用道具 举报

Nasher 发表于 2016-4-13 23:24:48 | 显示全部楼层
不好意思,刷屏了
请问你是之前在UTD,
我现在在申请UTD, 网申遇到些问题,想请教一下问题,有点着急,不知是否可帮忙解答下:
1. 网申时,上传的文件一定是PDF 是吗?因为申请说明里面是说PDF,可是申请过程中上面提了可接受哪些格式的文档,包括JPG的,所以不知道JPG的是否可以,以哪个说明为主。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
2. 网申时,每个上传的地方只能传一个文件,那是不是要吧毕业证和学位证,翻译文件都扫描到一个文档里面。还有本科的成绩单翻译件一共三张,这样是不是自己扫描到一个文件里面?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 02:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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