很久不写blog了，主要是因为转用linux系统之后，都找不到blog的入口，真是悲哀啊。
最近在潜心专研算法，数据结构这些，打算去大公司碰碰运气。
昨天在mitbbs看到一个兄弟准备面试的材料，让我大吃一惊，感觉自己还需要下大功夫才能拿到offer啊。不过拿offer除了下功夫，也要有运气。信著姐，拿offer。
下面是别人准备的清单，绝对不亚于GRE的难度。
再说NBA，昨天看了下骑士对凯子，我不是james密，但是我觉得除了骑士，其他队根本没法和湖人对抗。不过骑士又让我失望了，特别是JAMES的智商和情商真的不怎么样。遇到困难就不知道怎么办了，而主教练更是煞笔，你怎么换的人啊，就知道冒冷汗…..骑士的阵容，有3都是攻强守弱的球员，除了JAMES和parker。但是凯儿特人刚好有4个人进攻好，无论这2个人怎么防，球队到处是漏洞。特别是莫威，你防守差得可以进CBA了…..人见人爆。这个阵容除了打湖人，对其他强队基本都是被灭。因为湖人的控球后卫防守进攻也不行，而Parker和Moon又克制可鄙，奥尼儿克制拜那木，最多Jamison被Gasol互爆。个人防守差不可怕，就怕被别人无限利用…..凯儿特人球员篮球智商真是高！下场比赛，如果继续重用莫威，这比赛基本就没什么可看的了，骑士就等收尸吧。
Interview Qs
Data Structures
1. Integer
– find number of 1s
– next largest smaller
– smallest larger number
– determine if is palindrom
– itoa, atoi
– add 2 numbers w/o using + or arithmetic operators
– implement *, -, / using only +
– find max of two numbers w/o comparison
– swap two numbers with +/-
– swap two numbers with ^
– given an integer, find the closest number that is palindrome
– implement putlong() by putchar()
2. Bit array
3. Linked list
– find cycle,
– find position of cycle starts
– reverse LL
– delete a node in middle
– each node contains a value pointer pointing to a node,
duplicate LL.
– remove duplicates from sorted/un-sorted LL.
– find n-th to last node to end
– number is represented by LL, add 2 numbers
4. Array
– Longest common substring (LCSubstr)
– Longest common subsequence (LCS).
– Longest increasing subsequence (LIS).
– Longest palingdrome in string.
– array, elements are +/-, find subsequence of max sum
– circular array, elements are +/-, find subsequence of max sum
– find all pairs of integers add up to a sum
– find all pairs of integers add up to a sum,
integers are +/- and sorted
– find one missing number in N numbers in range [0, N]
– find two missing number in N numbers in range [0, N].
– binary search circular array
– Given {a1, a2, a3, ..}, {b1, b2, b3, …},
get {a1, b1, a2, b2, …}
– Given 2 arrays A and B, A large enough to hold both,
merge B into A.
5. String
– KMP, Rabin-Karp, Boyer Moore
– reverse string
– reverse words in string
– strcpy, strcmp, strstr, atoi, itoa, strdup
– remove duplicate characters in O(1) space
– Given dictionary, transform one word to another of same length.
– Given large text, find min cover distance of n words.
– find longest word made of other words
– find first non-repeated char
– remove specified char from a string
6. Matrix
– matrix elements are +/-, find submatrix of max sum
– rotate a matrix by 90 degrees
– each cell is black/white, find max subsquare with black border.
– binary matrix, find largest square matrix with 1s
– binary matrix, find largest rectangle matrix with 1s
7. Stack
– implement stack by queue.
– augmented stack with O(1) push, pop, min
– use single array to implement 3 stacks
– sort a stack in ascending order using only
push/pop/top/isEmpty/isFull
8. Queue
– implement queue by 2 stacks
9. Priority Queue
10. Heap
– create heap on array
11. Young Tableau
– find element
– get k-th element
12. BST
– pre/in/post-order traversal, recursive and iterative
– pre/in/post-order traversal, recursive and iterative,
with parent pointer
– find height
– determine IsBST
– find "next" node of a given node in inorder sequence
– find k-th inorder element
– find range of elements
– find diameter
– find all path adding to a sum
– Check if a tree is balanced
– Convert sorted array into balanced BST
– Find first common ancestor of two nodes in a BT or BST
– Link each node to its right sibling
– Print by level (BFS)
– Print by level (BFS) in reverse order
– Determine if 2 BSTs have the same structure
– Create a mirror BT of a BT
– Replicate a linked structure
13. 2-3-4 Tree
14. Red-Black Tree
15. Splay Tree
16. AVL Tree
17. Trie
18. Suffix Array
19. Suffix Tree
– LCSubstr (longest common substring)
– Longest repeated substring
– longest palindrome
– substring search
– data compression
20. B-Tree
21. KD Tree
22. Range Tree
23. Hash Table
24. Bloom filter
25. Disjoint set
26. Graph
– DFS, BFS
– find path existence between two nodes
– Min vertice set covering all edges
– shortest path
– minimum spanning tree
– min edge coverage by vertex
Sorting
1. Bubble sort
2. Insertion sort
3. Selection sort
4. Shell sort
5. Heap sort
6. Quick sort
7. Merge sort
8. N-way merge sort (external sort)
9. Counting sort
10. Bucket sort
Search
1. Linear search
2. Binary search
– Binary search, iterative/recursive
– find missing number is sorted array
– search in circular sorted array
3. Quick Select
Dynamic programming
1. BST
2. COV
3. ILP
4. KS
5. LCS
6. LSP
7. MCM
8. ODP
9. SCP
10. SPA
11. SPC
12. TSP
13. Given array a[], when i < j, get max(a[i] – a[j]).
14. levenshtein edit distance
15. Coin Change problem.
Large-scale system
1. Bloom filter
2. Bit-array/bit-map
3. Heap
4. Hash table
– d-left hashing
5. Sub-division
6. Database indexing
7. Inverted index
8. External sort
9. Map-reduce
Discrete math, Probability and Statistics, Numerical Computation
1. Permutation
– 3 colors, how many ways to color a cube?
– robot, ways to go to diagonal corner on NxN matrix?
– print all combinations of valid n-pairs of parentheses
– print all subsets of a set
2. Combination
3. Sampling
4. Random number generator
– What’s a good random number generator?
– Given random generator [1, 2, 3, 4, 5],
generate random in [1..7].
5. Reservoir sampling
6. Find median in stream
7. Card shuffling
8. Primality testing
9. Find prime numbers: naive, sieve of Eratosthenes, sieve of Atkin
10. Randomized primality testing, what’s good random generator
11. Fibonacci sequence
12. Factorial numbers
13. Frobenous numbers
14. Newton-Ralphson algorithm
15. Bayes theorem
Computational algebra
1. Convex-hull
2. Closest pairs
Computational theory
1. Automata theory
2. DFA
3. NFA
4. Regular language
5. Pumping lemma
6. Turing machine
7. NP-completeness
1. TSP
2. Vertex-cover problem
3. Set-covering problem.
4. Subset-sum problem.
OS
1. Process and thread
2. Semaphore, mutex, monitor
3. Function call/call frame
4. Context switch
5. Multi-threading
6. Multi-process
7. Thread safety
8. Big/Little-endian
9. Heap/stack
10. Malloc/free
11. Virtual memory, page fault, thrashing
12. DMA (Direct Memory Access)
Networking
1. 7-layer OSI model
2. 4-layer TCP/UDP model
3. TCP/UDP
4. TCP 3-way handshake (ACK machanism),
flow control, congestion control
5. Things happen after entering url
6. Routing protocols: BGP, OSPF, RIP
7. Subnet mask, packet routing on same/different network.
8. Performance
Database
1. Normalization
2. External sorting
3. B-tree, B+-tree.
4. Relational algebra
Compiler
1. LL, SLR, LALR, LR, GLR
2. recursive precedence
3. Operator precedence
4. Postfix evaluation of arithmetic expression
– implement a calculator
C/C++/Java
1. const char *, char * const, const char * const
2. static
3. volatile
4. explicit
5. Object/class
6. Inheritance
7. Encapsulation
8. Polymorphism
9. operator overloading
10. Composition/inheritance
11. Interface, abstract class
12. Struct/class
13. 4 default methods of a C++ struct/class
14. deep copy/shallow copy
15. C++ name hiding
16. C++ smart pointer
17. friend function/class
18. Multiple inheritance
19. Virtual inheritance
20. Constructor
21. Copy/assignment constructor
22. Virtual destructor
23. Virtual function, vtable
24. Pure virtual function
25. Macro, typedef, inline
26. C, C++, Java comparison
27. Garbage collection
28. Dangling pointer, free null pointer, memory leak
29. New/Delete
30. Malloc/free/realloc/calloc
31. Lock
32. Dead lock’s four conditions
33. #pragma directive
34. Exception handling
35. try/catch/finally
36. final, finally, finalize
37. Java object reflection
38. C++ templates, java generics
39. Effect of keeping constructor private
40. Pass by Value, reference, pointer
41. Reference v.s. pointer
42. In-memory file system data structures and algorithms?
43. Implement singleton
44. Implement singleton w/o static/global variable
45. Thread programming possible problems
46. sizeof operator.
47. Java: vector v.s. ArrayList
48. int (a*)[10]
49. Implement a lock.
50. Implement a buffer for DataOutputStream.
51. awk, tr, uniq, grep
Other problems
1. 2 eggs, 100 floors, find floor that breaks egg
minimizing number of drops.
2. 5 quart jug and 3 quart jug, measure 4 quarts of water.
3. 100 lockers, open every other i-th locker (i = 1, 2, …, 100).
Final open?
4. Men on island, can see hat on others only. N men, C hats,
days to remove?
5. 8/12 balls, find the one lighter/heavier
6. 8/12 balls, find one weighs different
7. 2 fuses each burns in 1 hour, measure 45 minutes
8. Bridge crossing, 1, 2, 5, 10. Minual number to pass bridge
9. Orange, apple, orange and apple, all labeled wrong. Find out.
10. 3 light switches, only one can be on at a time. Find it out.
11. Find the biggest, 2 biggest, biggest & smallest
12. n*m*k cube, how many are on the surface?
13. Test a pen, ATM machine, webpage, vending machine, program crash?
14. Given phone #, print all word representations on phone pad.
15. Find overlap of rectangles
16. Find median of two sorted arrays.
17. N computers each hold N numbers. Find median of these N*N numbers.
18. Recontruct a BT from pre/in/post-order traversal
19. Recontruct a BST from pre/in/post-order traversal
20. Find longest prefix common to all strings
21. Implement LRU cache system, O(1) find and update
22. Shifted sorted array, rotate.
23. Histogram, find max internal rectangle.
24. Tournament problem
25. N people, 1 celebrity, find celebrity in O(n) time.
26. 4 jars, 1 polluted so pills weigh +1, find out which jar
27. 25 horses, 5 horses maximal each match. Find the fastest 3
28. Mirror, why left/right reversed, not up/down?
29. How is next_permutation() in STL implemented?
30. N line segments on number axis, calculate common coverage
31. wild card match on patterns * (0-n) and ? (1).
32. Find number of trailing zeros in n!
33. Print square matrix in a spiral inwardly.
34. Find one’s phone number given resume only
35. N stairs, each time can go up 1 or 2. How many ways to go up?
36. Find majority element in an array.
37. Two cubes as a calendar
38. Coin change problem
39. Josephus Circle, last survivor?
40. Pick marbles, strategy to win?
41. Get sequence 1, 11, 21, 1211, …
42. C program that prints itself
43. Print week given date
44. enter code, allow one miss
45. Check equality of two number sets
