PureStorage Multithread Phone Question

Updated Oct 28, 2017-------------------------------------------------------------------------------

http://www.1point3acres.com/bbs/thread-192327-1-1.html

吐槽一句，这种万年不变面试题目的风格，真的好吗。。。

Background Read:

http://blog.poxiao.me/p/multi-threading-in-cpp11-part-1-thread-and-future/

C++多线程总结：http://www.cnblogs.com/zhiranok/archive/2012/05/13/cpp_multi_thread.html

Mutex and Cond Variable:

感谢一个叫Lilly的同学弄的截图：

网上帖子的总结

1-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...现在多线程这么弱）

然后时间差不多了...说你有啥问题吗...

exactly, 我就是这么做的，async的queue，加一个全局flag，多线程就是mutex，lock unlock，期间多线程的时候有些错，他提示改过来了，我多线程比较弱，后来挂了。加油！

1.1http://www.1point3acres.com/bbs/thread-128619-1-1.html

第一轮问的是一个api，每次register的时候需要call一个callback，但是在event被触发之前call的callback都不能成功被call，在event被触发之后call的都可以，同时之前delay的call也要成功call，让写具体的function如何work。还问了multithreading的问题。

第二轮是类似LRU cache的题目。

1.2http://www.1point3acres.com/bbs/thread-133917-1-1.html

第二轮面试， 面的是register那题，论坛里有，代码很简单，但是关键是要回答多线程下，应该要怎样弄，然后楼主悲剧了，我明明回答的跟面试官给的答案是一样的，但是他就觉得我的不对，我就呵呵了。祝大家好运。

1.3 Good Discuss:http://www.1point3acres.com/bbs/thread-134409-1-1.html

我面过，电面就是一个api，每次register的时候需要call一个callback，但是在event被触发之前call的callback都不能成功被call，在event被

触发之后call的都可以，同时之前delay的call也要成功call，让写具体的function如何实现，之后还实现单线程多线程来着。

1.4http://www.1point3acres.com/bbs/thread-176123-1-1.html

是一道多线程的题目。

大致意思就是实现回调函数的两个interface，分别是register(event) 和 fire_event()。每次call第一个函数应该把event存起来，直到第一次call fire_event()的时候之前所有存的event都要call一遍，并清空存储的event。之后所有的register(event)需要立刻执行event而不是存起来。题目本身只需要一个flag和一个vector就行了，但难点是线程安全。注意所存的event可能是register或者fire_event本身。面到最后实在是有点晕，已经被面试官提出的各种奇怪的情况弄的意识模糊，比如这里加个锁会怎么样，那里change value又会怎么样之类的。虽然最后写出了正确的代码，但在最后关键的步骤卡了太久，不出意料挂了。

1.5 A summary:http://softwarecareerup.blogspot.com/2015/03/pure-storage-interview.html

1. Which number can be represented as two decimal?

2. How to implement mutex using spinlocks and flags.

3. How virtual functions work

1.6 http://www.1point3acres.com/bbs/thread-133456-1-1.html

有两个API, 一个是register event, 另外一个是fire event, 当fire event之后之前的register的event也要执行, 多线程调用的时候怎么办

缃�

2-http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=116339&page=1#pid1696477

• 对concurrency,lock这些只了解概念，面试的时候让我实现一个锁
• 感觉Pure很看重multi-threading这些的，quiz考thread-safe stack，interview也考多线程

3-http://www.1point3acres.com/bbs/thread-148340-1-1.html

看一个数是否是pure number

仅一道编程题，在coderpad上编， 语言随意。

题目简单，但是三哥interviewer后续问了好多问题。比如说存储考虑，边界条件还有数学问题等等。

问的太杂了，感觉他是随便想随便问的，有些问题很跳跃

总之交流还不错

我是用detected cycle 方法写的，他的问题基本上是围绕我这个方法问的。假如有一个数每一次计算都是一个新的number， memory不够怎么办。会不会有找不出来的情况。memory足够的情况怎么证明一定找得到，我说因为大的数每一次计算会缩小，最后到达一个范围。然后让我证明，证完让我求出那个范围的临界值……大概是这样

新题:

给一个文件，reverse里面内容char by char。

Example:

Input File Content: ABCDEFG

Output File Content: GFEDCBA

读写同一个文件。文件很大，需要读chunk by chunk而不能全读出来, reverse再写回去

Follow up Question：

如果在reverse或者写入过程中systemcrash，那么怎么保证内容正确重新正确写回去。.鐣欏璁哄潧

感觉答的不好，一开始写完的没有能过test case，改了两次还是不能过全部test case。意识到错误后重新design的算法，不过没时间了，只是口头解释了一下。Interviewer还是比较满意最后这个做法。

4- 一个下属部门

1. 设计一个malloc 函数 void *malloc_aligned(size_t size, int align), align是任意的bytes，返回一个用系统malloc生成的但是起始地址必须按照align参数对齐的地址。一开始就题目意思没理解清楚，还好很快改正了，大致思路就是预先多开辟一点空间，然后修改系统malloc返回的地址来满足条件，这样会导致一些多余的地址也被开辟，形成一个offset。

于是follow up，写一个对应的free函数正确释放这个malloc_aligned安排的空间，free本身不提供任何参数，当时就傻眼了，没参数这怎么活。。。后来支吾了半天对方提示可以适当保存一下offset参数，遂想到把offset当成一个int存在malloc_aligned返回的地址前一位，这样其实需要修改相应的malloc_align（尼玛你也一开始没说怎么修改malloc_align）。

这个问题唧唧歪歪完再写完大概只有25分钟左右甚至更少了，本觉得接下来应该可以轻松一下了，开始问知不知道binary search tree，刨了一通基本概念诸如各种操作复杂度云云，又一个问题还跟他争论了一下，结果只剩15分钟左右了，说写个valid binary search tree，说了个最基本的recursive解法，不满意，遂说利用inorder traversal打印成array, 吭哧吭哧写完又说空间复杂度不好，然后纠结了一阵（LZ并没有准备到这步，后来看geeksforgeeks上面居然有）才写完了不利用array的，超时了5分钟。已经心力憔悴了，就没什么心思问他问题直接结束了。

面完觉得就是这面试官问的又多时间又紧，至于之前扯的什么C++概念一个没问，这跌跌撞撞的表现肯定是没戏了，发个面经给接下来攒攒RP吧。

5- 没见过的题；http://www.1point3acres.com/bbs/thread-138406-1-1.html

西雅图office：http://www.1point3acres.com/bbs/thread-141925-1-1.html

两轮电面， 一轮问了一个多线程题，记不清，读写同步，第二面问了Roman to number