腾讯wxg2020秋招面经（已拿offer）

本人在春秋招备战过程中的记录和总结已发布到语雀文档，欢迎学习和参考。

语雀文档：https://www.yuque.com/ouweibin/interview
个人Github：https://github.com/ouweibin

一面

1. 给定一个数组，找出其中没有出现过的最小正整数
2. 一颗二叉树，不能同时取相邻两个层级节点的值，问能取到和的最大值是多少
3. 实现memcpy

二面

1. 给定两个字符串 s1 和 s2 ，从 s1 中删除在 s2 中出现过的字符
   char * Remove( char * s1, const char * s2 )
2. 实现二叉树左右子树的交换
3. 两个排序的数组分别含有m和n个数，找到两个排序数组中的中位数，时间复杂度为O(log(m+n))

三面

1. 64位机器上如下代码，请填空

   char str[] = "Hello";
   char* pstr = str;
   const char* str_list[] = {"Hello", "World"};
   void* pbuf = malloc(100);
   int n = 10;

   请计算：

   sizeof (str )
   sizeof ( pstr )
   sizeof ( str_list )
   sizeof ( pbuf )
   sizeof ( n )
   void func ( char str[100]) {
       sizeof( str )
   }

2. 请问程序的输出结果是：

   class A {
   public:
       virtual ~A() { std::cout << "A::~A" << std::endl; }
       virtual void func() { std::cout << "A::func" << std::endl; }
   };
   class B : public A {
   public:
       ~B() { std::cout << "B::~B" << std::endl; }
       void func() { std::cout << "B::func" << std::endl; }
   };
   
   void TestFunc(A *pA) {
       pA->func();
   }
   
   int main(int argc, char** argv) {
       A *pA = new A;
       B *pB = new B;
       TestFunc(pA);
       TestFunc(pB);
       delete pA;
       delete pB;
       return 0;
   }

3. 请编写一个string类，实现：构造函数、析构函数、拷贝构造函数、operator =、c_str方法（返回const char*）

4. 后台开发场景中经常会使用到“定时器（Timer）”服务，比如启动Timer定期输出日志，或网络断连后启动Timer定期尝试重连；现在需要自行设计一个Timer，需求/约束如下：

   1）对外表现得颗粒度为秒级;
   2）能处理海量定时任务；
   3）单机、单线程实现；

   请回答：

   1）Timer的实现思路；
   2）补全Timer对外服务接口的签名（返回值、参数）：

   Schedule(); // 设置定时任务
   Cancel();   // 取消定时任务

四面

1. 有64匹马，一个赛场8个跑道，要比赛决出前4名，问充分必要条件最少需要多少场。(要求不允许记时，可以推导，比如A > B, B>C => A>C)，请写出解题思路

2. 下面一段函数实现带有S和*两种通配符的字符串的匹配功能。其中：$表示长度大于0的数字串，*表示任意长度的字符串。要求：按照自己对于算法的理解填写该函数的5个空白。可以应用strcmp，strcat，strlen等字符串操作函数，不要应用其它的C或者C++的库函数。请注意：必须是完全匹配才能返回true，比如21.txt和2a.txt可以匹配2*.txt，2.tx或者2.txta不能匹配*.txt。通配符可能出现多次。函数的参数与返回值的说明请参见函数的注释

   // 功能描述：表达式是否匹配成功，$表示长度大于0的数字串，*表示任意长的字符串
   // 输入参数: @pRule，以'\0'结束的字符串，表示规则；
   //           @pStr，以'\0'结束的待匹配的字符串；
   // 返回值：true：匹配成功；false：匹配失败
   bool IsRegularMatching(const char* pRule, const char* pStr)
   {   
       const char* pTempRulePtr = pRule;   
       const char* pTempStrPtr = pStr; 
       unsigned int dwCount = 0; 
       unsigned int dwStrLen = (unsigned int)strlen(pStr);
       while ((*pTempRulePtr != '\0') && (*pTempStrPtr != '\0'))
       {
           switch (_______________)
           {       
               case '*':   
                   pTempRulePtr = pTempRulePtr + 1;           
                   if (*pTempRulePtr == '\0')
                       return true;
                   else        
                   {
                       dwStrLen = (unsigned int)strlen(pTempStrPtr);
                       for (dwCount = 0; dwCount < dwStrLen; dwCount++)
                       {
   
                           if (_______________) 
                               return true;
                       }
                   }           
                   break;
               case '$':
                   if (_______________)
                       return false;          
                   while ((*pTempStrPtr != '\0') && (*pTempStrPtr >= '0')
                          && (*pTempStrPtr <= '9'))
                       pTempStrPtr++;
                   pTempRulePtr++;
                   break;      
               default:           
                   if (*pTempRulePtr != *pTempStrPtr)
                       _______________;          
                   ++pTempRulePtr;          
                   ++pTempStrPtr;          
                   break;     
           }
       }
   
       if ((*pTempRulePtr != '\0') && (*pTempStrPtr == '\0'))
       {      
           if (strcmp(pTempRulePtr, "*") == 0)       
               return true;
       }
       else 
       {     
           _______________;
       }
       return false;
   }

3. 从一个无序的存放了N个数文件中，找到最大的M个。要求给出一个快速的方法， 请说明思路

4. 在机场中，你想从A点前往B点。（为了将问题简化，假设机场是一条线性通道。）一些区域有电动扶梯（双向的），另一些区域没有。你的步行速度恒定为v，电动扶梯的运行速度为u，因此在扶梯上，你的实际速度为v+u。（显然，你不会搭乘与你前进方向不一致的扶梯。）你的目标是尽可能快地从A点到达B点。

   1) 假定你需要暂停片刻，比如系鞋带。请问你应该在电动扶梯上系，还是在没有上电动扶梯时系？假定两种情况下，系鞋带的时间相同。
   2) 假定你有有限数量的多余能量，用来奔跑。在跑动时，你的速度提高到v'（如果在电动扶梯上，就相应为v'+u）。请问你应该在电动扶梯上跑，还是在没有上电动扶梯时跑？假定两种情况下，你可供奔跑的能量相同。

5. 反转单链表（在原链表上反转）

   struct LinkNode {
       int value;
       struct LinkNode * next;
   };
   
   void reverseList(LinkNode* head)