yuanhsh

浏览: 570022 次
性别:
来自: 上海

最近访客更多访客>>

loginboot

Michael_113

z164974775

梦风云

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

面经算法总结

博客分类：

面经总结

Contents

Tasks

随时记得我的职业规划

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

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

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)!!!!!!!!!!!!!!!!!!!!!!!

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 write using 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

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 onlyONE 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）

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

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

Reference:

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

分享到：

LeetCode 211 - Add and Search Word - Dat ... | Find Union and Intersection of two unsor ...

2015-05-18 05:48
浏览 5418
评论(0)
分类:编程语言
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

面经算法总结

Tasks

Online Practice

Side Projects!

Reading

Research

Courses

Refer

Programming Challenges from Companies

Preparations

Online Problems

Tips

Nice Problems

Collection from LeetCode (deprecated, I have started using pen and paper for coding and taking notes)

ITInt5

Collection from 何海涛100题

Collection from EPI300（abandoned, notebook）

Chapter 1 ~ 3

Collection from CareerCup.com

From Interns Tag

Google

Facebook

Amazon

Collection from glassdoor

Collection from mitbbs

Facebook

LinkedIn

杂

Collection from StackOverflow & Geeksforgeeks

Collection from TopCoder, Hackerrank

Collection from POJ, UVa, SPOJ, etc.

Collection from SureInterview

Random collection of problems

Brainstormed Questions

Unix Commands for the Interview! link

Other

Problems about Design, OOP, etc.

Design Problems in Interviews

Design Patterns

From Other Materials

RoBa的牙慧

MIT Hack a Google Interview

The Five Essential Phone-Screen Questions (From Amazon!!!) link

C++ FAQ

ProgrammerInterview.com

Languages and Algorithms

C++

Other Problems of Algorithms

Former Brain Storms or Research Questions

Special Topics

Behavior Questions

Questions to Ask

Posts about Interviews

Other Posts

Programming Tips

Companies

Cheat sheet

偶尔练练POJ

谈判

评论

发表评论

相关推荐

Pocket Gems面经

2014一些FLG面经

FLAG面经集合

FLG System Design

Facebook 面经

Google & Twitter Interview

Google 两道题

Google Onsite 面经

Amazon interview Questions Cheatsheet

Google Onsite 面经

Matrix

Numbers

最近访客更多访客>>