淘天暑期实习算法终于oc

📍面试公司：淘天👜面试岗位：Java📖面试问题：1.个人介绍2.项目询问3.线程池相关，什么时候复用线程？什么时候创建线程？任务队列满了怎么处理？线程池的核心线程是线程池创建时就初始化了？4.联合索引（abc)，当查询ab, ac会走索引么？ac场景呢？5.当底层建了abc的联合索引，底层会建a,ab, abc这3个索引么？6.聚簇索引和非聚簇索引的区别是什么？7.超多页分页查询场景，查第10w页的场景查询性能可能会下降，该怎么优化？8.笔试题，数字（0～99999）转中文，例：1024 输出：一千零二十四🙌面试体验：面试体验还好，大部分都答上了#软件开发笔面经#

第一题 小红拿到了一个01串，她可以进行最多一次操作：选择一个连续子串，将它们所有字符取反（0变1，1变0）。小红想知 道，最终1字符数量的最大值是多少？ 输入描述 一个仅由0和1字符组成的字符串，长度不超过200000 输出描述 一个整数，代表'1′数量的最大值。 样例输入 101001001 样例输出 7 解法一 题目转化为找出含0最多的连续子串，这样翻转完后1才能最多。先求所有1的数量为sum，再求子串数位的和（使用前缀和），需要把所有的0当成-1，求与sum差值最大的子串。 import java.util.Scanner; public class taotianT1 { ...

#淘天笔试# #淘天# #笔试# 考虑换根DP，先随便找个点做根，每个点只统计这个有根树下它的子树对它的贡献，也就是if(color[u] != color[v]) color[u] += color[v];这样我们只能统计出子树的贡献，我们还需要父亲的贡献，父亲的贡献我们考虑扩展并查集，在dfs过程中顺便合并一下就能够得到每个点所在并查集的size，如果一个点和它的父亲不同颜色，那么就是相同并查集，直接用并查集size减去dp求出的子树贡献就是父亲的贡献，然后第二遍dfs，把每个点任意一种颜色都试一下，我们提前知道子树的贡献是多少，可以根据现在我们变的颜色统计一下现在的子树和，看看父亲跟他现在是不是一个颜色，是的话不加贡献，不然加上贡献，和ans取最大值即可。代码如下：#include# include#include# include#include# include#include# include#include# include#include# include#includeusing ll = long long;using ull = unsigned long long;const int maxn = 1e6 + 5;int fa[maxn],sum[maxn],siz[maxn];std::string color;char col[] = {'R','G','B'};int ans  = 0;int find(int x){    return x == fa[x] ? x : find(fa[x]);}void merge(int x,int y){    x = find(x), y = find(y);    if(x == y) return;    siz[x] += siz[y];    fa[y] = x;}std::vector g[maxn];void dfs(int u,int fa){    sum[u] = 1;    for(int i = 0;i < g[u].size();i++){        int v = g[u][i];        if(v == fa) continue;        dfs(v,u);        if(color[u] == color[v]){            sum[u] += sum[v];            merge(u,v);        }    }}void dfs2(int u,int fa){    int sfa = (find(u) == find(fa)) ? siz[find(u)] - sum[u] : siz[find(fa)];    for(int i = 0;i < 3;i++){        char c = col[i];        int s = 1;        for(auto& v : g[u]){            if(v == fa) continue;            if(c != color[v]) s += sum[v];        }        if(c != color[fa]) s += sfa;        ans = std::max(ans,s);    }    for(auto& v: g[u]){        if(v == fa) continue;        dfs2(v,u);    }}void solve(){    int n;    std::cin >> n;    std::cin >> color;    for(int i = 1;i <= n;i++){        siz[i] = 1;        fa[i] = i;    }    for(int i = 0;i < n - 1;i++){        int u,v;        std::cin >> u >> v;        g[u].push_back(v);        g[v].push_back(u);    }    dfs(1,0);    dfs2(1,0);    std::cout << ans << '\n';}int main() {    int T;    T = 1;    while(T--) solve();    return 0;}

部门：做淘宝首页和流量推送策略250302 70min实习拷打。这项目你感觉你在这个过程中有哪些亮点以及能进行一下总结吗？这个项目的时候，那你有没有达到你们预期？以及有没有还能进行一些改进的点？    进程中有一共有哪些状态，以及它这些状态是怎么去流转的？进程和线程有啥区别？    Java数组、ArrayList和LinkedList有啥区别？HashMap的工作原理？exception 和 error 它的一个区别有啥呀？throw 和 throws 的区别？    重定向和转发，forward和redirect两者的区别？    介绍一下悲观锁和乐观锁？    spring 里面bean的生命周期是怎么去创建和消亡的呀？spring bean 的自动生成的一个原理？    MySQL里面的那个索引的作用是啥呀？它有什么优缺点吗？B+树索引如何实现的呢？ left semi join和 left anti join的区别？count(1), count(*)和count字段的区别？    哪些场景是去使用Redis？Redis 和 memcache有啥区别？什么是缓存穿透？以及我们在该怎么去解决呢？ Flink 有用过没有？Hive会出现一些数据倾斜，有了解吗？场景题：给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url算法题：判断是否是回文整数SQL题：事件表event表有3个字段event_id：事件id，event_time：事件时间，user_id：用户id。使用SQL查询同一用户两个事件的时间间隔。输出4列：事件ID，事件时间，用户id，时间间隔