Prepare Software Engineer Interview

https://sites.google.com/site/careerofpsyclaudezintheus/

随时记得我的职业规划 Online Practice LeetCode CareerCup 150 九度及剑指offer July的面试题系列 ITInt5 做TopCoder以前的不同类型的题，参考http://www.hiredintech.com Quora上关于what are the best programming interview questions that you have been asked? link Side Projects! 当然其实最好是跟自己研究兴趣相关的，或者训练技能相关的。 Karan's projects Martyr2’s Mega Project List Don't have any idea? Check out Andrej’s page link Open source contributions ONGOING Add Konami code resources: link1, link2 Add projects page Analyse the passwords + d3 visualization MapReduce sorting duckduckgo, pluggin or Chrome extension python crawler Django Columbia million song dataset Bayesian Methods for Hackers Columbia CV & ML on mobile platform course!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! NYU - Path mobile app Reading Programming Inverview Program creek, link Intern tag on the forum of Careercup.com link Research Thrashing的意思 Courses Database on udemy Refer 王聪可以内推 Walmart lab link LinkedIn data scientist/engineer link LinkedIn link Amazon link Twitter link link link link (说一周内) SalesForce link Yahoo link link (data ads) AWS link Bloomberg link 一亩三分地上的内推 Yahoo,  Twitter，Amazon都在这个网站上面： https://plzrefer.me/jobs/ Yahoo link Groupon link Programming Challenges from Companies Link to the Quora page Preparations Online Problems LeetCode ITInt5 Geeksforgeeks Lots of questions on programinterview Tips Cornell 8月Google的准备技巧 Lessons from a Silicon Valley job search, 具体的事前、事中、事后！ 魏小亮的一些经验，http://blog.sina.com.cn/s/articlelist_2280861907_0_1.html 算法准备，里面还有面试的链接！http://zh.lucida.me/blog/on-learning-algorithms/ Nice Problems Collection from LeetCode (deprecated, I have started using pen and paper for coding and taking notes) Impressive Ones Permutation Sequence: 1）当不能使用额外内存时，考虑递归！2）永远不要忘了考虑负数的情况！ Minimum Depth of Binary Tree：跟maximum不一样！空节点的情况要单独考虑！ Linked List Cycle: 多种情况！ Remove Nth Node From End of List：多种情况！自己想的用一个哨兵的方法相当不错！不过不要忘了取消的那个环…… Permutations：自己把康托展开推出来了~ Best Time to Buy and Sell Stock：注意扫一遍求最小值的方法！ Gas Station：虽然识破了是最大子段和，但不要忘了它是环状的！ 3Sum，2Sum：双指针！ Path Sum：本来是很水很水的题，但因为多考虑了优化结果就忽略了加负数会更小的情况！ Unique Paths II：边界条件多！ Remove Element: 体会in place思想 First Missing Positive: 虽然这道题条件给得太TM少了，直接无视它的要求排序搞之……但还是要知道所谓“解题报告”中所提到的用原数组作为hash table的方法。 Subsets: 注意非递归的方法！还有就是要考虑输入为乱序的情况！ Sort Colors：注意只扫一遍的算法！和Qsort类似！ Populating Next Right Pointers in Each Node: 我真是傻逼！！！！！！！！！！！！！！！！！！！！！！！！不过确实需要体会“使用题上提供的指针“！ Surrounded Regions: 不要搞忘写引用符号了…… Merge Two Sorted Lists:注意链表尾巴的情况 Swap Nodes in Pairs: 为何我来做边界情况就那么多？！？！想清楚！！！ Pow(x, n): 注意负数！！！而且不存临时变量耗时更多！！！！！！！！！！！！！！！ Rotate Image: =.= 居然耽误了这么久！！！！！！！！！！！！！！！！！！！！！！！！！！！！！注意并不是一排的所有元素要换！最后一个角落里的不用！！！！而且注意画图！！ 3Sum: 考虑数字相同的情况！！！！！一方面是i！！！！一方面是j和k！！！！！！！！！！！ Merge Sorted Array: 注意从后往前处理的思想 Convert Sorted Array to Binary Search Tree: MLE居然是因为函数传参用的是vector<int> num而不是vector<int>& num！！！！ Binary Tree Maximum Path Sum: 值得一看，因为不完全是自己的想法。其实用的还是暴力方法…… Restore IP Addresses:  0的情况！！！前导0！！！！！！！！！！ 手打stirng to int的时候，注意1000的情况！！！！！ans = ans * 10 + i不管用！！！ 晕！我是猪，其实没有问题！！只要从高位往地位走！！ Sum Root to Leaf Numbers: 注意这种在递归函数中包含引用参数的方法！！ Gray Code: 这道题学到的重点是！在统计数组中某种元素个数时，不要把切换统计数字变量和统计数字操作（cnt++）放在同一个if else里！最好是两个并列的if！！！ Search in Rotated Sorted Array: 好题！！！考虑的条件很多！！！ Binary Tree Level Order Traversal: 这类题，如zigzag类都不要忘记了最后bfs完了后，buf里面还有最后一波没有push进去的节点！ 改进版的写法！以后都那样做！！！！保留next和cur两个queue Length of Last Word: 边界情况…… "", "a", "  a  ", " " Spiral Matrix: 类似的题都可以考虑使用向量dir[4][2] Flatten Binary Tree to Linked List: worth redoing!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 3Sum Closest: 记住最安全的最大值或最小值的初始值是那些数组中已经存在了的！ Longest Consecutive Sequence: unordered_map是O(1)的access complexity Jump Game II: 再想一遍 Implement strStr(): 字符串注意NULL和""是有区别的！！！！！！！！！！！！！！！！！！！！！ LRU Cache: 太…… 学了很多 struct的（）初始化操作 模块化！！模块化！！！即使是一道非实际题！！！！！ 虽然p指针考虑了不为tail，但它的next也需要考虑！ 每次使用->操作符时，问一下自己是不是空的！！！！！！ Search for a Range: 自己做的时候在n = 2的子问题是遇到了一些麻烦，后来看题解才发现其实搜索的时候只用关注一个if！！！ 4Sum: 注意重复的处理！ Permutations II: 跟上面的一样！注意重复的处理！ Edit Distance: 注意初始化边界条件 Interleaving String: 依然是DP，注意边界条件 Copy List with Random Pointer: 这里居然用到了hashmap Word Ladder: 刚开始bfs时用的是遍历所有dict！其实只要遍历字符串中每一个元素，把它变成另外一个字母然后看在不在字典中就行了！！ Multiply String, 用的是python，一行搞定……要重新写一遍！！！！ Distinct Subsequences: 注意DP循环的方向！！！因为用的是滚动数组，所以要从后往前扫！！！！！注意注意！！！ Integer to Roman: 总的来说，其实是一道简单题……注意的点： rule：http://projecteuler.net/about=roman_numerals 注意1000，100，10是不是可以减去500，50，5 注意900，90，9可不可以通过减构成 然后重要的是！每生成一个新数要break当前循环！！！！！ Reverse Words in a String: 其实边界情况都想到了的，就是没有注意j在while循环的时候也要<n啊！！！ Decode Ways: 忘了考虑'0'的情况！！！！！！！！而且把'0'写成0了！！！！！ String to Integer (atoi)： 看清题……|INT_MAX| = |INT_MIN| - 1， 不要忘了考虑正号的情况！！！！！！！！！！！！ 如果是long long的常数要加LL！！！！！！！！！！！！！ Populating Next Right Pointers in Each Node II: 与等分最高的答案差不多，但自忖可读性更强 不过最开始用的 while (root != NULL) {不断向左}以及while(root != NULL){不断向左，不行？向右}都是错的……因为却是不能保证扫到每一个！！！ Word Search: 只能说少年你想多了……直接暴力就行了 Unique Binary Search Trees II: 其实是很简单的题啦！！！！！只不过因为I的思维定势，一直在想一维的情况！其实每一个n是有一串的！要用二维数组！！！！另外，leetcode诡异的错误：把NULL push进vector时，要用nullptr…… Remove Duplicates from Sorted List II: 简单题，不过记得用O(1)的内存的迭代和递归方法做！ Minimum Window Substring: 好题，要细致！思路一直是对的，只是第一遍写的时候虽然是O(n)但是可能是因为常数太大所以在最大用例上一直超时……后来发现，其实用不着发现窗口之后每次只移一次lo——而是一口气把它移动到最后的位置，然后更新。这样就快多了！要重做！ Reverse Nodes in k-Group: 看破玄机轻松A过。不过最开始搞忘cur = cur->next了……=.= Convert Sorted List to Binary Search Tree: 简单，小笔误。 其实可以O(N) instead of O(logN)!!!!!!!!!!!!!!!!!!!!!!!!!!!!! link Count and Say：只能说太猪，还是太晃…… Candy: 正反求一遍下降，然后取各点最大。不过要注意 [1, 3, 4]这种输入，求出来是[1, 1, 2]！！！所以要看如果是比前一个大的情况的话，还要再取前一个的值的最大！！！！ Max Points on a Line: 注意重复的点！！！！注意size = 0和size = 1以及size > 1，最重要的是！注意不要忘了type cast！！！！！！ Divide Two Integers: 贱B题！！！！注意负数的情况！！！！还要注意int从负数转成整数溢出的(-2147483648)情况！！！我日！！！！ Palindrome Partitioning: 日他娘的臭傻逼题！！！！！！！我也很傻逼，因为太他妈多字了，脑子又是晕的。要重做！！！ Palindrome Partitioning II: 比上面的简单不过要注意 DP是中间加一句判断会问会让复杂度*n！！ 用一个预处理的palin表 trial and error类的 Valid Number: 唔…… 空格的情况！ 只有空格的情况！ 还要注意. e的数目不能太多 其他的都还好。不过Java还挺好用，trim、split Wildcard Matching: 看的题解很好！注意“保存上一个*位置”的方法！ Regular Expression Matching: 这个是用递归了~不错！！！ 这几道求面积的题可以做一个小分类了： Largest Rectangle in Histogram：很经典的用stack解决，这个解析写得相当棒 Maximal Rectangle: 会做上面这个，这个就能做了！相当于跑|column|次上面的O(n)算法！ Trapping Rain Water: 注意扫描求左边和右边的方法，因为是求总的面积，所以用不着上面的直方图法！！！ Container With Most Water: 这个又不一样！！这个的两个边界是可以无视中间障碍的！！ SPOJ CITY2，变体 区间的题 Merge Intervals：简单贪心…… Insert Interval: 几乎完全一样，但是用例没有输入的interval是非法的情况！！！！！！！！！！！！ ITInt5 4. 统计完全二叉树结点个数：二分法~ 35. 字符串转义：只要是指针就要判断NULL，即使是char *字符串！！ 38. 有序矩阵搜索~ 43. 两有序数组的交和并：注意边界情况！！注意输入是数组可以有重复输出是集合！！！还要注意其中一个为空和两个都为空是不同的情况！ Collection from CTCI150 Impressive Ones 1.1: 注意询问UTF, ASCII；位操作；  1.3: 每当要计字符数时，都要问清楚是不是只有ASCII！！！！ 3章： stack操作不要忘记了每次check isEmpty（）！ 注意类之中的数据结构，是没有初始化的！！！ 3.7!!!!! 注意面向对象（继承）思想的运用！！！！！！！！！！！ 4.3: minimal height就是每次用中位数来做节点！！！ 4.5: 递归函数中传递上下界的方法很好！ 4.6: TRICKY！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ 4.9: 注意找到了2 + 3并不算结束，也许还有2 + 3 + -2 + 2！！！！ 5.6: 0xaaaaaaaa, 0x55555555 5.7: 分类讨论！ 9.10: 注意刘汝佳教的DAG方法！先建图，再DP 10.2: 信息不能存在单一机器上，所以应该maintain一个id list 10.5: 想到hash不难，难的是想到url并不能唯一地identify一个网站！！！用相似性！ 10.6: 可以把一大堆的文件分成几个chunk，对于每个chunk，顺序读取然后存到一个文件whose name is file_xxx，where xxx is the hash number。所以最后所有文件都被分割了~ 11.6：O(m + n)的方法很好~！ 12.1: So damn tricky... 12.3: Not only the specific test cases, but also the GENERAL CASES! More black pieces, more red pieces etc. Also, generate bunch of pieces and let them move spontaneously  14.1: Cannot be inherited! 14.2: Some cases final block will not be executed: the thread is killed  the virtual machine exits 14.3 : final的用法 1. primitive variable -> value cannot change 2. reference variable -> cannot point to other variable 3. method -> cannot be overwritten 4. class -> cannot be subclassed  14.5: reflection 用来查看runtime application 用于测试 call method by name even have no idea of the name Bit Manipulation 三种clear bits的方法 num & (~(1 << i)) 一个bit num & ((1 << i) - 1) 从高位到i位 num & (~((1 << (i + 1)) - 1) 从0为到i位 allOnes = ~0 OOD AMBIGUITY Singleton Class and Factory Method Memory and Scalability 类似的题关键是要想到“不能存在单一的机器上！！！” Testing Test both COMPONENTS as well as INTEGRATION with other modules Breakdown the structure instead of speaking out anything that comes into the mind Black box and white box testing Procedures of Testing Software Black-box or white-box Who and Why use it Use cases Bounds of use Procedures of Testing Functions Test cases extremes Nulls and illegal strange (ordered list) Expected results Write test code Collection from 何海涛100题 1. 二叉树转双向链表：a. 递归，每次找左链表的尾和右链表的首；b. 中序遍历！ 15. 含有指针成员变量的类拷贝：因为指向同一个地方，如果其中一个被释放了，另一个也会。解决办法：deep copy，reference count 16. O(logN)求fibo：矩阵幂，二分递归 [1 1, 1 0] 22. 二进制1的个数：单纯右移数字，如果是负数会死循环！！！左移1，或者！！减1比较！！！ 25. 1到n数字1出现的次数：为什么递归呢？直接数学法不行吗？ 26. 和为n连续正整数序列：类似2sum！！！ 29. 调整数组顺序，使前一半XXX，后一半!XXX：前后两个指针，比如前面必须奇数后面必须偶数；前面指针遇到偶数且后面指针遇到奇数，交换 30 32. 不能被继承的类。西西西，Java是final的类不能，那C++呢？ 33. O(1)删除链表节点：简单，但是注意！如果是链表尾的话，还是要O(n)【从头搜起】 35. 单链表的交点，肯定是Y形不是X形！！！！！！！！！！ 47. 出现次数超过数组长度一半的数 55. 用位运算完成加法，不错！ 60. 判断是不是平衡二叉树，后序遍历的话求深度就不用啦~ Collection from EPI300（abandoned, notebook） Chapter 1 ~ 3 different schedule available if interviewing finance firm, probability and discrete math are important Collection from CareerCup.com From Interns Tag sizeof is a keyword in C/C++ Assuming there's no Array data structure in C, how would you implement it. malloc continuous memory, and use a pointer Three people, want to know average without knowing others': Person1 picks a random num, plus to his num, tell second ... 1->2->3->4 to 2->1->4->3: a few lines of code, recursively pick the consecutive pair of nodes Majority vote algorithm: cnt := 0, sweep, when a[i] is different from candidate, --cnt, else ++cnt if cnt == 0 change candidate Google 4096buffer link（直接搜read 4096也有） word search II，在word matrix里面word出现了几次 无向图的“三角形”，矩阵乘法 link http://www.careercup.com/question?id=5094709806497792 Facebook Amazon Collection from glassdoor Google: reverse the bits of a number link Collection from mitbbs peking2的面试题总结 link Trapping water同类题 http://www.mitbbs.com/article_t/JobHunting/32772225.html http://www.mitbbs.com/article_t/JobHunting/32772813.html 组织成 a1<a2>a3<a4>a5... http://www.mitbbs.com/article_t/JobHunting/32769375.html sally的模板非常适合conditional sliding window！！！！ Facebook F家的整理 link link link interval的题link LinkedIn link link 杂 买买提上ebay的整理 link Collection from StackOverflow & Geeksforgeeks Find an integer not in 4 million given ones: link BST里的2-sum: link Ugly number: link Rearrange the array such that positive and negative numbers appear alternatively. link 评论里面说得好，用类似快排的整理方法把数组分成<0和>0两个部分，然后两两交换！！！！ kth smallest in matrix (col, row both sorted) link kth smallest pair sum in 2 sorted arrays (similar to the above) link kth smallest in BST link Rolling median of integers link1 link2 内存无限 - 两个heap 内存有限 - 计数排序。而且最好是每16位每16位来~！ 相交最多的区间 link 圆上有N个点，圆外有一个点，求最近距离，bsearch link 判断是否存在一段连续子序列whose sum is k link count 连续子序列whose sum is in a range link 如果要print的话，不可能低于O(n^2) seg tree 若全正，bsearch 5^123192038102389102389 O(d^2 logp) link LCA BST和普通BT，link link 判断线段相交 link circular kadane link, 思路很巧妙啊！！ Collection from TopCoder, Hackerrank Zigzag path (div1 1)，找出最长的一条相邻差值为正负正负的数组 LIS，只不过条件换成了inc[i] = max{dec[j] + 1}, dec[i] = max{inc[j] + 1} data stream的中位数 最初的两个,小的到大根对，大的到小根堆 接下来每进来一个元素，比较： 如果比大根堆的根大，进这个；否则进小的 平衡两个堆，使得长度差为1（通过remove heap top） HackerRank, cut the tree：面试，还可以的DFS HackerRank, bus station: 面试，注意质因数的思想！ Collection from POJ, UVa, SPOJ, etc. SPOJ  BUGLIFE: 二分图就是这样搞的啊……还是要用广搜！ GCJ101BB: 面试,　要换个思考角度，好题！ CODESPTB: 唉……一个求逆序数写那么久…… KNJIGE: 面试, 特殊排序 LOOPEXP: 很好的thought problem！！！ NGM: 对于组合游戏题, 不要忘了可以用观察法!!!!!!! MAXSUM: 面试, 题意不清楚, 不过要考虑的情况有一些~ ANARC09A: 面试, 括号匹配 THEATRE: 面试, 感觉这种用堆解决的题已经有点熟悉了~ 双指针或sliding window CRAN02: 中高难度面试题 CRAN04：面试题，边界怎么搞啊~而且还要注意0的情况！！！！！！！！！ UOFTCC: 面试，sliding window，写了好多遍才写对…… 3663 - 2 sum加强版，求所有小于的对数，面试题 用的二分，但其实可以： if (num[lo] + num[hi] <= tar) { ans += hi - lo; ++lo;} INUM: 面试好题！！！，数组中的最小差的个数，最大差的个数。好题！！！注意几种情况 全部相等 length = 1 最值有重复但不是全部相等 NOTATRI: 面试，3 sum加强！跟上面的3663一样~ 字符串 JAVAC: 面试字符串题，有个别情况没考虑到！ NHAY: 可能的面试, KMP~注意, 这道题的启发是:做KMP时其实不用知道haystack的长度! POJ_2406: 可能的面试，KMP!!!最小重复子序列！！！NND next数组还能这样用!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! IITKWPCJ:同上！！！！！！！！！！！！！！！！！！！！！！！！！ BEADS和MINMOVE:面试，O(n)的找所有rotation中的最小表达！！！！很好，每次位移不是1而是i + count + 1!!!!!!!!!!!!!!!!! IITKWPCA: 面试，STL的istringstream！！！！用来split以及转int，但注意！！！必须写成要么while (iss >> s) 要么写成do { iss >> s} while (iss)!!!!!!!!!!!!!!!!!!!! IITKWPCE: 面试，预处理所有的回文O(n^2)，然后DP 数据结构 TREEORD: 面试, 还是二叉树还原.又TM出问题了: 注意递归的时候用lo hi!!!!!!!! 注意还原过程中cur在当前递归中++!!!!!!!!!!!!!!!!!!!!!!!!!!!!! RMID: 面试，堆 写rm的时候又出bug了……记住用INT_MIN作为哨兵的时候，后面比较e[l]和e[r]应该用lv和lr来比较！！！！！！！！！！！ BRCKTS2: 面试，栈，注意深度和高度的处理！！！！ UVa 10608, 并查集 - 要注意的是最后一次union可能会漏掉路径压缩，所以要记得在处理完后进行统计时, 用find(x)而不是parent[x]!!! IITKWPCI: 面试考过，并查集，网上都TM是些DFS，何必呢！！很涨自信的一道题，不过不要忘了查询的时候用find(x)而不是p[x]，跟上面一样…… ARRAYSUB：面试，minElem() for a queue！ 约瑟夫 ANARC08H: O(n)需要秒推，O(klogN) -> link 面试 WTK: 小变种 面试 DANGER: log(N), 面试 位运算 CODESPTA, 注意补码怎么换算的！！！以及怎么用公式算多少个1！！！ NR2, A ^B = (~A & B) | (A & ~B) = A\bar{B} + B\bar{A} 贪心（其实很容易出现在面试吧）： MSCHED：怎么贪，什么顺序贪 POJ 2392 - 比较有趣的背包，主要没有见过这样跟贪心结合的、上限不一样的背包 小专题，时间区间贪心 BUSYMAN: 简单的题， BYTESE2：类似，注意理解“跟谁是谁没有关系，重点是进和出”!!! MSCHED：怎么贪，什么顺序贪 高精度 MINNUM: 其实挺简单，只用考虑关于9的高精度。不过忘了考虑0了…… 搜 ALLIZWEL: 简单题，写得很漂亮，但是最开始搞忘回溯vis啦！！！！！！！！！！！！！！！！ MTREE: 面试的树搜 学到了O(n)的方式表示一颗树，且找寻各节点的复杂度跟邻接矩阵一样！没有借助STL 搜的时候（或者说DP的时候）要想到：如果边作为状态不行，那就试试节点！ 老是WA的原因是数组没开够！！！！要<<1，因为是无向图！！！！！ 总之是一道好题！ GCJ101C: 难面试题，很好的二分查找，不过其实有one-liner EKO: 面试, 二分找上限~ CLEANRBT: 面试, 很好的BFS + DFS!!! LABYR1: 面试, 求图的直径! 只用DFS两遍!!!!注意跟树的直径的区别!!!!! SUMFOUR: 面试, 二分查找，用的upper_bound和lower_bound…… GCPJ11J: 面试, 求图的中心距,其实跟直径是一样的道理!!!!!! MLASERP: 面试，好~最小转弯数~ CHASE1, 中难题，BFS+探圈 图论 MICEMAZE: floyd好久没做过啦,还wa了一次~ 注意多重边 注意不连通图 注意如果用-1表示不连接, floyd的时候要 m[i][k] != -1 && m[k][j] != -1 && m[i][j] < .. || m[i][j] == -1 数学题 GAMES: gcd，注意数学题的理解呀！！！ ROBBERY2: 简单题，但是调了起码3个小时……不要在脑子里面想！！visualize！！！！注意0，1下标问题！！！ VENOM: 本来很简单！！但是没有想清楚对称轴！！！其实只有一个二次方程解啊！！！！！！！！！！！！！！！！！！！！ UVa 10910: 注意ad hoc求组合数的方法！！！上下都是n个！所以一个循环就能搞定！！！ ASCDFIB: 其实比较简单不过要注意1：是取了余之后的排序！！2，虽然有1000000个数，但只用找100个！这时候那需要sort啊，用partial_sort(begin, begin + mid, end)!!!!!!!!!!!!!!!!!!!!!!! DP MBEEWALK: 注意六边形也是可以用笛卡尔坐标表示的~ IOIPALIN: 注意等长的LCS是可以滚动数组的 FISHER, FPOLICE: 变种背包！ SAMER08D: 面试，进阶lcs。注意最优解不一定只出现在最后循环终止的时候！！！！过程中也可能会出现！！！ PERMUT1, 面试 TRIP, 面试, 用了很多STL BACKPACK: 很好的背包问题~问题不复杂，但是写起来挺复杂~ DSUBSEQ: 好题,面试,注意跟leetcode的区别! 另外,要注意mod < 0的情况 PAREN: 面试, catalan (表达式的不同求值顺序总数) + 区间DP MPILOT: 好啊好啊！！！又学到一种新的方法表示状态！！！dp[i][j]表示已经取了i个，并且第一种类型物品比第二种类型的多j是的数目！！ POJ 2392 - 比较有趣的背包，主要没有见过这样跟贪心结合的、上限不一样的背包 UVa 11450: 背包，注意滚动数组的时候，如果不是要求最大值而是只能由上一个状态传递过来的时候，第二次到ks[0]的时候，它可能有些地方是有值的！！！ SCUBADIV: 面试, 简单背包.第一次做这种多维容量的,看来做法跟我想象的是一样的. GCJPURE: 好题, 中题! GCJ1C09C: 好题，不过因为tmp的初值设错了所以WA了一次…… GCJ121CC: 好题, lcs~ 不过有变换,并且要注意这道题O(n^4) -> O(n^3)的优化方法!!!! AE2A: 简单dp，虽然输入很大但其实一试就知道原来很大的值都是零！！！！ HOTELS: 面试，最大子段和的变种 SOLDIER: 背包，但注意中途有两个不等式！！！！首先是选一个更小的，然后是选一个更大的！！！！花了好多时间，不开心…… ISELECT: 面试，非常非常好的dp！！！！！刚开始没注意到可以连续两个不拿，做成ad hoc了！！！！而且这道题的性质是根本不用拷贝一次数组！！！！！另外，首位不能同时拿通过正反两遍dp，且初值设为-B就可以了！！！！！很好很好！！！！！ UVa_702: 很好的DP！ 5小时以上…… ANARC08A: 其实很朴素的bfs，不过因为不知为何SPOJ跑得特别慢，所以不断优化…… 第一个是哪都可以用的！像这种搜索题，可以一次把所有的最短步数求出来，然后存在cache里，最后query一次输出一次，这样才能保证效率！！！ 第二，bfs还是用数组加循环来表示每次的扩展动作（旋转、滑块之类的），防止loc explodes 第三，康拓展开还是很好用的~ 第四，不过对于这种题！尤其是节点数目很多很多的情况，康拓展开并不比trie好！！！！！！！毕竟复杂度是\theta(Cn^d), 其中C就是求hash的复杂度！如果是康拓的话，这道题是81，而如果用trie的话是9。节点数目少还不明显，一多之后区别还是很大的！！！（对这道题而言，大约是0.6s！！！） 第五，trie真的是又好写又好用！以前也还没想过用trie来作hash！这回学到了！！！哈哈哈！！！ 第六，时间复杂度高的算法，还是用char*不要用string。即使用string只是初始化、然后存一下变量，也会话很多时间…… PT07X: 奶奶的！！简单的一道树形DP，但没想到这么蛋疼!！！！ 也算是复习了一下如何用基础结构来表示树～ DP方程很好找,但是如果用vis数组实现的话很麻烦！！后来才想到可以记录递归过来的节点而不访问它! 最蛋疼的事情是老是TLE!!!!!　后来发现用stl::vector 0.7Xs就过了!！！非常非常地忧伤！！！！仔细一想,自己建一维树的话每一次添加边都有４次assignment, and the operation is not optimized!!!! Therefore I'm thinking, if I were still using the method (vis[][]) that first got TLE with STL, I could have ACed the problem long ago... Collection from SureInterview  kth in an unsorted list - heap Random collection of problems 最小的能被a整除的所有数字为1的整数 link Brainstormed Questions  Second shortest path, Dijkstra and Floyd-Warshall Second frequent elements in an array Remove the comments (什么叫用自动机可以解？) 比如C++的vector和list有什么使用的区别？ C++的virtual function有什么好处或者短处？ 什么是deadlock？ 如何使用mutex和semaphore？ 常见的系统面试题： 如何实现短网址服务？背后数据库，数据分布怎么设计？ link 如果提供一个服务让人实时知道附近的人，附近的名胜，附近的朋友等，要如何设计该系统，数据如何存储分布？ 如果要设计一个million people实用的聊天室，当然要分若干小聊天室或者聊天主题了，那么要如何设计？数据如何分布，如何发送消息？ Unix Commands for the Interview! link grep, find uniq -d file 可以用来找重复的！！！！！ sed用来替换文本 Other 24 interview problems for Hadoop and MapReduce developer. link Problems about Design, OOP, etc. OOP tutorial from Oracle √ too simple Introduction to Object Oriented Programming Concepts (OOP) and More Polymorphism method overloading operator overloading method overriding: override the methods from super-class Actually, I think my notes are more comprehensive (see below)  Architecture: 2-tier architecture: client/server 3-tire (3-layer) architecture: UI - application server () - data server MVC link to my notes of OOP chapter of PL class link to my notes of generic chapter of PL class In Java, functions are virtual by default; however, in C++ functions are virtual only when declared explicitly Abstract class and interface in C++ link!!!!!!!!!!!!!!!!!!! When to use INTERFACE, and when to use ABSTRACT CLASS link can-do is-a Design Problems in Interviews Don't forget to show off the knowledge of OOD Inheritance Encapsulation Polymorphism The ability to treat the class as its superclass, but mainly refers to virtual and overriding  Overloading - ad hoc polymorphism this link Abstract class Interface Singleton class In C++, use reference to implement a singleton class!! link Note that the type of the instance must be static!!! Why use it? The instance will be used over and over again! Why private? If public, instantiated over and over again Factory Pattern delegates the instantiation to classes I've used it for plugins to applications... this way you can have your main application call the class factory to instantiate the specific plugin implementing some interface that you've developed to in your main app. This way, you can code the main portion of your application without ever needing to know what is going to be plugged in. MVC Deck of cards class hand class card class deck enum Suit For implementation of Factory class, see this The factory itself can be a singleton class It can maintain a Registration List to record the objects that can be put created 注意数据结构的运用！ 比如playlist就应该用queue！ Using singleton means the class can only be instantiated ONCE Amazon Tic-tac-toe - MVC, Validator class 动物园 parking lot Deck and Card, shuffle - enum, Text Editor, solution here what is good OO design high cohesion and low coupling Low cohesion would mean that the class does a great variety of actions and is not focused on what it should do. High cohesion would then mean that the class is focused on what it should be doing it refers to how related are two classes / modules and how dependent they are on each other use abstraction to avoid repetition SOLID: S: single responsibility - each class should have only one responsibility O: Open closed - open for extension, closed for modification L: Liskov substitution principle -  I: Interface segregation principle - many client-specific interfaces are better than one general-purpose interface D: Dependency inversion principle Design Patterns Adapter (Structural) client call转换到老的接口上 Wrapper Strategy (Behavior) a family of algorithms,  其实类似于多态，interface: execute(a, b) => add implements interface (a, b), subtract(a, b) 都可以用统一接口调用 Decorator 其实就是Java的interface啦 Observer（观察者） 还MVC有点关系（model和view之间） From Other Materials RoBa的牙慧 bitonic，无重复搜素值。先bsearch找最大（snippets里面），再bsearch两边即可 Shuffle单链表，merge sort，merge的时候根据长度(lenA/(lenA + lenB))来计算某个链守被加入的概率 寻找数组中出现了n/k（k>2)的元素 link 注意的是这样的元素最多只能有k - 1个 MIT Hack a Google Interview 洗牌算法 Fisher–Yates shuffle. Path between nodes in binary trees: Use LCA (lowest common ancestor) Goal of MVC: keeping the dat separate from the user interface Leader selection problem of machines random numbers time stamp Typical DPs link Building bridge -> LIS Partition -> knapsack 一串矩形求相交：线扫 + segtree…… 遇左边界，query再插入，遇右边界删 link 好吧，其实是CLRS的，但是是Erik Demaine讲的！！很棒！link  判断一堆线段相交 不排序，而是维护一个heap，装的是events 每次一个event如果是左端点，加入，同时加入与其前驱急后继的meeting；右，删，同时删掉相关的meeting；meeting，添加结果，交换两个； 最近点对 这个地方CLRS讲得更好。关键在于merge也是O(n)。注意如果最近点对是跨界的话，那它们俩必然存在于\delte * 2\delte的矩形区域内，下略 The Five Essential Phone-Screen Questions (From Amazon!!!) link  Translation: some tips every candidate must know about interviewing at Amazon Write a function that sums up integers from a text file, one int per line.  Unclear terminology of OO: method signatures delegation It provides some example problems of design! Know some scripting and regex! grep, awk, sed, find Difference of different data structures C++ FAQ 6.9: C++ without virtual is not OO. Programming with classes but without dynamic binding is called "object based," but not "object oriented." Is virtual function really this important? 6.10: Very nice about virtual function!! Dynamic binding can improve reuse by letting old code call new code 7.9: the difference between class and struct: by default, one is private and the other is public 8.1: the reference IS the object 8.3: a[i] is actually Array::operator[](int)  8.4: method chain, a.method1().method2() 9.3: pros and cons about inline 9.5: Nice comparison between inline and macro!!!!!! 11.4: only one destructor, no overloading 13.6: at least one operand of any overloaded operator must be of some user-defined type 13.4: overload ++i, i++ (because the look the same): operator++ (){} operator++(int i){} (postfix) 16 17章暂时被跳过！ 18.5: Fred* const p, Fred const *p. read from left!!!!!!!!!!!! A const pointer to a fred 19.3: 继承的时候必须要写public！！！ class Sub : public Base 24.6: To make a public member of B public in D_priv or D_prot, state the name of the member with a B:: prefix, note that for f(int i, intj), just writeusing Base::f, instead of using Base::f(int, int) 25.9: virtual inheritance can be used to resolve dreaded diamond 39.1: string to other types 39.2: int to string ProgrammerInterview.com C++ pure virtual function: virtual void pure_virtual() = 0; it actually turns a normal class into an abstract class Any class that has at least one pure virtual function is called an abstract class. abstract in Java is the same thing of pure virtual functions in C++ -- need to be overwritten difference between lvalue and rvalue: An rvalue is any expression that has a value, but cannot have a value assigned to it;  inline and macro: compiler vs. preprocessor; textual replacement to call C functions: extern "C" void foo(); class variables and instance variables: 前者每一个类只能有一个，如static int count problems of multiple inheritance: diamond problem, use virtual public Base for inheritance to solve the problem this is C++ cannot be modified  The line that says “template” is called the template prefix, and it basically tells the compiler that the function definition underneath is a template, and “T” is called a type parameter. Name hiding in C++ Java Inner class != nested class inner class: non-static class inside another class, has access to everything of the enclosing class nested class: static System.out.println() out must be a static member variable, since there is no instance! Why private constructor don't want the objects to be created at all only want the objects to be created internally Good question about returning the reference to a private variable link Protected can be accessed by the same package!!!! Interface is essentially a type, any class can implement it When to use abstract or interface link，最后一段！ Everything passes by value in Java!!!!! For passing reference, think of C++: pointers are passed by value!!!!!! Java does not have the problem of diamond inheritance: although interface supports multiple inheritance, there is only ONE implementation of the method Inner class cannot have static methods 最后的inner class, anonymous class部分没有仔细看！ Data Structure Big-O notation: worst case, Omega notation: best case Design Pattern Private constructor is essential to Singleton method Misc Questions Languages and Algorithms C++ Tools page on my wiki What is the virtual function? virtual is related to dynamic binding, see this link on Stack Overflow, it is based on the type of class rather than the type of the reference. Java Tools page on my wiki What is the difference between interface and abstract in Java?  link 10 common Java interview questions Core Java interview questions static means Java can call it without even instantiation! The == operator compares two objects to determine if they are the same object in memory. It is possible for two String objects to have the same value, but located in different areas of memory. USE .equals() final – declare constant finally – handles exception finalize – helps in garbage collection Explain System.out.print System is a predefined final class, out is a PrintStream object and println is a built-in overloaded method in the out object. Polymorphism in Java Method overloading Method overriding through inheritance Method overriding through the Java interface Interview questions, link Another set, link Java里面String是immutable的！如果想，用StringBuilder！！ int[]传参时也是传的引用（虽然是pass by value） Other Problems of Algorithms External Sort: 注意最后多路归并时，会预留一块缓冲区在内存中。 Former Brain Storms or Research Questions C++ 二维数组传参 - 算了，还是直接上vector吧…… How to sort a map object in C++ - Map默认是按key排序的，如果想用value排序，最简单的办法是再建另外一个map；另外#include <utility>里面包含了关于pair的函数，hashmap就可以直接hashmap.insert(make_pair<aType, bType>(a, b)) C++ reference传参swap的bug - 没bug…… 浏览器里输入网址后进行的一系列工作流程？ DNS server -> port 80 -> TCP -> retrive HTML -> parse Special Topics how to implement multi-core version of programs in C++? link data parallelism and task parrallelism parallel sorting link profiling! lock-free data structure 区间贪心看这里http://www.cs.rit.edu/~zjb/courses/800/lec8.pdf 最多覆盖：扫线 最多的compitable：结束时间排序 interval partition segtree 模拟区间着色 优先队列（也就是课件上写的那种……) 带权值的scheduling 背包 Behavior Questions HR Interviews: questions and pitfalls Questions to Ask A/B testing? Posts about Interviews Most comprehensive面试准备 - 我的美国CS面试经验分享: link  BYVoid的面试记（G, A, F, T)  A student from Yale (G, F, 4sq, dp, fog creek) A bunch of interviews (mainly L) F, G, Box, houzz link LinkedIn: link Google's: link, link, news report about Google recruiting Twitter: link THU Dong Wang找工作的感想：上，中，下 Mona的fulltime求职攻略 买买提1，提到了很多公司 Cat Chen的经验 Google hiring process Hackernews Google!!!!!!! culture fit!!! enthusiasm, passion, interested in the problem rob said: TC rating 1500 -> pretty sure can get an offer Another experience link languages theory (compilers, grammars) is important Other Posts Junyu's travel to SC link Programming Tips 用 i & 1判断奇偶 branching prediction Companies Cheat sheet Power of 2 Project introduction Resume The project table provided by CCI 硬盘读取速度: <100M/s 内存读取速度: <10G/s 偶尔练练POJ 谈判 http://www.mitbbs.com/article_t2/Statistics/31356013.html

Sign in|Report Abuse|Print Page|Powered By Google Sites