一亩三分地论坛

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

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

Pure Storage 两次电面和Onsite面经,顺便贴点准备面试的资料

[复制链接] |试试Instant~ |关注本帖
进击的菜鸟 发表于 2016-6-5 09:58:37 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@Pure Storage - 内推 - 技术电面 Onsite |Failfresh grad应届毕业生

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

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

x
补一个Pure Storage 的面经,给自己攒攒人品,在地里学到了很多,希望也能帮到以后面pure storage的人地里的问题面经写的比较乱。。尤其是onsite的几个题,面经很多,没有几个能把题目仔细说说清楚的

Pure Storage是做Flash Storage Array的,在这个方向里面排前几名,在2015年年末IPO,上市之前的2015年猛招了一批人,大概很多人奔着IPO发财去的吧,有挺多人水平不错,
不过上市之后一直比较低迷,股价略惨,但是貌似招人的bar没怎么降低

第一次电面: 是虚函数的那个题目,发过来一段code,针对这个code来发散式的问很多问题,
参考资料:https://www.evernote.com/shard/s ... 1802d1941338b03d375


第二次电面: Happy Number,Leetcode原题: https://leetcode.com/problems/happy-number/

代码写完了要做比较细致的数学分析 证明为什么这么写是对的,参考资料: https://en.wikipedia.org/wiki/Happy_number
里面那段单调性的证明比较重要,

. From 1point 3acres bbs
Onsite:
准备的资料,里面有几段code,不过是最simple的版本,onsite的时候肯定要优化的:https://www.evernote.com/shard/s ... d2c9b353194335a1b62
(1) 画圆的题目,这个题目说起来简单,一个简单的循环加对称就完了,但是
follow up是很多的,关键有3点,
1 - 当r很小,如r==3时,如何多画几个点,使他尽量多画一些点,这些点可能不exactly在圆上,但是有这些点要比孤零零的一个圆四个点要好很多
2 - performance,尽量减少乘法以及开方的使用数量
    (1)x从r变到0.717r 要比从0变到0.717r可以多画几个点,
    (2)终止条件可以写成for(x=0; x<y;x++ ),这样就可以少用一次乘法或开方 .鏈枃鍘熷垱鑷1point3acres璁哄潧
    (3)x加1之后的y只有两种可能,要么是和上次的y相等,要么是减去1,因为在这段范围内的圆斜率是小于1的,所以这里又可以少用一次乘法。
最终版本的代码里面,只用了一次乘法

(2)ClearBits和SetBits
这是一个二维数组,不是一个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
我发的这个note的最后有一个link,有题目的详细说明和图解,但是代码是错的
. more info on 1point3acres.com
(3)O(1) Map.鏈枃鍘熷垱鑷1point3acres璁哄潧
设计一个Map, 满足 add: O(1)  deletion: O(1)  lookup: O(1)  clear:O(1)  iterate: O(number of elements)。. 1point 3acres 璁哄潧
关键在于clear和iterate了,mitbbs上的帖子暗示了一下,但是不是很明白:
number of elements 不是N,一定要严格的number of elements
如果我们用randomly accessed array,复杂度如下:
add: O(1)  deletion: O(1)  lookup: O(1)  clear: O(size of array)   iterate:
O(size of array)
如果我么用sequential array, 复杂度如下:
add: O(1)  deletion: O(number of elements)  lookup:O(number of elements)   
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。
网上的global version number的方法面试官不认可
整合的办法就是把没个数都存两遍,在random array存一遍,在sequential array村一边,但是sequential array里存的是index,不是数据本身(或者相反?我有点忘了). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
(4)MultiThread
本来以为第二次电面会是多线程的问题,没想到HappyNumber了,比较幸运,但是多线程的这个问题还是准备了很久,
我把当初整理的资料发上来:https://www.evernote.com/shard/s ... 906d67ab4ea189304f1
笔记里有题目的原题截图后来这个题在我onsite的时候问了,貌似这个体和网上面经里的task dispatch是类似的,相互替代
回答的时候先写简单的单线程的,再写个最简单的给整个函数body加锁的版本,
再指出问题在哪儿(当callback是register_cb的时候会导致程序死锁),再针对的改一改代码,时间过去了很久,我就不回忆代码怎么写的了,
大概思路是用一个全局的flag来表征是不是已经trigger过了,用一个Queue来存task,trigger之后也要注意检查Queue的size是不是0,因为多线程的时候可能导致有些callback加到队列的同时,flag被翻转了,如果不检查可能会导致有些callback没有被执行


