突击刷题： 一些问题

1.how does hashmap work,

Firstly, clarify the hash function: return an integer value from a given object. The value it returned should be the random the better. 

Eg: md5(obj)%hashSize
Or: famous 33 
for (int i=0; i<s.size(); i++{
  sum=sum*33+s[i];
  sum%=hashSize;
}
return sum;

Secondly, clarify the bucket. The bucket is simply an array, we used the hashed code to access the bucket. The bucket contains a linked list, which is used to handle collision or called chaining/open hashing.

Thirdly, rehashing when the size exceed the 20 percent of reserved bucket size, double the hashTableSize and rehash

 2.how many ways are there to go from top left of chess board to bottom right. 

state f[i][j] means number of way
initial condition f[i][*]=1, f[*][i]=1
transfer function f[i][j]=f[i-1][j]+f[i][j-1]
final f[m-1][n-1]

3.How to sort 1 trillion bits of data.
external merge sort. Say you have 100MB memory and use it to sort 900 MB data.

1) read in file sequencially with 100 MB and do the in-place sort (qsort?) save to file 
2) read 10 mb for each file (90 mb) and reserve 10 mb as cache, merge 9 list to 10mb cache, once cache is full, dump to file and clean cache. Once file cache is run out, load next 10mb. 
3) optimize with different hard drive, multithread and asynch IO

 4.operator= override 

  MyClass& MyClass::operator=(const MyClass &rhs) {
    // 1.  Deallocate any memory that MyClass is using internally
    // 2.  Allocate some memory to hold the contents of rhs
    // 3.  Copy the values from rhs into this instance
    // 4.  Return *this
  }

5 what is stable sort

Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.其实白话一点就是两个相等的数，各自标记，a在b前，排序后，a还在b前。。。