Skip to content

Latest commit

 

History

History
614 lines (378 loc) · 26 KB

Bytedance.md

File metadata and controls

614 lines (378 loc) · 26 KB

字节跳动

广告部门

2020.11.20 一面，后端主要C++，少量Python/Golang

C++

// 首先应该明白指针就是地址 
// p是一个常量指针【指向常量的指针】，指向的内容不可以变化，但是可以通过改变地址让它指向另一个常量
const int *p; 或者是 int const *p;

// p是一个指针常量【指针本身是常量】，指向内部存储的内存地址是常量，不可以改变，但是内存地址所对应的内容是可以变化的
int *const p; // 引用的本质是指针常量

void func(const int var);	// 传递过来的参数在函数内不可以改变(无意义，该函数以传值的方式调用)
void func(const char* var);	// 参数指针所指内容为常量不可变
void func(char* const var);	// 参数指针本身为常量不可变(也无意义，var本身也是通过传值的形式赋值的)
void func(const class& var);// 引用参数在函数内不可以改变
// 修改construction修饰的变量
// https://blog.csdn.net/weixin_41413441/article/details/80860135
const volatile int i = 10；

// https://www.cnblogs.com/gylhaut/p/5502583.html
# include <iostream>
using namespace std;
class TestMutable {
    mutable int i;
public:
    TestMutable() { i=0;}
    int Output() const {
        return i++; 
    }
};

  • static 关键字使用场景 参考

    • 限制符号的作用域只在本程序文件

    • C++类的静态成员变量和函数：静态成员函数中没有this指针，只能调用静态成员变量

    • 指定变量的存储位置: 全局的和函数内定义的static变量都是存放在数据区的，且只存一份，只在整个程序结束后才自动释放，其他变量都是存储在栈，函数结束之后就释放

  • ++i 和 i++ 区别，哪个更快，为什么

    • i++ 不能作为左值，而 ++i 可以。

    • a++是先用临时对象保存原来的对象，然后对原对象自增，再返回临时对象，不能作为左值；++a是直接对于原对象进行自增，然后返回原对象的引用，可以作为左值。

    • 由于要生成临时对象，a++需要调用两次拷贝构造函数与析构函数（将原对象赋给临时对象一次，临时对象以值传递方式返回一次）；++a由于不用生成临时变量，且以引用方式返回，故没有构造与析构的开销，效率更高。

int i = 0;
int *p1 = &(++i); //正确
int *p2 = &(i++); //错误

++i = 1; //正确
i++ = 5; //错误

cout << ++(++(++i)) << endl;
cout << ++ ++i << endl;

左值是对应内存中有确定存储地址的对象的表达式的值，而右值是所有不是左值的表达式的值

左值与右值的根本区别在于是否允许取地址&运算符获得对应的内存地址

http://haoqchen.site/2018/10/15/difference-between-++i-i++-i+=1-i=i+1/

计网和OS

  • 请求一个网页具体过程

    本地DNS服务器之前是查找浏览器、操作系统和路由器的DNS缓存，参考一次完整的HTTP请求过程图

  • 进程通信方式

  • 进程和线程区别

  • linux 中 vi 模式的查找命令

    正则式：命令模式下输入“/字符串”，例如“/mysqld”；如果查找下一个，按“n”即可

  • LCR 022. 环形链表 II

  • [算法] [1, 3, 1, 6] 四个数字全部都用，使用加减乘除运算怎么得到24

    3 * 8 和 4 * 6

火山引擎

2021.4.23 一面