. From 1point 3acres bbs
(5)manager
behavior question, why pure?

. From 1point 3acres bbs


. 鍥磋鎴戜滑@1point 3 acres



. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴



评分

3

查看全部评分

readman 发表于 2016-6-21 00:53:45 | 显示全部楼层
刚写了一个. 求bug

public static void clearBit(boolean[][] matrix,  int offset, int length) {
        int curLevel = matrix.length-1;
        int left = offset;. 1point3acres.com/bbs
        int right = offset+length;
        while (curLevel >= 0){
.1point3acres缃            for (int i = left; i <= right; i++) {
                matrix[curLevel][i] = false;
            }. 1point 3acres 璁哄潧
            curLevel--;
            left = left/2;.鏈枃鍘熷垱鑷1point3acres璁哄潧
            right = right/2;
        }
    }
    public static void setBit(boolean[][] matrix,  int offset, int length) {
        int curLevel = matrix.length-1;
        int left = offset;
        int right = offset+length;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        while (curLevel >= 0){
            for (int i = left; i <= right; i++) {
                if (curLevel == matrix.length-1)
                    matrix[curLevel][i] = true;
                else
                    if (matrix[curLevel+1][i*2]&&matrix[curLevel+1][i*2+1])
                        matrix[curLevel][i] = true;
            }
            curLevel--;
            left = left/2;. 鍥磋鎴戜滑@1point 3 acres
            right = right/2;
        }
    }

    public static void main(String[] args) {
        boolean[][] m = new boolean[][]{. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                    {           false},.鏈枃鍘熷垱鑷1point3acres璁哄潧
                {   false,                  true},
            {false,       true,        true,       true},
        {false, false, true, true, true,  true, true, true},
        }                      ;. from: 1point3acres.com/bbs
        setBit(m,0, 2);

    }
回复 支持 2 反对 0

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-6-5 09:59:48 | 显示全部楼层
最后那部分怎么莫名变成斜体了 还不能编辑。。有点怪怪的
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-6-7 02:54:54 | 显示全部楼层
楼主准备这么充分居然还会fail??!
回复 支持 反对

使用道具 举报

missing 发表于 2016-6-7 03:14:35 | 显示全部楼层
你写的比我的详细,感谢你的分享,我之前就从中学到了不少。然而我也跪了,新题+code写得不够快不够bug free。后面去面的人难度应该很大,没面经而且代码一次最优无错误是很难的
回复 支持 反对

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-6-7 03:25:31 | 显示全部楼层
missing 发表于 2016-6-7 03:14
你写的比我的详细,感谢你的分享,我之前就从中学到了不少。然而我也跪了,新题+code写得不够快不够bug fre ...
. visit 1point3acres.com for more.
嗯  刚看了眼你的帖子 看来又出新题了,这个信息很宝贵啊。
是啊,我觉的这几个题没面经没提前练习一下的话能答到面试官满意的程度确实很难,能流畅的follow面试官一点点优化就很不错了,画圆的那个题写到最后发code里现只用了一次乘法面试官才满意,当时我就惊呆了
回复 支持 反对

使用道具 举报

Urumic 发表于 2016-6-9 01:32:11 | 显示全部楼层
想问一下楼主buddy system 的资料里说的level update 而不是heap like update是什么意思啊
回复 支持 反对

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-6-9 04:21:21 | 显示全部楼层
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] -google 1point3acres
那么A[x][y]的孩子包括A[x+1][2y] 和 A[x+1][2y+1]
回复 支持 反对

使用道具 举报

Urumic 发表于 2016-6-12 02:18:31 | 显示全部楼层
进击的菜鸟 发表于 2016-6-9 04:21
heap就是说这个树存在一个一维数组里,满足A的child是A[2i+1]和A[2i+2]
level update:  比如有N个level ...

谢谢楼主!
回复 支持 反对

使用道具 举报

