迅雷居然也有二筆,，還好通過了一筆,，C++一筆一共有700多人參加,，二筆只有133人參加,，呵呵,，其實(shí)一筆里面的名單并沒有我,，我是去強(qiáng)筆的,，可能是網(wǎng)上簡歷投遞錯(cuò)了，迅雷公司的員工態(tài)度也挺好的,，另加了一個(gè)教室讓我們考,。二筆就不能強(qiáng)筆了，必須憑身份證核對后才可以進(jìn)入考場,。情景和上次周立功差不多,，dcs依然堅(jiān)挺著，我想這次筆試的人估計(jì)會經(jīng)常在以后的筆試和面試中相遇吧,。
       二筆只有三道題,，分值分別為30, 30, 40,，題分別如下：
1、實(shí)現(xiàn)strtol函數(shù),，其原型如為int strtol(const char *num_str, char **endptr, int base),，num_str存放待轉(zhuǎn)換的字符串，可以是負(fù)數(shù)也可以是正數(shù),；endptr指向第一個(gè)非法字符的地址,，如果endptr為NULL則不指向第一個(gè)非法字符的地址；base用于指示進(jìn)制,，若base為0，則根據(jù)num_str的指示來轉(zhuǎn)換,。函數(shù)必須檢查溢出,，如果正數(shù)溢出，返回INT_MAX,；若負(fù)數(shù)溢出,，返回INT_MIN。
2,、一億個(gè)數(shù)找最大的1000個(gè)數(shù),，要求效率高占用內(nèi)存少。函數(shù)原型為：find_max_data(int* source_data, int* max_data),，其中source_data是存放一億個(gè)數(shù)的數(shù)組,，max_data用于存放其中最大的1000個(gè)數(shù)。
3,、將一個(gè)集合拆分成兩個(gè)不相交的子集,，兩個(gè)子集元素之和相等，如{1, 2, 3, 4, 5, 6, 7},，拆分成：
{2, 5, 7}, {1, 3, 4, 6}
給出一個(gè)集合,，求所有符合上面要求的拆分，效率最高分越高,，函數(shù)原型為int cal_num(int n);

        第一道題沒有什么難度,，不管有多少瑕疵，實(shí)現(xiàn)其基本功能還是很容易的,。呵呵,，因?yàn)槲覍libc的了解，所以有點(diǎn)點(diǎn)沾光,，我知道glibc中的atoi函數(shù)的基本實(shí)現(xiàn),，其實(shí)atoi內(nèi)部調(diào)用另外一個(gè)更通用的函數(shù)來實(shí)現(xiàn)其功能，這個(gè)函數(shù)就是：int _strtol_internal (const char *nptr, char **endptr, int base, int group),，我對這個(gè)函數(shù)的實(shí)現(xiàn)代碼不是很熟悉,。自己寫的那個(gè)感覺好繁瑣啊,，有些細(xì)節(jié)考慮不周，有些細(xì)節(jié)卻又考慮過多,。glibc中的_strtol_internal實(shí)現(xiàn)如下：