操作系统

  • 进程调度的几个方法，说一下多级反馈队列调度

  • 死锁的条件：①互斥；②非抢占资源分配；③持有和等待；④循环等待

  • 进程和线程的区别

  • 虚拟内存了解吗，段页式了解吗

  1. 存储分配方式总体分为：连续内存分配和离散内存分配

  2. 离散分配原因：由于连续分配方式会形成许多内存碎片，虽可通过“紧凑”功能将碎片合并，但会付出很大开销。于是出现离散分配方式：将一个进程直接分散地装入到许多不相邻的内存分区中。

  3. 离散分配分为：页式、段式、段页式

    1. 页式：大小固定，存在地址覆盖的问题，将地址空间划分成固定大小的页，每一页再与内存进行映射。
    2. 段式：大小不固定，每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。
    3. 段页式：程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

  4. 分页与分段的比较

    • 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
    • 地址空间的维度：分页是一维地址空间，分段是二维的。
    • 大小是否可以改变：页的大小不可变，x段的大小可以动态改变。
    • 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

计算机网络

  • 网页请求过程，三次握手和四次挥手

    挥手过程FIN字段是客户端先发一次然后服务器那边再发送一次，CLOSE_WAIT 阶段，**TIME_WAIT **阶段

  • get 和 post 携带的 body 区别 参考

    POST携带body参数一般有四种

    • application/x-www-form-urlencoded：浏览器的原生form表单，发送之前编码所有字符
    • multipart/form-data：使用表单上传文件时，必须让 表单的 Content-Type 等于 multipart/form-data，不对字符编码
    • application/json：现在用的比较多的一种JSON字符串，支持格式化数据
    • text/xml：用于传输xml个数的数据，比JSON格式复杂臃肿，一般用于配置文件

  • 客户端请求的HTTP字段格式

    • 请求行：包括请求方法、URL字段、HTTP协议版本三个字段

    • 请求头部：由关键字-值对组成

    • 空行：发送回车符和换行符，通知服务器以下不再有请求头

    • 请求数据：请求数据不在GET方法中使用，而是在POST方法中使用。POST方法适用于需要客户填写表单的场合。与请求数据相关的最常使用的请求头是Content-Type和Content-Length。

  • HTTP响应报文 参考

    • 第一行包含协议版本、状态码以及描述，最常见的是 200 OK 表示请求成功了

    • 接下来多行也是首部内容

    • 一个空行分隔首部和内容主体

    • 最后是响应的内容主体

数据库

  • 索引种类，底层实现是什么

  • B+树的各种操作：插入（什么时候分裂），删除（什么时候合并），查找（目前看到的阶数一般是3）

    1. 插入：全部在叶子节点上进行，不能破坏关键字的顺序，如果插入之后节点中关键字个数超过3个就需要进行分裂，具体规则可以看知乎
    2. 删除：需要考虑合并过程
    3. 查找

  • 行锁和表锁了解吗

    1. 行锁通过索引加载，即是行锁是加在索引响应的行上的，要是对应的SQL语句没有走索引，则会全表扫描，行锁则无法实现，取而代之的是表锁
    2. 表锁不会出现死锁，锁冲突的几率高，但是并发低；行锁会出现死锁，锁冲突的几率低，并发高
    3. 行锁分为：共享锁和排它锁，排它锁上锁之后允许其他事物读？

2、[算法] 33. 搜索旋转排序数组 81. 搜索旋转排序数组 II

搜索部门

2021.4.30

  • OSI七层模型、每层相关技术

    • 应用层：程序以及接口，文件传输、电子邮件、文件服务、虚拟终端，HTTP、DNS、FTP、SMTP

    • 表示层：对数据进行转换、加密和压缩，没有协议

    • 会话层：建立、管理和终止会话，没有协议

    • 传输层：提供可靠的端到端的报文传输和差错控制，TCP、UDP

    • 网络层： 将分组从源端传送到目的端，为数据包选择路由IP，ICMP、RIP、OSPF、BGP、IGMP

    • 数据链路层：将分组数据封装成帧；提供节点到节点方式的传输，传输有地址的帧以及错误检测功能，PPP、ARP、RARP、MTU

    • 物理层：以二进制数据形式在物理媒体上传输数据，物理层：中继器、集线器

  • TCP/IP协议

    • 应用层

    • 传输层：四层交换机

    • 网络层：路由器

    • 数据链路层：网桥、以太网交换机、网卡（其实一半工作在物理层一半工作在数据链路层）

  • TCP 和 OSI 区别：参考1、参考2、参考3

    • TCP/IP支持跨层封装；OSI不支持

    • TCP/IP仅仅支持IP网络协议；OSI支持多种网络层协议（IP IPX APPLE TALK NOVELL NSAP）

  • 数据库隔离级别：未提交读、提交读、可重复读、可串行化

  • [算法] 有环链表