Urumic 发表于 2016-6-14 06:21:15 | 显示全部楼层
还想问一下楼主,关于Map那道题,面试官还有什么特殊要求吗?有没有空间上的follow up?
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-6-14 06:28:16 | 显示全部楼层
lz牛啊,请问lz是new grad吗?
回复 支持 反对

使用道具 举报

Urumic 发表于 2016-6-14 13:23:25 | 显示全部楼层
进击的菜鸟 发表于 2016-6-9 04:21.鐣欏璁哄潧-涓浜-涓夊垎鍦
heap就是说这个树存在一个一维数组里,满足A的child是A[2i+1]和A[2i+2]
level update:  比如有N个level ...

对了,楼主还想问你一下,第三题O(1)Map的sequential是什么意思啊?
回复 支持 反对

使用道具 举报

Urumic 发表于 2016-6-15 09:47:38 | 显示全部楼层
[quote]2 - performance,尽量减少乘法以及开方的使用数量
    (1)x从r变到0.717r 要比从0变到0.717r可以多画几个点, . 鐣欏鐢宠璁哄潧-涓
回复 支持 反对

使用道具 举报

Urumic 发表于 2016-6-15 09:48:52 | 显示全部楼层
进击的菜鸟 发表于 2016-6-5 09:59. visit 1point3acres.com for more.
最后那部分怎么莫名变成斜体了 还不能编辑。。有点怪怪的

请问楼主,第三条元的斜率指的是点和圆心的连线吗?.鏈枃鍘熷垱鑷1point3acres璁哄潧
.1point3acres缃
[quote]2 - performance,尽量减少乘法以及开方的使用数量.鐣欏璁哄潧-涓浜-涓夊垎鍦
    (1)x从r变到0.717r 要比从0变到0.717r可以多画几个点, . 鐣欏鐢宠璁哄潧-涓

补充内容 (2016-6-15 09:49):
额,这个回复怎么不好用。。。
回复 支持 反对

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-6-19 02:54:18 | 显示全部楼层
Urumic 发表于 2016-6-15 09:48
请问楼主,第三条元的斜率指的是点和圆心的连线吗?.鐣欏璁哄潧-涓浜-涓夊垎鍦

[quote]2 - performance,尽量减少乘法以及开方的 ...

不是,是指切线的斜率
回复 支持 反对

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-6-19 02:54:50 | 显示全部楼层
Urumic 发表于 2016-6-14 13:23
对了,楼主还想问你一下,第三题O(1)Map的sequential是什么意思啊?

类似于linkedlist,顺序存储的那种
回复 支持 反对

使用道具 举报

Urumic 发表于 2016-6-20 07:17:35 | 显示全部楼层
进击的菜鸟 发表于 2016-6-19 02:54
类似于linkedlist,顺序存储的那种

谢谢楼主。请问楼主onsite还是两次吗?
回复 支持 反对

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-6-20 09:52:24 | 显示全部楼层
Urumic 发表于 2016-6-20 07:17
谢谢楼主。请问楼主onsite还是两次吗?

一次都面了,可能是因为我在东海岸,飞两次太麻烦了,所以一次都面了。然并卵,还是挂了,你要面了么,加油,希望这些面经可以帮助到你。
回复 支持 反对

使用道具 举报

Urumic 发表于 2016-6-20 12:04:06 | 显示全部楼层
进击的菜鸟 发表于 2016-6-20 09:52. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
一次都面了,可能是因为我在东海岸,飞两次太麻烦了,所以一次都面了。然并卵,还是挂了,你要面了么,加 ...

是啊,快要面了。感觉不好过的应该是那个聊天。最后那个聊天都会问一些什么样的问题啊?
回复 支持 反对

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-6-20 12:37:03 | 显示全部楼层
Urumic 发表于 2016-6-20 12:04
是啊,快要面了。感觉不好过的应该是那个聊天。最后那个聊天都会问一些什么样的问题啊?

那个就随便聊聊了,为什么对pure感兴趣 主要是你问他,可以问问产品相关的 基本是走形式的一轮
回复 支持 反对

使用道具 举报

Urumic 发表于 2016-6-21 00:05:27 | 显示全部楼层
进击的菜鸟 发表于 2016-6-20 12:37
那个就随便聊聊了,为什么对pure感兴趣 主要是你问他,可以问问产品相关的 基本是走形式的一轮

好的,谢谢楼主。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 16:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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