#define LONG_MAX 2147483647L 
#define LONG_MIN (-2147483647L-1L)
long int _strtol_internal (const char *nptr, char **endptr, int base, int group)
{
 unsigned long int result = 0;
 long int sign = 1;

 //過濾掉空格和制表符,，這個(gè)我沒有考慮到
 //為什么不先斷言一下nptr不為NULL呢？
 while (*nptr == ' ' || *nptr == '\t')
  ++nptr;

 //如果為負(fù)數(shù)
 if (*nptr == '-')
 {
  sign = -1;
  ++nptr;
 }
 else if (*nptr == '+') //這個(gè)我沒有考慮到,，我想著正數(shù)就不用顯式寫'+'
  ++nptr;

 //如果是非法字符
 //僅僅在這兒判斷就夠了嗎,？？
 //如果出現(xiàn)"123!!78"這個(gè)字符串怎么辦呢,？
 if (*nptr < '0' || *nptr > '9')
 {
  if (endptr != NULL)
   *endptr = (char *) nptr;
  return 0L;
 }

 //為什么要做這樣的斷言呢,？？
 //_strtol_internal完全根據(jù)num_str來判斷是什么進(jìn)制
 assert (base == 0);

 //默認(rèn)是10進(jìn)制
 base = 10;

 //如果以'0'開頭則為八進(jìn)制,，以"0x"開頭的則為十六進(jìn)制
 if (*nptr == '0')
 {
  if (nptr[1] == 'x' || nptr[1] == 'X')
  {
   base = 16;
   nptr += 2;
  }
  else
   base = 8;
 }

 //根本不考慮出現(xiàn)16進(jìn)制中的'A'-'F'
 //我考慮的太多了,，僅僅判斷字符是不是合法我加上了
 //如果是16進(jìn)制，允許出現(xiàn)'A'-'F'這樣的字符
 while (*nptr >= '0' && *nptr <= '9')
 {
  unsigned long int digval = *nptr - '0';

  //if里面的條件太復(fù)雜了
  //條件有兩個(gè),，第一個(gè)是result已經(jīng)大于LONG_MAX / 10,，
  //第二個(gè)條件要分兩種情況，
  //第一種情況是處理正數(shù)時(shí),，result剛好等于LONG_MAX / 10并且將要加的值大于LONG_MAX % 10
  //第二種情況為負(fù)數(shù),，因?yàn)閨LONG_MIN| = |LONG_MAX|+1，所以這兒要將LONG_MAX加一
  //我感覺這兒有兩個(gè)問題：
  //一,，為什么僅僅考慮10進(jìn)制呢,，沒有考慮到8進(jìn)制和16進(jìn)制的情況
  //二、為什么不將LONG_MAX / 10,，LONG_MAX % 10這些值先求出來放入到一個(gè)變量中呢,？
  //每次LONG_MAX這樣大的數(shù)對10求模，效率應(yīng)該很低下吧,？

  //我使用減法來判斷是否有溢出,，但是沒有考慮到負(fù)數(shù)最小數(shù)的絕對值比正數(shù)最大值要大一
  if (result > LONG_MAX / 10
   || (sign > 0 ? result == LONG_MAX / 10 && digval > LONG_MAX % 10
   : (result == ((unsigned long int) LONG_MAX + 1) / 10
   && digval > ((unsigned long int) LONG_MAX + 1) % 10)))
  {
   //我沒有設(shè)置errno
   errno = ERANGE;
   return sign > 0 ? LONG_MAX : LONG_MIN;
  }

  //這個(gè)循環(huán)做的比較好，我居然傻乎乎將字符串倒置了,，以符合自己的思維
  //先處理低位數(shù),，再處理高位數(shù)。這兒并不將字符串倒置,，而是每次將以前的結(jié)果
  //乘以base,，比如“789”，循環(huán)三次,，
  //第一次,，result=0，result *= base后,，result=0,；result += digval;后,，result=7
  //第二次，result=7,，result *= base后,，result=70；result += digval;后,，result=78
  //第二次,，result=78，result *= base后,，result=780,；result += digval;后，result=789
  result *= base;
  result += digval;

  //移動(dòng)指針,，指向下一個(gè)元素
  ++nptr;
 }

 //別忘了乘上符號哦
 return (long int) result * sign;

 //函數(shù)返回了,，也沒有見到end_ptr的作用，group也沒有被使用過
}
       要熟悉ASC碼啊,，這次一定要記住，ASC碼表中'0'-'9'對應(yīng)著整數(shù)48-57,，'A'-'Z'對應(yīng)整數(shù)65-90,，‘a’-'z'對應(yīng)整數(shù)97-122。這道題我感覺我做的一般吧,。

       第二道題很簡單,，求第k大數(shù)前幾天我剛研究下了，一億個(gè)數(shù)全部讀入內(nèi)存的話需要占用400MB的空間,，這道題似乎說所有的數(shù)都已經(jīng)讀入了內(nèi)存,，如果使用堆來做的，只需要維護(hù)一個(gè)大小為1000的堆就好了,，這道題我很快就做完了,。首先寫了一個(gè)調(diào)堆的函數(shù)heapify，都是些經(jīng)典的代碼,。然后在find_max_data中,，先調(diào)用heapify建成一個(gè)大小為1000的小頂堆，然后遍歷1001到一億的所有數(shù),，如果大于堆頂?shù)脑?，就替換掉堆頂，然后再調(diào)整堆,。
      第三道題至今我仍然沒有找到什么好的辦法來解決,，有待進(jìn)一步研究。三道題兩個(gè)半小時(shí),，除了會做的早做完了,，不會做給再多時(shí)間也無用,，不知道二筆的結(jié)果怎么樣，如果過了二筆,，接下來會有三次面試,。