自我介绍：略

经常使用的容器

map k,v可以存储操作id和函数，作为回调。

sort()使用了哪种排序算法

sort() 底部使用了多种排序算法：快排，堆排

当数据量大，分布随机时，使用快速排序
数据量小，使用插入排序
递归深度过深时使用堆排序

排序算法的使用场景

快排：无序数组效率会很高，但是有序数组效率会很低，所以快速排序只适用于无序数组。
归并排序：内存有限的情况下，可以使用多路归并
插入排序：基本有序的数据，适合用插入排序。

智能指针

weak_ptr可以提升为shared_ptr吗？可以。

shared_ptr: 会使用计数器来记录引用次数，当引用次数为0时，释放对象。
weak_ptr：weak_ptr实现弱引用，可以通过.lock() 提升为 shared_ptr

使用一段代码体现C++面向对象的思想

首先，C++面向对象的特性有三个

封装
继承
多态

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Base{
   public:
   Base()
   {
       std::cout << "Base constructoer" << std::endl;
   }
   virtual void getObjName()
   {
       std::cout << "This is a Base object" << std::endl;
   }
   virtual ~Base()
   {
       std::cout << "Base destructor" << std::endl;
   }
};
class Derived:public Base{
   public:

   Derived()
   {
       std::cout << "Derived constructoer" << std::endl;
   }
   virtual void getObjName() override
   {
       std::cout << "This is a Derived object" << std::endl;
   }
   virtual ~Derived()
   {
       std::cout << "Derived destructor" << std::endl;
   }
};
int main()
{
   Base *p = new Derived();
   p->getObjName();
   delete p;
}

这段代码会输出:

1
2
3
4
5


Base constructoer
Derived constructoer
This is a Derived object
Derived destructor
Base destructor

面试官接着问了两个类的大小，回答没有考虑继承时的虚函数指针，所以回答的两个都是1。实际上因为对象会有一个虚函数指针，对于个一个64位的机器，指针的大小是8字节，所以两个类的大小都是8字节。

1

std::cout << sizeof(Base) << " " << sizeof(Derived) << std::endl;

输出

1

8 8

实现字符串数字相加，相减

当时实现时考虑的场景太多了，所以没有实现。而且要注意，做相加或相减时，要将字符转为整数。所以具体实现时，要考虑

实现基础的正数相加
大数减小数
特殊情况，特殊判定

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94


// 1. 首先要将两个字符串的前缀0 去掉
std::string trimLeadingZeors(const std::string &str)
{
    size_t nonZeroIdx = str.find_first_not_of('0');
    if(nonZeroIdx == std::string::npos)
        return '0'; // 此时全部是0
    return str.substr(nonZeroIdx);
}
// 2. 比较两个字符串数字绝对值的大小
bool isAbsGreaterOrEqual(const std::string &a, const std::string &b)
{
    std::string aTrimmed = trimLeadingZeors(a);
    std::string bTrimmed = trimLeadingZeors(b);
    if(aTrimmed.size() != bTrimmed.size())
        return aTrimmed.size() > bTrimmed.size();
    return aTrimmed > bTrimmed;
}
// 3. 两个整数字符串加法
std::string addStrings(const std::string &a, const std::string &b)
{
    std::string result;
    int carry = 0, sum=0;
    int i = a.size()-1, j = b.size()-1;
    while(i>=0 || j>=0 || carry)
    {
        int digitA = (i>=0)?a[i--]-'0':0;
        int digitB = (j>=0)?b[i--]-'0':0;
        sum = digitA + digitB + carry;
        carry = sum / 10;
        result.push_back(sum % 10 + '0');
    }
    std::reverse(result.begin(), result.end());
    return result;
}

// 4. 字符串减法， a>=b
std::string subStrings(const std::string &a, const std::string &b)
{
    std::string result;
    int borrow = 0, diff=0;
    int i = a.size()-1, j = b.size()-1;
    while(i>=0 || j>=0)
    {
        int digitA = (i>=0)?a[i--]-'0':0;
        int digitB = (j>=0)?b[i--]-'0':0;
        diff = digitA - digitB - borrow;
        if(diff < 0)
        {
            diff += 10;
            borrow = 1;
        }else 
        {
            borrow = 0;
        }
        result.push_back(diff + '0');
    }
    std::reverse(result.begin(), result.end());
    return result;
}
// 5. 实现 任意类型的加减
std::string add(const std::string &num1, const std::string &num2) {
  bool isNum1Negative = (num1[0] == '-');
  bool isNum2Negative = (num2[0] == '-');

  std::string absNum1 = isNum1Negative ? num1.substr(1) : num1;
  std::string absNum2 = isNum2Negative ? num2.substr(1) : num2;

  if (!isNum1Negative && !isNum2Negative) {
    // 都是正数
    return addStrings(absNum1, absNum2);
  } else if (isNum1Negative && isNum2Negative) {
    // 都是负数
    return "-" + addStrings(absNum1, absNum2);
  } else if (isNum1Negative) {
    // num1负，num2正
    if (isAbsGreaterOrEqual(absNum1, absNum2)) {
      return "-" + subtractStrings(absNum1, absNum2);
    } else {
      return subtractStrings(absNum2, absNum1);
    }
  } else {
    // num1正，num2负
    if (isAbsGreaterOrEqual(absNum2, absNum1)) {
      return "-" + subtractStrings(absNum2, absNum1);
    } else {
      return subtractStrings(absNum1, absNum2);
    }
  }
}
// 字符串相减 任意
std::string subtract(const std::string &num1, const std::string &num2) {
  std::string negatedNum2 = (num2[0] == '-') ? num2.substr(1) : "-" + num2;
  return add(num1, negatedNum2);
}

最后

倒霉倒霉倒霉。面试期间，快手电话没接到，应该是约面的。结束之后去官网看已经挂了。此前快手三面因为面试官的问题有一个是特定场景，跟C++不一样没有答出来。讲解项目面试官说他没听懂😅。

自我介绍：略#

经常使用的容器#

sort()使用了哪种排序算法#

排序算法的使用场景#

智能指针#

使用一段代码体现C++面向对象的思想#

实现字符串数字相加，相减#

最后#