字节跳动架构一面记录

自我介绍，大学做过什么感觉可以拿出来一说的事情

8个球，有一个球质量不一样，一个天平最少称量几次称出来，一般化到n个球呢？

    这个问题我和面试官讨论半天。

    我说是应该分三组，面试官觉得应该分两组。

    面试的时候没弄明白，面试完之后一下就反应过来了。

    不管知不知道问题球的轻重，三组用两次称量就可以知道有问题的球在哪一组里，是轻还是重。

    不过可惜面试的时候没反应过来。

C++智能指针的实现（引用计数），是否线程安全。

线程和进程的区别。

进程的内存结构是什么样的。

虚拟内存和内存有什么区别。

虚拟内存是如何实现的。

C++的STL里面map和unordered_map，底层分别是什么。

红黑树的结构是什么样的，插入时候是一个什么过程。

git rebase的作用，和reset有什么区别

编程：

链表翻转

    挺水的一题，但面试的时候太紧张了卡了四五分钟。

给一个字符串，输出这个字符串所有字符的全排列

    这题和面试官卡了好久。

    我用了一个vector<pair<char,int> >存储每个字符出现的次数，然后把这个vector当参数，写了一个函数，函数的作用就是根据这个vector生成字符串的全排列。

    具体实现的时候是循环检查vector的每一个元素，然后如果这个字符出现次数是零，就continue。

    循环体内递归调用，调用前提走一个字符，就是相应元素的second--，调用后再把second加回来，然后把提走的字符加在返回的所有字符串后面，添加进结果列表。

    最后输出的是逆字典序的全排列。

    但面试官好像没太看明白，质疑我这个递归调用什么时候终止。

    我说假设所有字符出现的总数是S，每次调用S都会比上一次少1，当S=0的时候就会终止递归。

    面试官好像一脸将信将疑，搞得我也有点不自信。

    然后面试官说时间不多了，这题先过。

    面试结束以后我把代码从浏览器拷进IDE，修正了一些typo，最后发现输出符合预期。

    不知道面试官有没有给我扣分。

vector<string> build(vector<pair<char,int> > ch){
    vector<string> result,tmp;
    for(size_t i = 0;i<ch.size();i++){
        if (ch[i].second==0){
            continue;
        }
        ch[i].second--;
        tmp = build(ch);
        if (tmp.size() == 0){
            result.push_back(string("")+ch[i].first);
        }
        for(size_t j=0;j<tmp.size();j++){
            result.push_back(tmp[j]+ch[i].first);
        }
        ch[i].second++;
    }
    return result;
}

vector<string> find(string str){
    int ascii[128]={0};
    vector<pair<char,int> > ch;
    for(size_t i=0;i<str.size();i++){
        ascii[str[i]]++;
    }
    for(int i=0;i<128;i++){
        if (ascii[i] !=0){
            ch.push_back(make_pair((char)i,ascii[i]));
        }
    }
    return build(ch);
}

C++多线程，一个线程写，其他线程读

    直接用了C++11新特性来实现，STL的thread，然后加锁，线程尝试获得锁，成功的就写。

感觉心里很虚，昨天阿里巴巴笔试，电脑没装chrome折腾了四五分钟，然后上来第一题思路错了半个小时，最后直接爆0。

今天面试表现感觉也就中规中矩，问的东西都很水，结果我也答得磕磕绊绊，希望能顺利吧。