飞书PC客户端

一面

2023.10.24—17:00-18:00 办公套件，终于被捞😭，久违的面试

  • 上来直接介绍 muduo 网络库，具体细节

  • 替换的 boost 什么依赖，any？bind？

  • epoll_wait 等待占用 CPU 吗，分几种情况？

    当进程被"阻塞/挂起"时，是不会占用 CPU 资源的

    参考：https://www.infoq.cn/article/26LPJzSp9EChwgNIc7Lq

  • 线程/进程常见三个状态以及转换关系：就绪、运行、阻塞 参考

  • 线程池线程使用完了怎么办，1个 main Reactor 接受 IO 连接，3 个 sub Reactor 已经在处理 3 个相关业务了，此时如果再来一个连接如何处理？

    还是会 dispatch 给 3 个 subReactor 中的一个，相当于现在一个 EventLoop 处理两个连接中的读写业务

  • 其中有哪些线程同步操作，条件变量、信号量同步哪个效率高一些

    • 互斥锁（Mutex）：使用互斥锁可以确保在同一时间只有一个线程可以访问被保护的共享资源。线程在访问共享资源之前需要先获取互斥锁，访问完成后再释放互斥锁，以确保互斥访问

    • 条件变量（Condition Variable）：条件变量用于线程之间的等待和通知机制。一个线程可以等待某个条件满足，而另一个线程可以在满足条件时通知等待的线程继续执行

    • 信号量（Semaphore）：信号量是一种计数器，用于控制多个线程对共享资源的访问。它可以限制同时访问的线程数量，通过增加或减少信号量的计数来控制访问权限。

    • 原子操作（Atomic Operations）：原子操作是一种无需使用锁的同步机制。它们提供了一种保证某些操作是原子性的方式，即不会被其他线程中断。常见的原子操作包括原子加载、存储、比较和交换等

    • 读写锁（Read-Write Lock）：读写锁允许多个线程同时读取共享资源，但只允许一个线程进行写操作。这样可以提高读操作的并发性能

    哪种同步方式效率更高取决于具体的使用场景和需求。不同的同步方式适用于不同的情况，并且其性能也会受到多种因素的影响，如线程数量、竞争程度、共享资源的访问模式等。

    **一般来说，原子操作的效率较高，因为它们通常不需要使用锁来保护共享资源，而是利用底层硬件提供的原子指令来实现同步。**因此，在并发度较高、对共享资源的访问较为简单的场景下，原子操作可能是较为高效的选择。

    另外，读写锁在读多写少的情况下可以提供更好的性能，因为它允许多个线程同时读取共享资源，从而提高了读操作的并发性能。

    然而，对于具体的应用场景，最好的方式是进行实际的性能测试和评估，以确定最适合的同步方式。此外，还应考虑代码的可维护性、易用性和可扩展性等因素，并根据实际需求进行权衡和选择。

  • C++ 常见容器以及对应的使用场景：序列式容器、关联式容器、无序容器、容器适配器

  • sort 函数可以排序那些容器

    • 关联式容器无需 sort，自然有序
    • 序列式容器 list 有 sort 成员函数，不能直接调用 sort，因为算法库的 sort 要求 random access Iterator，其他的序列式容器 array、vector 和 deque 不具有 sort 成员函数，可以调用 sort 算法库

  • 右值引用用途：主要用于避免深拷贝，效率更高，move 原理

  • 智能指针相关，weak_ptr 线程安全吗？

  • 算法：返回链表倒数第 k 个节点

二面

