2022-09-20-微软软开苏一面

自我介绍

介绍下论文原理

写个快排
讲解思路
写个测试，没通过。。
debug，加了个 if （when那行）
还是报错
最后面试官说是不是要把l++，r--也放到if里，我也不确定对不对
然后就过了。。

#include <iostream>
#include <vector>
#include <random>
using namespace std;

void quicksort(std::vector<int> &a, int left, int right)
{
    if (left >= right)
        return;
    int pivot = left, l = left + 1, r = right;
    while (l < r)
    {
        while (l < r && a[l] <= a[pivot])
            l++;
        while (r > l && a[r] >= a[pivot])
            r--;
        if (a[l] > a[r]) // when a[pivot+1:] all are bigger than a[pivot], no need to swap
        {
            swap(a[l], a[r]);
            l++;
            r--; // l, l+1, r -> l+1
                 // l, r      -> r, l
        }
    }
    if (a[l] <= a[pivot])
    {
        swap(a[l], a[pivot]);
        pivot = l;
    }
    else
    {
        swap(a[l - 1], a[pivot]);
        pivot = l - 1;
    }
    std::cout << "l= " << left << ", r= " << right << ", a= ";
    for (auto &i : a)
    {
        std::cout << i << ", ";
    }
    std::cout << std::endl;
    quicksort(a, left, pivot - 1);
    quicksort(a, pivot + 1, right);
}

int main()
{
    srand(0);
    std::vector<int> a(5);
    a[0] = 6, a[1] = 1, a[2] = 10, a[3] = -5, a[4] = 4;
    quicksort(a, 0, a.size() - 1);
    for (auto &i : a)
    {
        std::cout << i << ", ";
    }
    std::cout << std::endl;
    return 0;
}

39分钟了，还有几分钟，讲思路
文件a 100GB 存url
文件b 100GB 存url
内存 2GB，找出文件a、b里都有的url，输出到文件c

v1
for a 每一块1GB
for b 每一块1GB
加载到内存，hash 找相同
O(n*n)

v2
对每个文件内部做去重
怎么去重？
把文件分成50块，假设hash值为100，对应到100个小hash文件上
遍历每一块2GB，存入到对应hash文件上
对单个hash文件内部去重
合并100个hash文件