2010迅雷二笔题

2010迅雷二笔题

算法及数据结构 2009-09-22 20:08:49 阅读985 评论7 字号：大中小

         迅雷居然也有二笔，还好通过了一笔，C++一笔一共有700多人参加，二笔只有133人参加，呵呵，其实一笔里面的名单并没有我，我是去强笔的，可能是网上简历投递错了，迅雷公司的员工态度也挺好的，另加了一个教室让我们考。二笔就不能强笔了，必须凭身份证核对后才可以进入考场。情景和上次周立功差不多，dcs依然坚挺着，我想这次笔试的人估计会经常在以后的笔试和面试中相遇吧。
       二笔只有三道题，分值分别为30, 30, 40，题分别如下：
1、实现strtol函数，其原型如为int strtol(const char *num_str, char **endptr, int base)，num_str存放待转换的字符串，可以是负数也可以是正数；endptr指向第一个非法字符的地址，如果endptr为NULL则不指向第一个非法字符的地址；base用于指示进制，若base为0，则根据num_str的指示来转换。函数必须检查溢出，如果正数溢出，返回INT_MAX；若负数溢出，返回INT_MIN。
2、一亿个数找最大的1000个数，要求效率高占用内存少。函数原型为：find_max_data(int* source_data, int* max_data)，其中source_data是存放一亿个数的数组，max_data用于存放其中最大的1000个数。
3、将一个集合拆分成两个不相交的子集，两个子集元素之和相等，如{1, 2, 3, 4, 5, 6, 7}，拆分成：
{2, 5, 7}, {1, 3, 4, 6}
给出一个集合，求所有符合上面要求的拆分，效率最高分越高，函数原型为int cal_num(int n);

        第一道题没有什么难度，不管有多少瑕疵，实现其基本功能还是很容易的。呵呵，因为我对glibc的了解，所以有点点沾光，我知道glibc中的atoi函数的基本实现，其实atoi内部调用另外一个更通用的函数来实现其功能，这个函数就是：int _strtol_internal (const char *nptr, char **endptr, int base, int group)，我对这个函数的实现代码不是很熟悉。自己写的那个感觉好繁琐啊，有些细节考虑不周，有些细节却又考虑过多。glibc中的_strtol_internal实现如下：
#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;

 //过滤掉空格和制表符，这个我没有考虑到
 //为什么不先断言一下nptr不为NULL呢？
 while (*nptr == ' ' || *nptr == '\t')
  ++nptr;

 //如果为负数
 if (*nptr == '-')
 {
  sign = -1;
  ++nptr;
 }
 else if (*nptr == '+') //这个我没有考虑到，我想着正数就不用显式写'+'
  ++nptr;

 //如果是非法字符
 //仅仅在这儿判断就够了吗？？
 //如果出现"123!!78"这个字符串怎么办呢？
 if (*nptr < '0' || *nptr > '9')
 {
  if (endptr != NULL)
   *endptr = (char *) nptr;
  return 0L;
 }

 //为什么要做这样的断言呢？？
 //_strtol_internal完全根据num_str来判断是什么进制
 assert (base == 0);

 //默认是10进制
 base = 10;

 //如果以'0'开头则为八进制，以"0x"开头的则为十六进制
 if (*nptr == '0')
 {
  if (nptr[1] == 'x' || nptr[1] == 'X')
  {
   base = 16;
   nptr += 2;
  }
  else
   base = 8;
 }

 //根本不考虑出现16进制中的'A'-'F'
 //我考虑的太多了，仅仅判断字符是不是合法我加上了
 //如果是16进制，允许出现'A'-'F'这样的字符
 while (*nptr >= '0' && *nptr <= '9')
 {
  unsigned long int digval = *nptr - '0';

  //if里面的条件太复杂了
  //条件有两个，第一个是result已经大于LONG_MAX / 10，
  //第二个条件要分两种情况，
  //第一种情况是处理正数时，result刚好等于LONG_MAX / 10并且将要加的值大于LONG_MAX % 10
  //第二种情况为负数，因为|LONG_MIN| = |LONG_MAX|+1，所以这儿要将LONG_MAX加一
  //我感觉这儿有两个问题：
  //一，为什么仅仅考虑10进制呢，没有考虑到8进制和16进制的情况
  //二、为什么不将LONG_MAX / 10，LONG_MAX % 10这些值先求出来放入到一个变量中呢？
  //每次LONG_MAX这样大的数对10求模，效率应该很低下吧？

  //我使用减法来判断是否有溢出，但是没有考虑到负数最小数的绝对值比正数最大值要大一
  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)))
  {
   //我没有设置errno
   errno = ERANGE;
   return sign > 0 ? LONG_MAX : LONG_MIN;
  }

  //这个循环做的比较好，我居然傻乎乎将字符串倒置了，以符合自己的思维
  //先处理低位数，再处理高位数。这儿并不将字符串倒置，而是每次将以前的结果
  //乘以base，比如“789”，循环三次，
  //第一次，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;

  //移动指针，指向下一个元素
  ++nptr;
 }

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

 //函数返回了，也没有见到end_ptr的作用，group也没有被使用过
}
       要熟悉ASC码啊，这次一定要记住，ASC码表中'0'-'9'对应着整数48-57，'A'-'Z'对应整数65-90，‘a’-'z'对应整数97-122。这道题我感觉我做的一般吧。

       第二道题很简单，求第k大数前几天我刚研究下了，一亿个数全部读入内存的话需要占用400MB的空间，这道题似乎说所有的数都已经读入了内存，如果使用堆来做的，只需要维护一个大小为1000的堆就好了，这道题我很快就做完了。首先写了一个调堆的函数heapify，都是些经典的代码。然后在find_max_data中，先调用heapify建成一个大小为1000的小顶堆，然后遍历1001到一亿的所有数，如果大于堆顶的话，就替换掉堆顶，然后再调整堆。
      第三道题至今我仍然没有找到什么好的办法来解决，有待进一步研究。三道题两个半小时，除了会做的早做完了，不会做给再多时间也无用，不知道二笔的结果怎么样，如果过了二笔，接下来会有三次面试。