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文件