0618百度C/C++平台开发工程师二面试题

ydfgic

2.2 用bitmap做。

如果是32位整数，则耗费0xffff*8 = 512K 内存,遍历第一个数组，在相应的位置上置1；然 ...
noword2k 发表于 2011-06-21 13:27

bitmap只能讲数据缩小32倍,也就是 说 32位整数 要耗的内存是0x111ff =  2^(27) = 128M 内存

flyingwalf

第一题随手做了下，欢迎大家指正交流

1. #include <stdio.h>
   
2. 
   
3. #define BASE 26
   
4. 
   
5. int revert(const char*);
   
6. int pow(int, int);
   
7. 
   
8. int main(int argc, char** argv)
   
9. {
   
10.     if(argc != 2)
    
11.     {
    
12.         printf("Args not correctly supplied\nUsage:revert message\n");
    
13.         exit(1);
    
14.     }
    
15. 
    
16.     int res = revert(argv[1]);
    
17. 
    
18.     if(res != -1)
    
19.     {
    
20.         printf("Revert of %s is:%d\n", argv[1], res);
    
21.     }
    
22.     else
    
23.     {
    
24.         printf("Illegal message string\n");
    
25.     }
    
26. 
    
27.     return 0;
    
28. }
    
29. 
    
30. int revert(const char* message)
    
31. {
    
32.     int res = 0;
    
33.     char* pch = message;
    
34.    
    
35.     while(*pch != '\0')
    
36.     {
    
37.         pch++;
    
38.     }
    
39.     pch--; //pch now point to the last character of message
    
40. 
    
41.     int bitCount = 0;
    
42.     int tmpval;
    
43.     while(1)
    
44.     {
    
45.         if( *pch >= 'a' && *pch <= 'z')
    
46.         {
    
47.             tmpval = *pch - 'a' + 1;
    
48.         }
    
49.         else if(*pch >= 'A' && *pch <= 'Z')
    
50.         {
    
51.             tmpval = *pch - 'A' + 1;
    
52.         }
    
53.         else
    
54.         {
    
55.             printf("Message String contain illegal char, return error!\n");
    
56.             return -1;
    
57.         }
    
58. 
    
59. 
    
60.         res += tmpval*pow(BASE, bitCount);
    
61.         bitCount++;
    
62. 
    
63.         if(pch == message)
    
64.         {
    
65.             break;
    
66.         }
    
67.         else
    
68.         {
    
69.             pch--;
    
70.         }
    
71.     };
    
72. 
    
73.     return res;
    
74. }
    
75. 
    
76. /**
    
77. *  Ugly pow function, DO NOT use it anywhere else
    
78. */
    
79. int pow(int base, int index)
    
80. {
    
81.     if(index == 0)
    
82.     {
    
83.         return 1;
    
84.     }
    
85.     else
    
86.     {
    
87.         return base*pow(base, index-1);
    
88.     }
    
89. }

复制代码

goldenfort

回复 17# snowpinex


    可以唯一确定，那好不好恢复呢？ 恢复费事吗

snowpinex

回复 23# goldenfort

我只是将我的第一想法给写出来，那时还没考虑效率；恢复时可以用递归算法，之前写过一个

noword2k

bitmap只能讲数据缩小32倍,也就是 说 32位整数 要耗的内存是0x111ff =  2^(27) = 128M 内存
ydfgic 发表于 2011-06-22 10:27

    我算错了，应该是4G/8 = 512M内存。

lwrsmy

第一题:
//暂不考虑size <0
int power(int size,int base)
{
        int i = 0;
        int result = 1;
        printf("%s:%s:%d\n",__FILE__,__FUNCTION__,__LINE__);
        while(i < size)
        {
                result = result*base;
                i++;
        }
        printf("%s:%s:%d\n",__FILE__,__FUNCTION__,__LINE__);
        return result;
}
int  strToInt(char *string)
{
        int len = strlen(string);
        int result = 0;
        int i = 0;
       
        if(string == NULL)
        {
                return -1;
        }
        printf("%s:%s:%d\n",__FILE__,__FUNCTION__,__LINE__);
        printf("strlen(string)=%d\n",strlen(string));
        printf("string=%s\n",string);
        while(string[i] != '\0')
        {
                //'A'=65,26进制
                result += (string[i]-64)*power(len - i - 1,26);
                i++;
                printf("%s:%s:%d\n",__FILE__,__FUNCTION__,__LINE__);
        }
        printf("%s:%s:%d\n",__FILE__,__FUNCTION__,__LINE__);
        return result;
}

int main()
{
        char str[4] = "ABC";
        int result = 0;

        printf("%s:%s:%d\n",__FILE__,__FUNCTION__,__LINE__);
        result = strToInt(str);
        printf("result=%d\n",result);
        return 0;
}

lwrsmy

第二题2)
先对两个数组分别快排
int   merge(int *a,int asize,int *b,int bsize,int *c)
{
        int i = 0;
        int j = 0;
        int        k = 0;
        int times = 0;
       
        for(; i<asize; i++)
        {       
                while(a[i] > b[j])
                {
                        j++;
                }
               
                if(a[i] < b[j])
                {
                        continue;
                }
                else
                {
                        c[k] = a[i];
                        k++;
                        j++;

                }
        }


        return 0;
}

lwrsmy

2(1):
<parent>
      <lchild>
          <>
              <>
              <>
          <>
      <lchild>
      <rchild>
          <>
              <>
              <>
          <>
      <rchild>
<parent>

atomthan

百度果然猛！敢想不敢写……

goldenfort

回复 1# liqingfang


   关于写二叉树 那个，  遍历时直接 记录从根 到 当前节点的 左右左。。。。序列就可以了， 每个左右只要一个bit. 恢复也非常快速。

不过保存二叉树 到 disk,  比 保存数据，用程序构建  二叉树  好处在哪里呢？  

这就是个专门考人的题目吧，实用价值比较小