面试题目总结 转载

标签（空格分隔）： interview

转载于chengdujin博客

  • 终于找到这篇了, 之前看过, 整理的很全面, 后来丢掉了链接...

Data Structures

  1. Integer
  2. find number of 1s
  3. next largest smaller
  4. smallest larger number
  5. determine if is palindrom
  6. itoa, atoi
  7. add 2 numbers w/o using + or arithmetic operators
  8. implement *, -, / using only +
  9. find max of two numbers w/o comparison
  10. swap two numbers with +/-
  11. swap two numbers with ^
  12. given an integer, find the closest number that is palindrome
  13. implement putlong() by putchar()
  14. Bit array
  15. Linked list
  16. find cycle,
  17. find position of cycle starts
  18. reverse LL
  19. delete a node in middle
  20. each node contains a value pointer pointing to a node, duplicate LL.
  21. remove duplicates from sorted/un-sorted LL.
  22. find n-th to last node to end
  23. number is represented by LL, add 2 numbers
  24. Array
  25. Longest common substring (LCSubstr)
  26. Longest common subsequence (LCS).
  27. Longest increasing subsequence (LIS).
  28. Longest palingdrome in string.
  29. array, elements are +/-, find subsequence of max sum
  30. circular array, elements are +/-, find subsequence of max sum
  31. find all pairs of integers add up to a sum
  32. find all pairs of integers add up to a sum, integers are +/- and sorted
  33. find one missing number in N numbers in range [0, N]
  34. find two missing number in N numbers in range [0, N].
  35. binary search circular array
  36. Given {a1, a2, a3, ..}, {b1, b2, b3, ...}, get {a1, b1, a2, b2, ...}
  37. Given 2 arrays A and B, A large enough to hold both, merge B into A.
  38. String
  39. KMP, Rabin-Karp, Boyer Moore
  40. reverse string
  41. reverse words in string
  42. strcpy, strcmp, strstr, atoi, itoa, strdup
  43. remove duplicate characters in O(1) space
  44. Given dictionary, transform one word to another of same length.
  45. Given large text, find min cover distance of n words.
  46. find longest word made of other words
  47. find first non-repeated char
  48. remove specified char from a string
  49. Matrix
  50. matrix elements are +/-, find submatrix of max sum
  51. rotate a matrix by 90 degrees
  52. each cell is black/white, find max subsquare with black border.
  53. binary matrix, find largest square matrix with 1s
  54. binary matrix, find largest rectangle matrix with 1s
  55. Stack
  56. implement stack by queue.
  57. augmented stack with O(1) push, pop, min
  58. use single array to implement 3 stacks
  59. sort a stack in ascending order using only push/pop/top/isEmpty/isFull
  60. Queue
  61. implement queue by 2 stacks
  62. Priority Queue
  63. Heap
  64. create heap on array
  65. Young Tableau
  66. find element
  67. get k-th element
  68. BST
  69. pre/in/post-order traversal, recursive and iterative
  70. pre/in/post-order traversal, recursive and iterative, with parent pointer
  71. find height
  72. determine IsBST
  73. find "next" node of a given node in inorder sequence
  74. find k-th inorder element
  75. find range of elements
  76. find diameter
  77. find all path adding to a sum
  78. Check if a tree is balanced
  79. Convert sorted array into balanced BST
  80. Find first common ancestor of two nodes in a BT or BST
  81. Link each node to its right sibling
  82. Print by level (BFS)
  83. Print by level (BFS) in reverse order
  84. Determine if 2 BSTs have the same structure
  85. Create a mirror BT of a BT
  86. Replicate a linked structure
  87. 2-3-4 Tree
  88. Red-Black Tree
  89. Splay Tree
  90. AVL Tree
  91. Trie
  92. Suffix Array
  93. Suffix Tree
  94. LCSubstr (longest common substring)
  95. Longest repeated substring
  96. longest palindrome
  97. substring search
  98. data compression
  99. B-Tree
  100. KD Tree
  101. Range Tree
  102. Hash Table
  103. Bloom filter
  104. Disjoint set
  105. Graph
  106. DFS, BFS
  107. find path existence between two nodes
  108. Min vertice set covering all edges
  109. shortest path
  110. minimum spanning tree
  111. 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
  3. Binary search, iterative/recursive
  4. find missing number is sorted array
  5. search in circular sorted array
  6. 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
  5. d-left hashing
  6. Sub-division
  7. Database indexing
  8. Inverted index
  9. External sort
  10. Map-reduce

Discrete math, Probability and Statistics, Numerical Computation

  1. Permutation
  2. 3 colors, how many ways to color a cube?
  3. robot, ways to go to diagonal corner on NxN matrix?
  4. print all combinations of valid n-pairs of parentheses
  5. print all subsets of a set
  6. Combination
  7. Sampling
  8. Random number generator
  9. What's a good random number generator?
  10. Given random generator [1, 2, 3, 4, 5], generate random in [1..7].
  11. Reservoir sampling
  12. Find median in stream
  13. Card shuffling
  14. Primality testing
  15. Find prime numbers: naive, sieve of Eratosthenes, sieve of Atkin
  16. Randomized primality testing, what's good random generator
  17. Fibonacci sequence
  18. Factorial numbers
  19. Frobenous numbers
  20. Newton-Ralphson algorithm
  21. 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
  8. TSP
  9. Vertex-cover problem
  10. Set-covering problem.
  11. 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
  5. 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. nmk 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