字节跳动也启动春季校园招聘了(含二面算法原题)
字节跳动 - 春招启动
随着各个大厂陆续打响春招的响头炮,字节跳动也官宣了春季校园招聘的正式开始。
还是那句话:连互联网大厂启动校招计划尚且争先恐后,你还有什么理由不马上行动?!
先来扫一眼「春招流程」和「面向群体」:
一般的大厂校招,只会放出「岗位类型(前端/后端/算法)」和「要求说明」,具体会分到什么部门 or 事业群,是后面的事,选择权往往不在候选人手上。
但字节则有所不同,会在校招岗位中直接指明这是哪个部门 or 事业群的实习岗位。
因此可投岗位会很丰富,好处是候选人会对岗位了解得比较清楚,并且不会出现大量候选人都涌入某个投递口的情况:
然后再看看和公主号相关性较高的岗位:
...
回归主线。
字节是众多国内互联网大厂中,以「算法面试」著称的大厂。
即使是字节社招中,仍然会有较大的算法占比。
今天给大家分享一道「字节跳动」二面算法原题。
题目描述
平台:LeetCode
题号:895
设计一个类似堆栈的数据结构,将元素推入堆栈,并从堆栈中弹出出现频率最高的元素。
实现 FreqStack 类:
-
FreqStack()构造一个空的堆栈。 -
void push(int val)将一个整数val压入栈顶。 -
int pop()删除并返回堆栈中出现频率最高的元素。
如果出现频率最高的元素不只一个,则移除并返回最接近栈顶的元素。
示例 1:
输入:
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出:[null,null,null,null,null,null,null,5,7,5,4]
解释:
FreqStack = new FreqStack();
freqStack.push (5);//堆栈为 [5]
freqStack.push (7);//堆栈是 [5,7]
freqStack.push (5);//堆栈是 [5,7,5]
freqStack.push (7);//堆栈是 [5,7,5,7]
freqStack.push (4);//堆栈是 [5,7,5,7,4]
freqStack.push (5);//堆栈是 [5,7,5,7,4,5]
freqStack.pop ();//返回 5 ,因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。
freqStack.pop ();//返回 7 ,因为 5 和 7 出现频率最高,但7最接近顶部。堆栈变成 [5,7,5,4]。
freqStack.pop ();//返回 5 ,因为 5 出现频率最高。堆栈变成 [5,7,4]。
freqStack.pop ();//返回 4 ,因为 4, 5 和 7 出现频率最高,但 4 是最接近顶部的。堆栈变成 [5,7]。
提示:
-
-
push和pop的操作数不大于 -
输入保证在调用 pop之前堆栈中至少有一个元素
哈希表
这是一道很纯的哈希表题儿。
首先,我们容易想到建立 「第一个哈希表 cnts 用于记录某个数值的出现次数,cnts[val] = c 含义为数值 val 当前在栈中的出现次数为 c。我们称该哈希表为「计数哈希表」」。
再结合每次 pop 需要返回「频率最大的元素,若有多个则返回最考虑栈顶的一个」的要求,我们还可以 「建立第二个哈希 map,该哈希表以「出现次数 c」为键,以「出现次数均为 c 的元素序列」为值,map[c] = A = [...] 含义为出现次数为 c 的序列为 A,并且序列 A 中的结尾元素为出现次数为 c 的所有元素中最靠近栈顶的元素。我们称该哈希表为「分桶哈希表」」。
最后再额外使用一个变量 max 记录当前最大出现频数,不难发现,max 必然是以步长 进行变化(当出现次数为 max 的元素被 pop 掉了一个后,必然剩下 max - 1 个),因此当我们在某次 pop 操作后发现出现次数为 max 的集合为空时,对 max 进行自减操作即可。
将题目给的样例作为 🌰 ,大家可以看看 cnts、map 和 max 三者如何变化,以及 pop 的更新逻辑:
Java 代码:
class FreqStack {
Map<Integer, List<Integer>> map = new HashMap<>();
Map<Integer, Integer> cnts = new HashMap<>();
int max;
public void push(int val) {
cnts.put(val, cnts.getOrDefault(val, 0) + 1);
int c = cnts.get(val);
List<Integer> list = map.getOrDefault(c, new ArrayList<>());
list.add(val);
map.put(c, list);
max = Math.max(max, c);
}
public int pop() {
List<Integer> list = map.get(max);
int ans = list.remove(list.size() - 1);
cnts.put(ans, cnts.get(ans) - 1);
if (list.size() == 0) max--;
return ans;
}
}
C++ 代码:
class FreqStack {
public:
unordered_map<int, int> freq;
unordered_map<int, vector<int>> m;
int maxv = 0;
void push(int val) {
maxv = max(maxv, ++freq[val]);
m[freq[val]].push_back(val);
}
int pop() {
int x = m[maxv].back();
m[maxv].pop_back();
if (m[freq[x]--].empty()) maxv--;
return x;
}
};
Python 代码:
class FreqStack:
def __init__(self):
self.cnts = defaultdict(int)
self.map = defaultdict(list)
self.mv = 0
def push(self, val: int) -> None:
self.cnts[val] += 1
c = self.cnts[val]
self.map[c].append(val)
self.mv = max(self.mv, c)
def pop(self) -> int:
ans = self.map[self.mv].pop()
self.cnts[ans] -= 1
self.mv -= 0 if self.map[self.mv] else 1
return ans
TypeScript 代码:
class FreqStack {
map: Map<number, Array<number>> = new Map<number, Array<number>>()
cnst: Map<number, number> = new Map<number, number>()
max: number = 0
push(val: number): void {
if (!this.cnst.has(val)) this.cnst.set(val, 0)
this.cnst.set(val, this.cnst.get(val) + 1)
const c = this.cnst.get(val)
if (!this.map.has(c)) this.map.set(c, new Array<number>())
this.map.get(c).push(val)
this.max = Math.max(this.max, c)
}
pop(): number {
const ans = this.map.get(this.max).pop()
if (this.map.get(this.max).length == 0) this.max--
this.cnst.set(ans, this.cnst.get(ans) - 1)
return ans
}
}
-
时间复杂度:所有操作均为 -
空间复杂度:所有入栈的节点最多会被存储两次,一次在计数哈希表中,一次在分桶哈希表中,复杂度为
我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。
欢迎关注,明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
相关文章:
字节跳动也启动春季校园招聘了(含二面算法原题)
字节跳动 - 春招启动 随着各个大厂陆续打响春招的响头炮,字节跳动也官宣了春季校园招聘的正式开始。 还是那句话:连互联网大厂启动校招计划尚且争先恐后,你还有什么理由不马上行动?! 先来扫一眼「春招流程」和「面向群…...
二,几何相交---4,BO算法---(3)数据结构
数据结构分两块,一个是某一时间状态的局部相交线段。一个是事件队列,是某一时刻局部相交线段的集合。...
中间件MQ面试题之Kafka
MQ相关面试题 Kafka面试题 (1)rockermq和kafka 的区别在哪里? 使用场景有什么不一样? 不同点: 数据可靠性 不同: RocketMQ:支持异步实时刷盘、同步刷盘、同步复制、异步复制;kafka:使用异步刷盘方式,异步复制/同步复制。性能对比:kafka单机写入TPS比较高单机支持…...
Prometheus 安装部署
文章目录 1.部署Prometheus1.1.修改配置文件1.2.配置告警规则1.3.运行Docker 2.部署Alertmanager2.1.修改配置文件2.2.Prometheus监控配置2.3.运行Docker 3.部署Grafana3.1.运行Docker3.2. 配置数据源3.3. 配置dashboard 开源中间件 # Prometheushttps://iothub.org.cn/docs/m…...
龙芯杯赛道-学习过程记录
Preface&免责声明: 由于参赛资料企业并未开源,所以我不能开放出有关参赛的资料 但是我会在这里记录参赛时看不懂的一系列知识补充 ------------------------------------------------------------------------------------------------------- TSEN…...
76. 最小覆盖子串-力扣hot100(C++)
76. 最小覆盖子串s 初始化和特判 //本题做题思想 //从头开始,首先找到一个包含所有字母的字串,将i移动到包含字串字母的位置,然后更新长度和字符串ans后, //i的位置加1,j的位置也加1,从新开始上面的流程&…...
vue的生命周期有那些
1.v-text 相当于js的innerText <div v-text"姓名:name"></div>const name ref(张三); //声明 2.v-html 相当于js的innerHTML <div v-html"html"></div>const html ref(<s>这是一段文字</s>) 3.v-bin…...
OpenStack安装步骤
一、准备OpenStack安装环境 1、创建实验用的虚拟机实例。 内存建议16GB(8GB也能运行)CPU(处理器)双核且支持虚拟化硬盘容量不低于200GB(!)网络用net桥接模式 运行虚拟机 2、禁用防火墙与SELin…...
如何借助CRM系统获得直观的业务洞察?CRM系统图表视图解析!
Zoho CRM管理系统在优化客户体验方面持续发力,新年新UI,一波新功能正在赶来的路上。今天要介绍的新UI功能在正式推出之前,已经通过早鸟申请的方式给部分国际版用户尝过鲜了。Zoho CRM即将推出图表视图,将原始数据转换为直观的图表…...
制作图片马:二次渲染(upload-labs第17关)
代码分析 $im imagecreatefromjpeg($target_path);在本关的代码中这个imagecreatefromjpeg();函数起到了将上传的图片打乱并重新组合。这就意味着在制作图片马的时候要将木马插入到图片没有被改变的部分。 gif gif图的特点是无损,我们可以对比上传前后图片的内容…...
XGB-20:XGBoost中不同参数的预测函数
有许多在XGBoost中具有不同参数的预测函数。 预测选项 xgboost.Booster.predict() 方法有许多不同的预测选项,从 pred_contribs 到 pred_leaf 不等。输出形状取决于预测的类型。对于多类分类问题,XGBoost为每个类构建一棵树,每个类的树称为…...
websocket 使用示例
websocket 使用示例 前言html中使用vue3中使用1、安装websocket依赖2、代码 vue2中使用1、安装websocket依赖2、代码 前言 即时通讯webSocket 的使用 html中使用 以下是一个简单的 HTML 页面示例,它连接到 WebSocket 服务器并包含一个文本框、一个发送按钮以及 …...
基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的水下目标检测系统(深度学习模型+UI界面+训练数据集)
摘要:本研究详述了一种采用深度学习技术的水下目标检测系统,该系统集成了最新的YOLOv8算法,并与YOLOv7、YOLOv6、YOLOv5等早期算法进行了性能评估对比。该系统能够在各种媒介——包括图像、视频文件、实时视频流及批量文件中——准确地识别水…...
中间件 Redis 服务集群的部署方案
前言 在互联网业务发展非常迅猛的早期,如果预算不是问题,强烈建议使用“增强单机硬件性能”的方式提升系统并发能力,因为这个阶段,公司的战略往往是发展业务抢时间,而“增强单机硬件性能”往往是最快的方法。 正是在这…...
生成哈夫曼树C卷(JavaPythonC++Node.jsC语言)
给定长度为n的无序的数字数组,每个数字代表二叉树的叶子节点的权值,数字数组的值均大于等于1。请完成一个函数,根据输入的数字数组,生成哈夫曼树,并将哈夫曼树按照中序遍历输出。 为了保证输出的二又树中序遍历结果统一,增加以下限制:二叉树节点中,左节点权值小于等于右…...
Java代码审计安全篇-SSRF(服务端请求伪造)漏洞
前言: 堕落了三个月,现在因为被找实习而困扰,着实自己能力不足,从今天开始 每天沉淀一点点 ,准备秋招 加油 注意: 本文章参考qax的网络安全java代码审计,记录自己的学习过程,还希望各…...
入门可解释机器学习和可解释性【内容分享和实战分析】
本篇文章为天池三月场读书会《可解释机器学习》的内容概述和项目实战分享,旨在为推广机器学习可解释性的应用提供一定帮助。 本次直播分享视频和实践代码以及PP获取地址:https://tianchi.aliyun.com/specials/promotion/activity/bookclub 目录 内容分…...
Promise其实也不难
难点图解:then()方法 ES6学习网站:ES6 入门教程 解决:回调地狱(回调函数中嵌套回调) 两个特点: (1)对象的状态不受外界影响。Promise对象代表一个异步操作&…...
吴恩达 x Open AI ChatGPT ——如何写出好的提示词视频核心笔记
核心知识点脑图如下: 1、第一讲:课程介绍 要点1: 上图展示了两种大型语言模型(LLMs)的对比:基础语言模型(Base LLM)和指令调整语言模型(Instruction Tuned LLM࿰…...
JVM从1%到99%【精选】-【初步认识】
目录 1.java虚拟机 2.JVM的位置 3.代码的执行流程 4.JVM的架构模型 5.JVM的生命周期 6.JVM的整体结构 1.java虚拟机 Java虚拟机是一台执行Java字节码的虚拟计算机,它拥有独立的运行机制,其运行的Java字节码也未必由Java语言编译而成。JVM平台的各种语言可以共享Java…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
echarts使用graphic强行给图增加一个边框(边框根据自己的图形大小设置)- 适用于无法使用dom的样式
pdf-lib https://blog.csdn.net/Shi_haoliu/article/details/148157624?spm1001.2014.3001.5501 为了完成在pdf中导出echarts图,如果边框加在dom上面,pdf-lib导出svg的时候并不会导出边框,所以只能在echarts图上面加边框 grid的边框是在图里…...
在Spring Boot中集成RabbitMQ的完整指南
前言 在现代微服务架构中,消息队列(Message Queue)是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件,支持多种消息协议,具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...
标注工具核心架构分析——主窗口的图像显示
🏗️ 标注工具核心架构分析 📋 系统概述 主要有两个核心类,采用经典的 Scene-View 架构模式: 🎯 核心类结构 1. AnnotationScene (QGraphicsScene子类) 主要负责标注场景的管理和交互 🔧 关键函数&…...
