code interview

Cracking the coding interview, careercup

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

gistfile1.txt

一个随机生成的整数序列，要求将奇数归到序列的左边，偶数在序列的右边，不考虑元素的相对顺序。要求的时间复杂度是O(n)

quicksort的partition，在两端设置游标，游标的停止条件有三个：
(0)：l = r
(1)：满足第一个条件下s[l]是偶数
(2)：满足第一个条件下s[r]

给定两个已排序的字符序列，求两个序列的最大公共子序列。例如 s1 = {a,b,c,d,f,i}, s2 = {a,f,g,h,k}，那么最大公共子序列就是 s = {a,f}
这道题其实就是求LCS，不能用DP，复杂度是 O(m+n)。

gistfile10.txt

void permute(char *a, int i, int n) // i is zero in first call and n is size of the string.
{
  int j; 
  if (i == n)
    printf("%s\n", a);
  else{
    for (j = i; j <= n; j++){
      swap((a+i), (a+j));
      permute(a, i+1, n);
      swap((a+i), (a+j)); //backtrack
    }
  }
}

gistfile11.txt

Shuffle a deck of cards
Fisher–Yates shuffle(Knuth shuffle) O(n)

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 down to 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

gistfile12.txt

int LIS(int[] array){
  int[] LIS=new int[array.Length];
  for (int i=0;i<arrary.Length;i++){
    LIS[i]=1;
    for (int j=0;j<i;j++)
      if (array[i]>array[j] & LIS[j]+1>LIS[i])
        LIS[i]=LIS[j]+1;
  }
  return max(LIS);
}

gistfile13.txt

Write code to remove alternate duplicate characters (case insensitive) from a string in place. For eg. "Today is the day" -> "Today ishe ". Also give test cases.

http://www.careercup.com/question?id=5684901156225024

http://www.geeksforgeeks.org/remove-all-duplicates-from-the-input-string/

gistfile2.txt

Reverse words in a given string

http://www.geeksforgeeks.org/reverse-words-in-a-given-string/

void reverseWords(char *s){
  char *word_begin = s;
  char *temp = s; /* temp is for word boundry */
 
  /*STEP 1 of the above algorithm */
  while( *temp ){
    temp++;
    if (*temp == '\0'){
      reverse(word_begin, temp-1);
    }
    else if(*temp == ' '){
      reverse(word_begin, temp-1);
      word_begin = temp+1;
    }
  } /* End of while */
 
   /*STEP 2 of the above algorithm */
  reverse(s, temp-1);
}

void reverse(char *begin, char *end){
  char temp;
  while (begin < end){
    temp = *begin;
    *begin++ = *end;
    *end-- = temp;
  }
}

gistfile3.txt

LCA and RMQ

http://blog.csdn.net/hell2pradise/article/details/5815959
http://www.cppblog.com/superKiki/archive/2010/05/08/114838.html
http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/

tarjan算法的步骤是(当dfs到节点u时):
1 在并查集中建立仅有u的集合,设置该集合的祖先为u
1 对u的每个孩子v:
   1.1 tarjan之
   1.2 合并v到父节点u的集合,确保集合的祖先是u
2 设置u为已遍历
3 处理关于u的查询,若查询(u,v)中的v已遍历过,则LCA(u,v)=v所在的集合的祖先

//parent为并查集，FIND为并查集的查找操作
//QUERY为询问结点对集合
//TREE为基图有根树
Tarjan(u)
    visit[u] = true
    for each (u, v) in QUERY
        if visit[v]
            ans(u, v) = FIND(v)
    for each (u, v) in TREE
        if !visit[v]
            Tarjan(v)
            parent[v] = u

FIND:
int find(int x){ // 并查集路径压缩
    if(x != fat[x]){
        return fat[x] = find(fat[x]);
    }
    return x;
}

gistfile4.txt

You are given an integer K, and a sorted array as an input which has been rotated about an unknown pivot. For example, 4 5 6 7 8 9 1 2 3. 
We need to write a function which should return the index of K in the array, if K is present, else return -1.

