Python descriptor details

腾讯游戏研发校招电话面试一面

本来还在写着创梦天地的笔试，腾讯突然打电话过来要面试。没办法，果断放弃笔试，hah。

首先进行了自我介绍，项目上的简单介绍。然后问了熟不熟悉C++，没办法，只会C艹不会C++…

问题

1. ++i和i++的区别。

i++指的是先用i进行其他操作，在执行i+=1的操作。
++i指的是先执行i+=1的操作，在用i进行其他操作。

实际上，i++和++i的实现可以由以下函数模拟实现：

int i_plus_plus()
{
   int temp = i;
   i = i + 1;
   return temp; //注意这里返回的是没自增的i
}

int plus_plus_i()
{
    i = i + 1;
    return i; //这里返回的是自增过后的i
}

---

2. 能否在头文件进行函数定义？

理论上来说，可以在头文件中进行函数定义，但是需要保证此头文件只被一个源文件所包含。否则，在compiler链接.o文件时会出现重复定义的错误。并且，从编译效率的角度来说，如果把函数定义在源文件中，当修改函数体时，只需要重新编译源文件，能提高编译效率。

例如，如果将函数func()定义在头文件source.h中：

/* source.h */
void func()
{
    printf("Im defined at the .h file!\n");
}

当test.c和main.c两个源文件同时包含source.h头文件时，因为include操作属于preprocess，所以在编译之前preprocessor会把头文件的内容copy到源文件中。因此，在编译的时候，分别对于test.c和main.c来说其编译都能通过并且得到相应的test.o和main.o文件，但是在链接的时候则会出现

Duplicate symbols while linking .o files error.

因为两个.o文件中都包含了func的定义。如果非要将函数定义在头文件中，可以使用**static**使函数变为静态函数，即只能被当前包含了resource.h的.c文件调用，且不会产生重复定义错误。

注意这里有一个问题就是：虽然static func()被定义在了头文件resource.h中，但是只要是包含这个头文件的源文件test.c和main.c都可以调用func。因为static其实并不是限制作用域为在某个文件中，而是在一个compilation unit中。其中一个编译单元指的是它的.c文件和所有include的.h文件展开后的内容。所以源文件中还是可以调用定义在头文件中的静态函数。

其实也可以理解为，preprocessor会把include的头文件在源文件中都展开，所以定义在头文件中的static func()也会被复制到源文件中，所以static还是做到了可以在头文件中定义函数并且避免duplicate definition error.

还有一种关于在头文件中初始化全局变量的duplicate definition error可以查看here。

此外，还有一种常见的编译错误为头文件的循环依赖，可以使用预编译的#ifndef...#define...#endif来解决，详情here。

函数的定义与声明：

• 因为C是由上往下编译，所以被调函数如果在主调函数之后则无法识别，所以需要声明(declaration)来告诉compiler这是个函数。
  通常一个函数可以被声明多次，但是只能被定义一次。
• 函数的定义则是一个完整的函数体，包括类型，函数名，形参，形参类型和函数具体实现等等。函数在定义时需要系统开辟相应的内存来存储函数，其相对地址（函数的地址相对于程序基址的偏移量）在编译链接的时候则已经确定，但是绝对地址无法得知。

---

3. 在一个struct x中有一个成员a，在不定义x的情况下，如何得到a在struct中的偏移量？

可以将0值强制转换为该结构体类型的指针，虽然不能访问结构体中的成员（编译不通过），但是可以通过取地址操作取得成员变量的地址。对于取地址操作，编译器不会产生访问成员变量（在内存中进行读取）的代码，而是根据结构体的内存布局和该结构体的基址在编译期计算成员变量的偏移量，而又因为将0强转为结构体类型的指针，其自身地址为0，所以可以直接取得结构体中成员变量的地址。

#define OFFSET(struct, member) (size_t)&(((struct *)0)->member)
#define OFFSET_1(struct, member) (size_t)&(((struct *)1)->member)

