Hulu笔试20220916
hulu的笔试难度是今年秋招碰到的最难的，每题都有点麻烦。我第一题看错题意耽误了不少时间，导致第二题没时间写完。第二题一开始也没有想到简单做法。
T1
题意：
输入k个访问记录，每条记录包含一个用户名和一个日期（yyyy-mm-dd，yyyy = 2021），然后输入一个n。求一个最小的时间窗口，使得这个窗口内的活跃用户（在窗口内访问过的用户就是活跃用户）>=n，输出最小的窗口大小。
解法：
先要对日期字符串进行处理，转换成int。然后维护一个滑动窗口计数，用户名用一个哈希表维护一下。
我没注意到在不同天访问的同一个用户只算一次，结果调试了很久，以为不能跳出去所以又一直在写这题，写了大概35分钟，后面的题就寄了。
#include<iostream>
#include<set>
#include<unordered_map>
#include<algorithm>
using namespace std;
int days[13]{0,31,28,31,30,31,30,31,31,30,31,30,31};
int date(const string& t){
int m = atoi(t.substr(5,2).c_str());
int d = atoi(t.substr(8,2).c_str());
int ans = 0;
for(int i = 0;i<m;++i)
ans += days[i];
ans += d-1;
return ans;
}
pair<int,string> p[1000];
int main(){
int k;cin>>k;
string a,b;
for(int i = 0;i<k;++i){
cin>>a>>b;
int t = date(b);
pair<int,string> pp(t,a);
p[i] = pp;
}
sort(p,p+k);
int n;
cin>>n;
int l = 0, r = 0;
int cnt = 0;
unordered_map<string ,int> ma;
int ans = 366;
while(r<k || cnt >= n){
if(cnt<n){
if(ma[p[r].second] == 0) ++cnt;
++ma[p[r].second];
++r;
}
else{
ans = min(ans,p[r-1].first-p[l].first+1);
--ma[p[l].second];
if(ma[p[l].second] == 0) --cnt;
++l;
}
}
if (ans == 366) cout<<-1<<endl;
else cout<<ans<<endl;
} T2
题意：
输入一个xml格式的字符串，只包含标签和文本，标签没有属性。求标签树的层次遍历。
样例：
input: <root><1><2></2></1><3><6/></3><3/><4></4><5><7/><8><9><10><2/></10></9></8></5></root>
output: root 1 3 3 4 5 2 6 7 8 9 10 2
解法：
对字符串进行分割之后，实际上给的是一个dfs的过程，我一开始想建树再bfs，但其实不用这么麻烦，dfs过程都给你了，就顺序遍历这个dfs过程中间标记一下访问到的结点的深度就可以。比赛时没写完，寄了。
#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<stack>
using namespace std;
bool debug = 0;
int main(){
string s;
if(debug) s = "<root><1><2></2></1><3><6/></3><3/><4></4><5><7/><8><9><10><2/></10></9></8></5></root>";
else cin>>s;
int pos =0;
int depth = 0;
vector<pair<int,string>> V;
while(s.find('<',pos)!=string::npos){
pos = s.find('<',pos);
int pos2 = s.find('>',pos);
string v = s.substr(pos+1,pos2-pos-1);
pos = pos2+1;
if (v[0] == '/') {
depth --;
// out
}
else if (v[v.length()-1] == '/') {
V.push_back(pair<int,string>(depth+1, v.substr(0,v.length()-1)) );
// in and out
}
else{
V.push_back( pair<int,string>(++depth, v) );
// in
}
}
stable_sort(V.begin(),V.end());
for(auto p:V){
cout<<p.second<<" ";
}
} T3
菜鸡根本没看到第3题，希望有大佬补充题意
