Pure Storage

画圆经典题。followup: 如果像素点较少怎么办。
利口六六一
-------------------

https://www.1point3acres.com/bbs/thread-475566-1-1.html


小印面试官全程冷冰冰，没有交流，感觉开始就要fail我的样子

if (n%2 == 0) n = n/2

else n = 3*n + 1

3 --> 10 --> 5 ---> 16 ---> 8 ---> 4 ---> 2 ----> 1

总共需要7步

写一个函数计算步数，系统可能要call 几百万，所以需要计算这个步数更快



关于第二题 既然bottleneck在速度 我目前只能想到


(1) 不要recursively 要iteratively 因为arithmetic ops太cheap了 much lower than recursion overhead.


(2) For even number, simply use shifting ops 因为移位是底层arch实现里几乎最简单的操作了 比加法还快 while (x&1) { x = x>>1; ans++; } arch pipeline移动一步就可以做一个iteration了 没什么继续加速的必要了


(3) For odd number, simply use x + (x<<1) + 1， 两个加法和一个移位，也是底层arch里最简单的操作之一 结合(2)(3) 应该是快得要飞起来了 pipeline走几步就做完一组了


(4) 要考虑一下是不是一定有解 这个数学上证明一下就好 很简单的反证法 如果我碰到这题 肯定会主动证明这个结论


(5) 要是可以数学上估计出step的upper bound就更完美了 我没想出来



--------------------

https://www.1point3acres.com/bbs/thread-298316-1-1.html


valid square 给平面上四个点，判断是否能组成一个正方形。每个点是由（x，y）坐标表示。follow up是给n个点，问可以组成多少个valid square，要求先O(n^4)，再改进到O(n^3)，最后改进到 O(n^2)
event fire https://instant.1point3acres.com/thread/177053 https://www.evernote.com/shard/s260/sh/a01e5b26-d3eb-44c0-8ef4-01086605f675/da31dd196df57906d67ab4ea189304f1
bitmap http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=226030&extra=page%3D127%26filter%3Dsortid%26sortid%3D311%26sortid%3D311


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


画圆 可能需要用数学方法证明解法的正确性 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=192327&extra=page%3D43%26filter%3Dsortid%26sortid%3D311%26sortid%3D311 https://www.cs.uic.edu/~jbell/CourseNotes/ComputerGraphics/Circles.html
implement O(1) set https://instant.1point3acres.com/thread/177053
image smooth 这篇帖子说要求in place http://www.1point3acres.com/bbs/thread-138406-1-1.html-baidu 1point3acres


另外一篇帖子里又说 in place 行不通 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=202635&extra=page%3D5%26filter%3Dsortid%26sortid%3D311%26sortid%3D311


align rectangle/textbox http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=202635&extra=page%3D5%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
c++ virtual table 相关知识 https://www.evernote.com/shard/s260/sh/dfc7453b-e50f-46c0-b223-196bead364a9/c41f1cea8f38c1802d1941338b03d375
call api http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=192290&extra=page%3D109%26filter%3Dsortid%26sortid%3D311%26sortid%3D311 http://www.1point3acres.com/bbs/thread-206999-1-1.html
sort color (3-way partition) 要求swap次数最少 http://www.1point3acres.com/bbs/thread-206999-1-1.html
which number can be represented as two decimal http://softwarecareerup.blogspot.com/2015/03/pure-storage-interview.html
implement lock http://softwarecareerup.blogspot.com/2015/03/pure-storage-interview.html
happy number LC 202 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=192327&extra=page%3D43%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
memcpy, memmove http://www.1point3acres.com/bbs/thread-206999-1-1.html
fibonacci number both iterative and recursive http://www.1point3acres.com/bbs/thread-141925-1-1.html
coin change LC 322 http://www.1point3acres.com/bbs/thread-141925-1-1.html
min stack http://www.1point3acres.com/bbs/thread-141925-1-1.html
LRU cache， Skyline， Permutation, combination sum, roman to int
What data structure would you use to construct a skip list? Implement search() and insert(). http://www.cnblogs.com/binyue/p/4545555.html http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html http://www.sanfoundry.com/java-program-implement-skip-list/
thread-safe stack 多线程下的stack的push和pop，好像只有校招会碰到。