int main()
{
    typedef struct x
    {
        int a;
        int b;
    }X;

    printf("%p\n", (X *)0);  // 0x00, 此时得到一个X型的空指针，即指向NULL
    printf("%p\n", (X *)1);  // 0x01
    printf("%p\n", &(((X *)0)->b));  // 0x04
    printf("%zd\n", OFFSET(X, b));  // 4,  通常使用macro来获得偏移量，需要zd来输出size_t
    printf("%zd\n", OFFSET_1(X, b) - 1);  // 4, 
    // 如果强转为1，计算偏移量时则需要减掉相应偏移量，因为此时初始地址不是0。

}

扩展： 对于结构体内部的内存字节对齐规则，here, Further Reading.

---

4. C 内存中堆栈的区别

here

---

5. new和malloc的区别

here

---

6. 有1000瓶水，其中只有一瓶有毒，有10只老鼠，如何一次找出那瓶有毒的水？

关键是考察如何应用二进制数来表示每一瓶水。因为有10只老鼠，其实也暗示了2^10=1024>1000，即可以用10位二进制数来无重复表示1000瓶水。然后让10只老鼠分别对应二进制的10位数，第一只老鼠喝右数第一位中值为1的水，第二只老鼠喝右数第二位中值为1的水，依次类推。最终，检查老鼠死亡状态，死亡老鼠所对应的位数记为1，没死的老鼠所对应的位数记为0，得到的二进制数化为十进制数则为有毒的那瓶水。

如图，第一只老鼠m1喝的水为二进制表示中右数第一位的值为1的水。如果第一只老鼠死亡，则可以说明有毒的水此位为1的水中，反过来也说明有毒的水在此位为0的水中。此时可以看到第一位数实际上已经过滤了一半（500瓶）的水。接着看第二只老鼠m2所在的第二位。同样地，m2喝了第二位中值为1的水，如果m2死了的话则说明有毒的水在第二位为1的水中，否则有毒的水在第二位为0的水中。需要注意的是，如果第一只第二只老鼠都死了，则说明有毒的水在第一位和第二位都为1的水中；或者第二只老鼠没死，第一只老鼠死了，则说明有毒的水在第二位为0，第一位为1的水当中…即老鼠越多则越能确定有毒的水的位置。如此往前推，则可以知道有毒的水为10只老鼠的死亡状态的组合，该组合的十进制值则是有毒的水的位置。

例如，如果最后10只老鼠的死亡状态(i.e. 10只老鼠所对应的二进制各个位数的值)为0000000001，则可以说明第一瓶就是有毒的水。或者说，如果第十只老鼠（从右数，即m10）死亡，也就是说有毒的水一定在第512瓶或它之后的水中。

其实这个题也可以直接由二分法解：

• 第一只老鼠喝1-500瓶；
• 第二只老鼠喝1-250，500-750；
• 第三只老鼠喝1-125，250-375，500-625，750-875；
• …
  比如，如果第一只老鼠死了，则说明有毒的水在1-500瓶当中，如果第二只老鼠没死，则说明有毒的水在250-500瓶中，如果第三只老鼠死了，则说明有毒的水在250-375瓶当中…如此继续，最终可以确定有毒的那瓶水。其实本质上这个方法和二进制表示一样，每只老鼠最终都会喝到500瓶水，只不过喝的500瓶水不一样。这样就可以通过每只老鼠的状态来分析出有毒的水。例如，在二分法中第一只老鼠其实相当于二进制表示中最左边的老鼠(i.e. m10)，它喝了前500瓶水；最后一只老鼠则相当于二进制方法中最右边的老鼠(i.e. m1)，其相当于每隔一瓶喝一次（例如，第1，3，5…瓶），总计也喝了500瓶。

Essentially, this is a problem of Bloom Filter.

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 gzrjzcx@qq.com