本篇大概分两部分，一部分是刷八股文，一部分是应试进度。本文不定时更新。就我找summer的体验来看，找工作真的非常痛苦，一方面是因为我面试时很容易紧张+大脑空白，另一方面是我的开发能力确实也不咋地，但是算法研发又不是那么熟悉。

八股文

又要开始背八股文了，先背背看看吧。虽然我觉得被拷打很丢人，而且背八股文真的很死板很无趣，但是也没办法，找工作就是这样的。本文不定时更新，包含被拷打的问题以及自己平时不太会的问题。

链表环的入口点或交点

使用一个快指针和慢指针，其中快指针速度是慢指针的两倍，然后快指针和慢指针会相遇在环内。假设链表里开头到环入口点长度为A，相遇处距离环的入口点长度为B，环里还剩下C，则有

$$ A + B = A + n(B+C) + B $$

其中n为快指针转了n圈。此时有$A = n(B+C) - B = (n-1)(B+C) + C$。再搞一个head指针与慢指针一起走，它俩会相遇在环的入口点，因为head走了A，而慢指针走了A也就是转了n-1圈走了C，两者会相遇。

同理，问两个链表相交的点也一样。初始设两个指针分别指向两个链表的头，一起移动（如果到末尾了换成另一个链表的头），直到相交，两者会走在交点处走过同样的距离（A+C+B 与 B + C + A）。

快排与归并与堆排

void quicksort(int a[], int l, int r){
    if(l < r){
       int i = l, j = r, pivot = s[l];
       while(i < j){
           while(j > i && s[j] > pivot)j--;
           if(j > i)s[i++] = s[j];
           while(j > i && s[i] < pivot)i++;
           if(j > i)s[j--] = s[i];
       }
       s[i] = pivot; //别忘了这句
       quicksort(a, 0, i-1);
       quicksort(a, i+1, r);
    }
}

void mergesort(int a[], int l, int r){
    if(l >= r)return;
    int mid = (l + r) / 2; // l + (r - l) / 2 可以防止l + r过大溢出
    mergesort(a, l, mid);
    mergesort(a, mid+1, r);
    merge(a, l, mid, r);
}
void merge(int a[], int l, int mid, int r){
    int *temp = new int[r - l + 1];
    int cur = 0;
    int h1 = l, h2 = mid+1;
    while(h1 <= mid && h2 <= r){
        if(a[h1] < a[h2])temp[cur++] = a[h1++];
        else temp[cur++] = a[h2++];
    }
    while(h1 <= mid)temp[cur++] = a[h1++];
    while(h2 <= r)temp[cur++] = a[h2++];
    for(int i = low; i <= r; i++){
       a[i] = temp[i - low];
    }
    delete []temp;
}


void MaxHeap(int arr[], int now, int heap_size){
    int left_son = now * 2+1, right_son = left_son + 1;
    while(left_son < heap_size){
        int largest = right_son < heap_size && arr[left_son] < arr[right_son] ? right_son : left_son;
        if(vec[now] >= largest)return;
        swap(arr[now], arr[largest]);
        now = largest;
        left_son = now * 2 + 1;
        right_son = left_son + 1;
    }
}
void HeapSort(int arr[], int n){
    if(n < 2)return;
    for(int i = (n - 1) / 2; i >= 0; i--){
        MaxHeap(arr, i, n);
    }
    swap(arr[0], arr[--n]);
    while(n){
        MaxHeap(arr, 0, n);
        swap(arr[0], arr[--n]);
    }
}

单例模式

class Singleton {
public:
    static Singleton& GetInstance() {
        static Singleton instance;
        return instance;
    }
private:
    Singleton() = default;
    ~Singleton() = default;
    Singleton(const Singleton&) = default;
    Singleton& operator=(const Singleton) = default;
};

def singleton(cls):
    _instances = {}
    def inner():
        if cls not in _instances:
            _instances[cls] = cls()
        return _instances[cls]
    return innter()


@singleton
class single(object):
    def __init__(self):
        pass

C++ 多线程交替打印

#include <iostream>
#include <thread>

std::mutex mtx;
std::condition_variable cv;
std::string flag("A");

void PrintA(){
    while(True){
        std::unique_lock<std::mutex> lck;
        while(flag == "B"){
            cv.wait(lck);
        }
        std::this_thread::sleep_for(std::chrono::seconds(1));
        std::cout << "A" << std::endl;
        flag = "B";
        cv.notify_all();

    }
}

void PrintB(){
    while(True){
        std::unique_lock<std::mutex> lck;
        while(flag == "A"){
            cv.wait(lck);
        }    
        std::this_thread::sleep_for(std::chrono::seconds(1));
        std::cout << "B" << std::endl;
        flag = "A";
        cv.notify_all();
    }
}

int main(){
    std::thread t1(PrintA);
    std::thread t2(PrintB);
    t1.join();
    t2.join();
    std::cin.get();
}

C++ 一个类只能在栈 或者 堆 上创建

class OnlyStack{
private:
    void* operator new(size_t){}
    void operator delete(void* ptr){}
public:
    OnlyStack(){}
    ~OnlyStack(){}
};

class OnlyHeap{
protected:
    OnlyHeap(){}
    ~OnlyHeap(){}
public:
    static OnlyHeap* create(){
        return new OnlyHeap();
    }  
    void destroy(){
        delete this;
    }
};

并查集

vector<int> roots(n, 0);

int find(int k){
    if(roots[k]==k)return k;
    return roots[k]=find(roots[k]);
}

for(int i = 0; i < n; i++){
    roots[i] = i;
}
// union x & y
roots[find(x)] = find(y);

秋招进度

已投：华为，小红书，快手，字节，百度，美团，腾讯

小红书（没有面试）

字节一面（8.24）

快手一面（8.22）（没消息）

阿里淘天一面（8.29）

美团一面（8.28）（凉）

腾讯一面（8.30）

字节二面（9.1）