http://www.careercup.com/question?id=4852029923000320

Actually, you can do a little simpler than that. You don't actually need the pivot index. We just need to compare the mid element with rightmost and leftmost elements. If mid element is larger than leftmost element, bottom half of the array is properly sorted. In this case, we have a plain binary search (if element we are searching for is between leftmost and middle element, look at the lower half of the array; otherwise look at the upper half of the array). 
If mid element is smaller than leftmost element, upper half of the array is sorted. Accordingly, we look if the given element is at the upper of lower part.

int search(int A[], int N, int key) {
  int left = 0;
  int right = N - 1;
 
  while (left <= right) {
 
    int mid = left + ((right-left) / 2);
    if (A[mid] == key) return mid;
 
    // the bottom half is sorted
    if (A[left] <= A[mid]) {
      if (A[left] <= key && key < A[mid])
        right = mid -1;
      else
        left = mid+1;
    }
    // the upper half is sorted
    else {
      if (A[mid] < key && key <= A[right])
        left = mid+1;
      else
        right = mid-1;
    }
  }
  return -1;
}

The method won't work if there are duplicates in the array

gistfile5.txt

Given an array write a function to print all continuous subsequences in the array which sum of 0. 
e.g: 
Input: 
Array = [-1, -3, 4, 5, 4] 
output: 
-1, -3, 4

http://www.careercup.com/question?id=5172027535130624

1) run cumulate sum on the original array 
2) append [0] in font of this cum_sum_array 
3) check if two item in this cum_sum_array are same (for requirement sum==0, this could be done in O(n)) 

gistfile6.txt

You are given an array of 1's 2's and 3's. Sort this list so the 1's are first, the 2's come second, and the 3's come third. 
Ex: Input [1, 3, 3, 2, 1] 
Output [1, 1, 2, 3, 3] 
But there is a catch!! The algorithm must be one pass, which means no merge/quick sort. Also no extra list allocations are allowed, which means no bucket/radix/counting sorts. 
You are only permitted to swap elements.

http://www.careercup.com/question?id=18824667

dutch national flag problem

void sort(int *arr, int len) {
  int low, mid, high;
    for(low = mid = 0, high = len - 1; mid < high; ) {
      arr[mid] == 1 ? swap(&arr[mid++], arr[low++]) : arr[mid] == 2 ? mid++ : swap(&arr[mid], &arr[high--]);
    }
}

gistfile7.txt

find the missing number in a sorted array

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

Use Modified Binary Search
We modify the standard Binary Search algorithm to compare the middle element with its index and make decision on the basis of this comparison.
1) If the first element is not same as its index then return first index
2) Else get the middle index say mid
   a) If arr[mid] greater than mid then the required element lies in left half.
   b) Else the required element lies in right half.

int findMissing(int array[], int start, int end) {
    if(start  > end)
      return end + 1;
 
    if (start != array[start])
      return start;
 
    int mid = (start + end) / 2;
 
    if (array[mid] > mid)
      return findMissing(array, start, mid);
    else
      return findMissing(array, mid + 1, end);
}

gistfile8.txt

Find the k'th largest element in a binary search tree. Write code for

struct Node {
    int val;
    struct Node *left;
    struct Node *right;
} Node;

Node * kth_largest(Node *root, unsigned int k);

Traverse in reverse in-order (i.e. descending order)

http://www.careercup.com/question?id=15645665

TreeNode kthLargest(TreeNode t, int k){ 
    if(t == null){ 
        return null; 
    } 
    kthLargest(t.right, k); 
    k--; 
    if(k <= 0){ 
        return t; 
    } else { 
        return kthLargest(t.left, k); 
    }
}

gistfile9.txt

The Celebrity Problem

http://www.geeksforgeeks.org/the-celebrity-problem/

In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions.

We can describe the problem input as an array of numbers/characters representing persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, false otherwise. How can we solve the problem, try yourself first.

We measure the complexity in terms of calls made to HaveAcquaintance().