京东22届校招一面（50min）已挂

部门：技术与数据中心-数据与智能-智能优化部

1、问项目和实习项目

因为我两个项目都比较水，其实没啥问的，但这次问了近20分钟，第一次有人问那么细，问得我都怀疑自己做没做过这个项目了。

其中问了我的聊天室项目是用的TCP还是UDP？

我答TCP，面试官反问：如果你有100个好友在线，但你只跟一个好友聊天，那么其他99个好友的连接都要一直保持吗？然后给我解释了像微信、QQ这类聊天软件都是基于UDP的。

2、了解C++新特性吗？说一下move的用法？说一下智能指针？

C++11的新特性这块我其实比较薄弱，因为没有动手写过，都只记得一些概念。但是现在面试问得实在是太多了，move右值引用、智能指针这些一定要背牢。我就把简单的概念给面试官说了一遍。

追问：unique_ptr能作为返回值吗？unique_ptr是怎么实现独有权的？

第一问我答不知道，第二问我也不知道，但我猜是把构造函数、拷贝构造函数和赋值运算符声明为私有了。面试官说答的方向是对的，unique_ptr其实是对拷贝构造和赋值运算符使用了delete关键字，禁用了。后来我查了下资料：unique_ptr没有拷贝构造，赋值运算符，但是有move构造，move赋值，unique_ptr对象可以被函数返回。

3、说说map和unordered_map的区别？

map底层是红黑树，增删查的时间复杂度为O(logN)，其中键值是有序的；
unordered_map底层是哈希表，增删查的时间复杂度为O(1)；

追问unordered_map是否线程安全？需不需要用锁？

这问的太细了，我直接说不知道，然后反问面试官：需要用锁吗？面试官说需要。

我后来查了下资料，根据C++标准：任何对STL集合的读取访问都是线程安全的。写入操作不是线程安全的。

4、编程题：替换空格

面试官很照顾我，给了我一个剑指offer第五题原题：将字符串中的空格替换成%20，然而不争气的我又忘了最优解法怎么做了。。我上来就直接写了个最差解法，声明另一个字符串，遍历原字符串，遇到空格就在新字符串上累加%20，否则直接累加原字符串的字符。面试官说空间复杂度太高，我又想了老半天，没想出来，求面试官给点提示。面试官说我应该先计算替换后的字符串长度，再从后往前遍历，原地构造字符串，我突然明白了，编写代码如下：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    getline(cin, s);

    int old_length = s.length(), real_length = 0;
    for (int i = 0; i < s.length(); ++i)
    {
        if (s[i] == ' ') real_length += 3;
        else real_length += 1;
    }
    //注意resize后s的length值等于real_length，所以前面我要保存一个old_length
    s.resize(real_length);

    real_length -- ;
    for (int i = old_length - 1; i >= 0; -- i)
    {
        if (s[i] == ' ')
        {
            s[real_length -- ] = '0';
            s[real_length -- ] = '2';
            s[real_length -- ] = '%';
        }
        else s[real_length -- ] = s[i];
    }
    cout << s << endl;
    return 0;
}