字节跳动2026届实习生招聘计划近日正式官宣，用一个字总结就是“夯”。
这次开放的Offer数量首次突破了7000大关，堪称史上最大规模的转正实习生招聘项目。7000个HC是什么概念？绝大多数互联网公司的员工总数，可能都达不到这个数字的十分之一。
不过，大厂高调放出海量HC，却在“转正率”上“做文章”的事情之前也时有发生，导致最终能留下的应届生比例可能连10%都不到，这对于满怀期待的应届生来说无疑是一种打击。
字节这次显然考虑到了大家的顾虑，在公布HC数量的同时，特别说明转正率高于50%。这意味着，每两位参与实习的应届生中，至少有一位能够成功转正。
不仅HC数量和转正率可观，实习生的待遇水平也有所提升。这很可能得益于字节跳动此前的全员信，其中提到“公司将继续加大人才投入，提高薪酬和激励回报的天花板，确保员工薪酬竞争力和激励回报在各个市场都领先于头部水平”。
为了让大家有个直观对比，这里整理了一份当下主流互联网大厂的实习待遇概览（数据来源于公开信息整理，仅供参考）：
至于如何参与投递，通过官网渠道当然可以。但如果有机会的话，建议走一下内推渠道，流程通常会更快一些。内推码可以在各大技术社区或论坛里找找，很多热心的在职员工或校友都会分享。
聊完招聘，我们来一道经典的算法题换换脑子。这道题在面试求职和算法刷题中都很常见。
题目描述
平台：LeetCode
题号：933
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
RecentCounter() 初始化计数器，请求数为 0 。int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证每次对 ping 的调用都使用比之前更大的 t 值。
示例 1：
输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]
解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
提示：
1 <= t <= 10^9- 保证每次对
ping 调用所使用的 t 值都 严格递增
- 至多调用
ping 方法 10^4 次
分析说明
以下内容基于我漏看了 t 递增这一条件。由于 t 递增，因此往前距离大于 3000 的记录无须保留，从而简化了问题，可以使用队列直接做。今天打字很多了，不补充了。
基本分析
根据题意，题目涉及“单点修改”和“区间查询”，根据区间求和问题的总结，可以使用“树状数组”和“线段树”进行求解。
但是留意到 t 的数据范围为 10^9，虽然调用次数是 10^4，但由于本题是“强制在线”问题，因此我们无法利用“离散化”手段来解决 MLE 问题，而要使用“线段树（动态开点）”来解决。
线段树（动态开点）
动态开点的优势在于，不需要事前构造空树，而是在插入操作 update 和查询操作 query 时根据访问需要进行“开点”操作。由于我们不保证查询和插入都是连续的，因此对于父节点 u 而言，我们不能通过 u << 1 和 u << 1 | 1 的固定方式进行访问，而要将节点 u 的左右节点所在 tr 数组的下标进行存储，分别记为 ls 和 rs 属性。对于 ls 和 rs 则是代表子节点尚未被创建，当需要访问到它们，而又尚未创建的时候，则将其进行创建。
线段树的插入和查询都是 O(logn) 的，因此我们在单次操作的时候，最多会创建数量级为 O(logn) 的点，因此空间复杂度为 O(mlogn)，而不是 O(4n)。而开点数的预估需不能仅仅根据 O(mlogn) 来进行，还要对具体常数进行分析，才能得到准确的点数上界。
动态开点相比于原始的线段树实现，本质仍是使用“满二叉树”的形式进行存储，只不过是按需创建区间，如果我们是按照连续段进行查询或插入，最坏情况下仍然会占到 4n 的空间。因此我们可以估算点数为 4 * m * logn，其中 n 和 m 分别代表值域大小和查询次数。
当然一个比较实用的估点方式可以“尽可能的多开点数”，利用题目给定的空间上界和我们创建的自定义类（结构体）的大小，尽可能的多开（Java 的 128M 可以开到 7e6 以上）。
代码：
class RecentCounter {
class Node {
// ls 和 rs 分别代表当前节点（区间）的左右子节点在 tr 的下标
// val 代表在当前节点（区间）所包含的数的个数
int ls, rs, val;
}
int N = (int)1e9, M = 800010, idx = 1;
Node[] tr = new Node[M];
void update(int u, int lc, int rc, int x, int v) {
if (lc == x && rc == x) {
tr[u].val += (rc - lc + 1) * v;
return ;
}
lazyCreate(u);
int mid = lc + rc >> 1;
if (x <= mid) update(tr[u].ls, lc, mid, x, v);
else update(tr[u].rs, mid + 1, rc, x, v);
pushup(u);
}
int query(int u, int lc, int rc, int l, int r) {
if (l <= lc && rc <= r) return tr[u].val;
lazyCreate(u);
int mid = lc + rc >> 1, ans = 0;
if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
if (r > mid) ans += query(tr[u].rs, mid + 1, rc, l, r);
return ans;
}
void lazyCreate(int u) {
if (tr[u] == null) tr[u] = new Node();
if (tr[u].ls == 0) {
tr[u].ls = ++idx;
tr[tr[u].ls] = new Node();
}
if (tr[u].rs == 0) {
tr[u].rs = ++idx;
tr[tr[u].rs] = new Node();
}
}
void pushup(int u) {
tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
}
public int ping(int t) {
update(1, 1, N, t, 1);
return query(1, 1, N, Math.max(0, t - 3000), t);
}
}
- 时间复杂度：令
ping 的调用次数为 n，值域大小为 m，线段树的插入和查询复杂度均为 O(logm)
- 空间复杂度：
O(nlogm)
分块
另外一个值得考虑的算法是“分块”。
通常来说，值域范围为 n，我们可以定义块大小为 sqrt(n)，这样时空复杂度都是 O(n)。
回到本题，我们定义一个 region 数组，用于存储每个块所包含的数的个数。
对于在位置 x 插入一个值 v 而言，我们可以计算位置 x 所在的块编号 bid，然后对块大小进行累加操作（region[bid] += v）。同时由于在查询 [l, r] 时不总是覆盖完整的块，因此我们需要额外记录位置 x 当前所包含的总数是多少。本题值域大小达到了 10^9，因此不能使用静态数组来做，只能使用哈希表来实现动态记录。
我们可以分析单个 ping 操作的计算量/复杂度：
update 操作：O(1)；query 操作：不限制区域大小的话，计算量为 O(sqrt(n))，由于存在 3000 的限制，相当于这部分操作全部变成块内了，计算量固定为 O(sqrt(n))。
代码：
class RecentCounter {
static int m = 300, n = (int)(1e9 / m) + 10;
static Map<Integer, Integer> map = new HashMap<>();
static int[] region = new int[n];
int getIdx(int x) {
return x / m;
}
void update(int x, int v) {
map.put(x, map.getOrDefault(x, 0) + v);
region[getIdx(x)] += v;
}
int query(int l, int r) {
int ans = 0;
if (getIdx(l) == getIdx(r)) {
for (int k = l; k <= r; k++) ans += map.getOrDefault(k, 0);
} else {
int i = l, j = r;
while (getIdx(i) == getIdx(l)) ans += map.getOrDefault(i++, 0);
while (getIdx(j) == getIdx(r)) ans += map.getOrDefault(j--, 0);
for (int k = getIdx(i); k <= getIdx(j); k++) ans += region[k];
}
return ans;
}
public RecentCounter() {
map.clear();
Arrays.fill(region, 0);
}
public int ping(int t) {
update(t, 1);
return query(Math.max(0, t - 3000), t);
}
}
- 时间复杂度：通常情况下：调用次数为
n，值域大小为 m，复杂度为 O(sqrt(m))；本题：O(sqrt(3000))，其中 sqrt(3000) 为块大小
- 空间复杂度：通常情况下：
O(n + sqrt(m))；本题：O(sqrt(10^9))，其中 sqrt(10^9) 为分块数组大小
希望这份关于字节跳动校招的最新资讯，以及这道LeetCode题目的详细解析，能对正在准备面试和钻研Java等后端技术的你有所帮助。想了解更多大厂动态、技术干货和求职心得，欢迎来云栈社区一起交流成长。
发表于 3 天前
|
查看: 34|
回复: 0