2023.10.27—16:00-17:40

  • shared_ptr 和 weak_ptr 底层实现，lock() 是如何做到线程安全的

    weak_ptr.lock()通过CAS（Compare and Swap）操作实现自旋锁，可以实现原子操作。CAS是一种原子操作，它允许线程比较内存位置的当前值和期望值，如果相等，则修改内存位置为新值。这是一种常见的原子操作，通常由底层硬件提供支持。CAS 操作的一般流程如下：

    1. 读取内存位置的当前值，比较当前值与期望值；
    2. 如果相等，将新值写入内存位置；
    3. 否则，放弃操作，因为内存位置的值已经发生了变化；

  • 原子类型了解吗，底层是如何实现原子变量的 ++ 和 -- 操作的

    通过底层的硬件和编译器支持来实现的，通常使用特定的CPU指令来保证操作的原子性。不同编译器或者不同平台的具体实现可能不同：

    • CPU 指令：许多现代CPU都支持原子操作的硬件指令，如原子增加和原子减少。编译器可以将 ++ 和 -- 操作映射到这些指令上，以确保操作的原子性。这些硬件指令会锁定内存位置，使其他线程无法在同一时间修改它。
    • CAS（Compare-and-Swap）操作：某些平台不支持硬件原子操作指令，但编译器可以使用CAS操作来实现原子性。CAS是一种基本的并发原子操作，它允许线程比较内存位置的当前值和期望值，如果相等，则修改内存位置为新值。CAS操作通常需要循环，直到成功为止，以确保操作的原子性。
    • 使用互斥锁：在一些不支持硬件原子操作或CAS操作的平台上，编译器可能使用互斥锁来实现原子操作。这会带来一些性能开销，因为它需要线程之间的同步，但可以确保操作的原子性。

  • 单例模式的线程安全问题，锁+双重检测可以提高效率

  • 不同平台的 IO 复用 API 了解多少

    1. POSIX select() 和 poll()：

      Linux/Unix/macOS：select() 和 poll() 在这些平台上是通用的I/O复用接口，并且名称相同。它们使用文件描述符集合来监视多个文件描述符的状态，并在有数据准备好时通知应用程序。

    2. POSIX epoll()：

      Linux：epoll 是Linux特有的I/O复用接口，相对于 select 和 poll，它通常更加高效，特别是在大量并发连接的情况下。它使用事件驱动的机制，应用程序可以等待文件描述符上的特定事件，而不是在所有文件描述符上等待变化。

    3. POSIX kqueue()：

      FreeBSD/macOS：kqueue 是BSD衍生系统上的I/O复用接口，类似于epoll。它也使用事件通知机制，允许应用程序监视大量文件描述符上的事件。

    4. Windows IOCP（I/O Completion Ports）：

      Windows：Windows上的I/O复用接口是IOCP，它使用事件驱动的模型，并允许应用程序异步地处理I/O操作。IOCP通常被认为在处理大规模并发连接时非常高效。

  • lambda 表达式了解吗，可以转化成函数指针吗

    可以，参考：https://blog.csdn.net/weixin_42695485/article/details/130810561

  • 动态库和静态库了解吗，分别使用两个库编译得到可执行文件，输入「复杂参数」运行有问题吗

    • 静态库编译得到的可执行文件没问题
    • 动态库编译得到可执行文件可能存在问题，动态库函数实现中的类型可能和「复杂参数」不一致，另外也可能由于编译动态库的系统不同导致运行出错

  • muduo 网络库作者是谁，有读过陈硕其他文章吗，C++ 读过哪些书籍

三面

2023.11.1 — 18:00-19:00

  • STL 容器有哪些

  • vector 和 list 区别

  • 存放 10w 条数据选择哪个容器更好一些，如何查找更加高效

  • 如果有序，list 可以二分吗

    链表不能二分，upper_bound 查找 list 就是 O(n) 复杂度

  • 智能指针，手撕 unique_ptr

    template<typename T>
