布隆过滤器及其误判率推导
本文将首先介绍布隆过滤器 (Bloom Filter) 是如何工作的,然后我们将形式化推导布隆过滤器的误判率。布隆过滤器是一种使用多哈希的方式判断元素是否属于集合的数据结构,他的优势在于不需要存储任何键值,非常节约空间且高效。
面经 - 吉比特 引擎开发实习生 笔试 240425
时间线
流程概况
240425 笔试
应该都写出来了,个别问题存疑。
240527
拒绝了面试邀约,因为这段时间没什么时间。
笔试
Part1 选择题
回忆几道印象深刻的题,其余部分概括一下。
甲乙丙丁戊其中四人发言说 “XX 是我的 XX (亲戚) 的 XX (亲戚)”,请问谁未发言。(岳母和女婿是啥来着…)
有三个小组各 10 / 15 / 25 人,其中女生 3 / 7 / 5 人,问随机从其中一个组选两人,已知后选出的为男生,则先选出为女生的概率?
A. 13; B. 29; C. 2061; D. 2990;A.~\frac{1}{3};~~B.~\frac{2}{9};~~C.~\frac{20}{61};~~D.~\frac{29}{90};A. 31; B. 92; C. 6120; D. 9029; (完全不会,五次算出五个答案,没一个在选项里)
一副扑克 54 张,均分 3 副,一副 18 张。问大小王在同一人手中的概率是多少?(吉比特你超爱考概率啊!)
剩余一道读代码题:本质是数二进制 111。
两道时间复杂度分析,余下都是 ...
逐行解析 - 从汇编看 C 语言
前言
本章我们将通过几个示例,本文以 Linux 系统为例,深入 C 语言的汇编代码,这能帮助我们更好理解程序的工作原理,例如栈的工作机制。
本文需要 C 语言基本语法、GCC 编译、GDB 调试的前置芝士。
如何调试 C 语言汇编代码
不需要安装额外的工具,直接使用 GDB 进行汇编代码调试即可,当然通过配置你的 IDE 也可以进行更舒适的调试。
首先书写源文件,假设我们已经书写了 main.c 文件,然后按照下面的方法编译:
12gcc main.c -o main.s -S # 生成汇编代码gcc main.s -o main -g # 附加调试信息
我们只要不在源代码中添加调试信息,而只在汇编代码中添加调试信息,即可直接使用 GDB 调试汇编代码。
12gdb main# 正常添加断点和运行代码, 使用形如 p $eax 查看寄存器
一段简单的汇编代码
在这段代码中,我们不对代码如何工作作介绍,仅用于介绍 C 语言汇编代码的基本框架。在之后的代码中,我们将不再解释框架性质的代码。
源码解释
1234567#include <stdio.h>int ma ...
CMake 项目构建和代码测试
前言
CMake 是非常常见的 C++ 代码构建工具,在 C++ 项目构建中被广泛使用。
本文我们将以著名的 CMake 入门示例 Useful CMake Examples - Github 为例,进行 CMake 的使用汇总。
快速开始
链接示例
这个示例中包含 CMake 配置文件的基本结构,同时包含头文件、静态库、动态库的链接方式。
最后,我们还在这个示例中包含了安装的示例,尽管这并不常用。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667# 定义项目名和最小支持版本cmake_minimum_required(VERSION 3.5)project(hello_binary)############################################################# 配置###################################### ...
梳理事务中的锁
事务中的锁一直是数据库中非常重要的部分,其中 MySQL 的 InnoDB 就包含意向锁 / 记录锁 / 间隙锁等,本文将以此展开事务的背后锁是如何运作的。
C++ 正则表达式 regex 的使用
前言
正则表达式(regular expression / regex)是非常实用的工具,几乎在所有语言中,都包含对正则表达式的支持,它们的语法大同小异。今天我们来讲讲 C++ 中 regex 的使用。另外需要注意的是,正则表达式不是专属于 C++ 的,在本文中我们假设你已经熟悉正则表达式。
本文需要正则表达式的前置芝士。
快速开始
一个简单的匹配
在正则表达式中,表达式的匹配分为编译和匹配两个部分。在 regex 库中,必须首先编译模式串,然后和字符串匹配。需要注意的是,在 C++ 中,编译和匹配两个操作必须是分离的,而在一些其他语言中可能支持直接匹配的接口(例如 Python,初学者通常选择直接编译)。
因此在 C++ 中,使用正则表达式必须分为两个步骤:
构造 regex 对象,即前面提到的编译。
使用 regex_match / regex_search 匹配。或者使用其他方法匹配。
123456789101112131415161718192021222324252627#include <iostream>#include <regex>us ...
面经 - 字节 广告基架实习 一面挂 240223
时间线
流程概况
240221 牛客简历初筛
…挺快,几个小时后就收到了面试邀约。
240223 一面口头过
主要聊了 C++,写了两道题。最后出了点问题,但在最后改对了(还是太紧张了),但还是给我过了。差强人意吧。
240304 感谢信
一面口头过了,但估计还因为大二以及实习只有两个月,以及面试表现不算特别突出,最后正式挂了。
一面
面试过程
首先是相互介绍,面试官先介绍了它们部门的业务,然后我介绍了一下我的技能项。
问题
解答情况
(面试官自我介绍,我的自我介绍)
什么时候开始打 ACM?高中有没有代码基础?
balabala,如实回答。
LRU-K 是啥?我知道 LRU,你给我大概讲讲 LRU-K。(面试官读简历中…)
balabala,面试官应该是真不知道。
Copy-on-Write 又是什么东西?(面试官读简历中…)
balabala,面试官应该是真不知道。
(后面开始问 C++)
总结下 static 这个关键字。
函数中的 static,类中的 static,总之可以扩大生命周期。
追问: static 成员函数是否可以访问普 ...
面经 - 达坦科技 Python开发实习生 一面挂 240220
这是第一次面试,自我安慰为,面得不好是意料之中吧。
岗位背景
达坦科技,北京小公司,线上实习。找 Rust 分布式存储开发,应该是缺人,牛客私聊我有 Python 线上实习。
个人简历主 C++,也涉及一半 Python 内容。
面试过程
首先是本来以为面试官会要求打开屏幕共享,结果面试官全程不露脸,也不要求屏幕共享,我开了摄像头也没开。
整个流程非常快,当天 HR 微信联系。
下午和 HR 聊了分布式和 Rust,我说我都不懂,HR 提供了意见:MIT6.824、Rust 官方教程。总体感觉 HR 很友好(但个人并没有 Rust 发展计划,我只能嗯嗯嗯好好好)。
晚上 CTO 约面(下文称面试官),约了第二天下午。整个微信联系过程都很礼貌,面试过程也很礼貌,不过给我挂了,当然聊得过程中也感觉到会被挂了。
面试官只问了一个问题,CMU15445。和我聊整个项目的实现和中间拓展的问题,估计面试官对数据库还是比较拿手,它说他还有很多关于数据库的拓展问题,但我没办法继续回答下去。其中主要问题如下:
问题
解答情况
大概介绍简历上两个项目。
Python 项目是 Python ...
从引用折叠到 move 与 forward 代码复现
前言
C++ 中的引用折叠十分晦涩难懂,而 move 与 forward 正是基于引用折叠,且难以理解。本文将从引用折叠讲起,理解为什么需要引用折叠、什么是引用折叠、引用折叠在模板中的作用,最后复现 move 与 forward。
本文需要右值引用、移动语义、模板的前置芝士。
引用折叠
什么是引用折叠
为什么需要引用折叠引用折叠用于保障一些 C++ 功能的正常工作,而它正是 std::move 的基础。事实上,我们之前学习的所有右值引用和移动语义的相关芝士,都需要通过 std::move 的协助。如果没有引用折叠,则 std::move 将无法实现,那么所有的右值引用都没有意义,引用折叠可以看作是编译器最初为实现右值引用做出的妥协。
在正常编程中,我们实际上极少接触引用折叠,因为它几乎仅仅被 std::move 与 std::forward 应用。不过在模板编程中,引用折叠又被赋予了其新的意义 。当然,如果你并不熟悉引用折叠,这些意义可能意味着新的 “坑”。
引用折叠是多次定义引用后的类型推导方式。但引用折叠禁止被显示定义,它事实上只在 using 或模板场景中才会出现,例如下 ...
一文理解类的访问权限
在类的继承体系中,关于访问权限我个人感觉一直是非常复杂,各类博客、书籍对它的解释都不够好。在这篇文章我想通过我的理解,着重解释类的继承体系中复杂的访问权限的原理。