0729 字节跳动提前批三面面经

时长：1小时

体验：问的都是我意想不到的问题，问八股很少

介绍项目
问项目细节、写项目实现的伪代码（人傻了，随便写了点）
场景题：用户反应头条新闻刷不出来怎么排查问题？要从客户端角度考虑
代码到可执行文件的过程？（唯一八股）追问词法分析语法分析语义分析具体做了什么？
算法题：应该是部门自己出的，大概意思是：西瓜视频想找到高频词是哪些，给了一些敏感词需要过滤。输入：unordered_map<string,int>表示词汇、频率，set<string>表示敏感词，int k表示前k个高频词，返回vector<string>前k个高频词（不含敏感词)。主要考察排序+topK+unordered_map+set的使用吧，面试官要求尽量时间复杂度低。sort自定义排序不行，可能就想让自己写排序吧（优化快排或者堆排），没全写出来，写了80%吧

----0803更新，自己用堆排序写了一份代码，如果有问题请指出----

// 西瓜视频高频词.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<vector>
#include<iostream>
#include<unordered_map>
#include<string>
#include<unordered_set>
using namespace std;

void adjustHeap(vector<pair<string, int>>& arr, int begin, int end){
	int dad = begin, son = 2 * dad + 1;
	while (son <= end){
		if (son + 1 <= end&&arr[son].second > arr[son + 1].second) son++;
		if (arr[dad].second < arr[son].second) return;
		else{
			swap(arr[dad], arr[son]);
			dad = son;
			son = 2 * dad + 1;
		}
	}
}

void buildHeap(vector<pair<string, int>>& arr){ //建立小顶堆
	int len = arr.size();
	for (int i = len / 2 - 1; i >= 0; i--){
		adjustHeap(arr, i, len - 1);
	}
}


vector<string> getHotWords(unordered_map<string, int> mp, unordered_set<string>& st, int k){
	vector<pair<string, int>> heap(k); //维护小顶堆，每个节点为<词汇，频率>
	vector<string> res;
	int i = 0;
	bool hasBuild = false;

	for (auto p : mp){
		string curWord = p.first; //词汇
		int count = p.second; //词频
		if (i < k){ //加入小堆顶,先加入k个，建堆
			if (st.find(curWord) == st.end()){ //如果不是敏感词
				heap[i] = { curWord, count };
				i++;
			}
		}
		else{
			if (hasBuild==false){
				buildHeap(heap);
				hasBuild = true;
			}
			else{
				if (count > heap[0].second&&st.find(curWord)==st.end()){
					heap[0] = { curWord, count };
					adjustHeap(heap, 0, heap.size() - 1);
				}
			}
		}	
	}
	for (int i = 0; i < heap.size(); i++){
		res.push_back(heap[i].first);
		//cout << res[i] << endl;
	}
	return res;
}



int _tmain(int argc, _TCHAR* argv[])
{
	unordered_map<string, int> words{ 
	{ "易烊千玺", 10000 },
	{ "杨迪", 5000 },
	{ "李晓峰", 23 },
	{ "张三", 123 },
	{ "李四", 1 },
	{ "王源", 90000 },
	{ "宋亚轩", 200000 },
	{ "刘亦菲", 300 }
};
	unordered_set<string> st;
	st.insert("易烊千玺");
	st.insert("宋亚轩");

	int k = 1;
	cout << "前" << k << "个高频词为： " << endl;
	vector<string> ret=getHotWords(words, st, k);	
	for (int i = 0; i < ret.size(); i++){ //输出高频词
		cout << ret[i] << endl;
	}
	return 0;
}