class uniquePtr {
private:
    T* _ptr;	// 原始指针
    
public:
    // 默认构造函数
    uniquePtr(T* ptr = nullptr): _ptr(ptr) {}
    
    uniquePtr(const uniquePtr&) = delete;
    uniquePtr<T>& operator=(const uniquePtr&) = delete;

    uniquePtr(uniquePtr && other) {
        // 注意这里没有 delete _ptr, 一般移动构造就是初始构造时调用，_ptr 并没有指向一个地址
        _ptr = other._ptr;
        other._ptr = nullptr;
    }

    uniquePtr<T>& operator=(uniquePtr&& other) {
        if (this != &other) {
            delete _ptr; // 先释放现有空间，主要理解指针的含义，其实就是一地址！
            _ptr = other._ptr;
            other._ptr = nullptr;
        }
        return *this;
    }
    
    T* get() const {
        return ptr;
    }
    
    T* operator->() const {
        return _ptr;
    }
    
    T& operator*() const {
        return *_ptr;
    }
    
    ~uniquePtr() {
        delete _ptr;
        _ptr = nullptr;
    }
};

  • 类的空间布局

    class A { // sizeof(A) = 16
    int a;
    virtual void funA() {}
};

class B : public A { // sizeof(B) = 16
    virtual void funA() {}
    virtual void funB() {}
};

  • 项目遇到那些比较棘手的问题，如何防止内存泄漏

财经部门

一面

2023.11.16 — 15:00-16:00

  • 实习项目具体介绍、nginx 限速如何实现的，了解令牌桶吗

    1. 发送速率控制： 当 Nginx 处理客户端请求时，limit_rate 指令控制响应的发送速率。这个速率限制是每秒的速率，表示 Nginx 每秒最多发送的字节数。
    2. Token Bucket 算法： 限速的实现基于令牌桶（Token Bucket）算法。令牌桶是一个用于存储令牌的容器，每个令牌代表一个可发送的数据单元。令牌以恒定的速率被添加到令牌桶中。
    3. 发送数据检查： 当 Nginx 准备发送数据给客户端时，它会检查令牌桶中是否有足够的令牌。如果有足够的令牌，就发送相应的数据，并从令牌桶中减去相应数量的令牌。如果令牌不足，Nginx 可能等待，直到令牌积累到足够的数量。
    4. 速率限制应用范围： limit_rate 可以在全局、server、location 等不同的配置块级别使用。这样，你可以根据需要在不同的地方应用不同的限速策略。

  • IO 复用底层如何实现

  • mmap 用在哪些场景

    1. 文件映射： mmap 允许将整个文件或部分文件映射到内存中。这样，应用程序可以直接访问文件的内容，而不需要使用传统的读取和写入文件的方法。
    2. 共享内存： 多个进程可以将同一个文件映射到它们的地址空间，实现进程间的共享内存。这种方法比使用进程间通信（IPC）机制更为高效。
    3. 内存映射 I/O： mmap 允许你将文件的一部分或整个文件映射到内存，使得文件的 I/O 操作变得更加高效。当需要处理大文件时，内存映射 I/O 可以减少读取和写入的次数，提高性能。
    4. 零拷贝： 内存映射文件可以用于实现零拷贝（zero-copy）技术。在某些情况下，可以直接在用户空间和磁盘之间进行数据传输，而不需要将数据在内核空间和用户空间之间进行复制。

  • Linux 服务器很卡有哪些方面的原因

    • CPU 使用率高：top 查看占用情况，ps aux 查看具体进程信息
    • 内存不足：free -m 查看内存使用情况，top 定位具体进程，是否内存泄漏
    • 磁盘IO瓶颈：iostat -d 1 检查磁盘IO情况，检查是否大量的读写操作
    • 网络问题：nload 查看网络使用情况，确认是否有异常网络流量
    • 进程数量过多
    • 服务异常崩溃
    • 系统负载或者系统需要升序优化

  • 10亿条数据存储在100个文件中，每个文件1000万条数据，每条数据包括 userId 以及 hotkeys，如何找到 hotkeys 最高的 10000 条数据

    小根堆，多线程可以加速吗，可以不加锁吗

  • 148. 排序链表

花呗、借呗和保险业务

二面

2023.11.16 — 14:30-15:30

  • 网络IO分类

  • 分布式系统设计需要考虑哪些要点，如果 zk 崩了对服务器集群有哪些影响

    考虑点：CAP原理、数据分片与复制、负载均衡、故障处理与容错、事务处理、

    影响：

    • 服务注册和发现中断： 如果服务端使用ZooKeeper进行服务注册和发现，ZooKeeper的崩溃可能导致服务端无法正确地注册自身或发现其他服务。新的服务实例可能无法加入到服务注册表中，而已注册的服务实例也可能无法被发现
    • 配置管理中断： 如果服务端使用ZooKeeper来进行配置管理，例如动态配置更新，ZooKeeper的崩溃可能导致服务端无法获取或更新配置信息。这可能影响到服务的行为和性能
    • 领导者选举问题：如果服务端参与了分布式系统中的领导者选择，例如分布式锁的管理，ZooKeeper的崩溃可能导致选举过程中的问题。这可能影响到服务端在分布式环境中的一致性操作
    • 容错性问题： 如果服务端依赖ZooKeeper来实现容错机制，例如检测其他服务实例的健康状态，ZooKeeper的崩溃可能导致服务端无法有效地进行容错

  • 你理解的网络层和传输层的区别

  • 手写一个单例模式，有哪些使用场景

    配置文件管理器、日志记录器、数据连接池、线程池、缓存管理器、计数器

  • 项目中有哪些场景不能使用单例模式

  • 排序算法有哪些，不稳定有哪些

    选择排序、快速排序和堆排序

  • 场景题目：1到1亿的数据各不相同，随机选择100000个数据，如何在O(n) 时间如何排序，空间复杂度如何优化

    void countingSort(std::vector<int>& arr) // 计数排序
{
    // 找出数据的范围（最大值和最小值）
    int maxVal = arr[0], minVal = arr[0];
    for (int num : arr) {
        maxVal = std::max(maxVal, num);
        minVal = std::min(minVal, num);
    }

    // 计算每个元素出现的次数
    std::vector<int> count(maxVal - minVal + 1, 0);
    for (int num : arr) {
        count[num - minVal] ++;
    }

    // 根据统计信息重新排列数据
    int index = 0;
    for (int i = 0; i < count.size(); ++i) {
        while (count[i] > 0) {
            arr[index++] = i + minVal;
            count[i]--;
        }
    }
}

  • sql 题：stu_id、class_id、score 中计算每个班级的平均分以及找出每个班级最高分的学生

  • 算法题：LCR 194. 二叉树的最近公共祖先

三面

2023.11.21 11:00-12:00

困难题，主管很傲慢的感觉...3面寄

视频中台云游戏

一面

2023.12.22 16:00-16:40

  • 为什么选择 DASH
  • HLS 和 DASH 的索引文件区别
  • UDP 了解多少，RTP 用在哪些场景
  • extern、静态链接和动态链接
  • 层序遍历输出结果

二面

2023.12.26 20:00-20:20

  • 实习项目
  • muduo 网络库线程数量为1

感觉很水，20min结束

三面

2023.12.28 14:00 - 14:40

  • 实习项目，QoE 设计
  • muduo 网络架构，如何处理高并发
  • IO 复用、IO 分类
  • [算法] 20. 有效的括号

感觉没啥难度...

抖音-C++客户端

一面

2024.03.21 19:00-20:00

  • C struct 和 C++ struct 区别

  • C 语言如何实现面向对象

    1. 封装：struct
    2. 继承：内含 struct
    3. 多态：函数指针

  • 形参和实参的区别、传指针和传引用

  • HTTPS 建立连接过程、TCP 如何保证可靠性

  • 线程同步方式

  • 算法：判断子树（两次 DFS）、日程表安排（差分数组）