Skip to content

Latest commit

 

History

History
365 lines (202 loc) · 15.7 KB

Baidu.md

File metadata and controls

365 lines (202 loc) · 15.7 KB

百度

0313笔试

T2 构造字符串 [mid]

输入一个整数 n（1 <= n <= 1e9），输出一个字符串 s（任意符合要求的都可）

  • 要求1：s 的字符只能从 {'r', 'e', 'd'} 中选择

  • 要求2：s 的回文子串个数为 n

# 样例
输入：n = 3
输出：s = "rr"（"red"也可以）

输入：n = 4
输出：s = "rre"（"rrd"也可以）

贪心构造：(rrr...)(eee...)(ddd...)(rrr...)(eee...)(ddd...)...这样构造，长度从长到短

代码参考：baidu_0313_2.cpp

T3 树上同色连通块 [hard]

题目内容 : 每个节点被染成了红色或者蓝色。小红定义每条边的权值为：删除这条边时，形成的两个子树的同色连通块数量之差的绝对值。小红想知道，所有边的权值之和是多少？

输入描述 : 第一行输入一个正整数 n，代表节点的数量；第二行输入一个长度为 n 且仅由 R 和 B 种字符组成的字符串；第 i 个字符为 R 代表 i 号节点被染成红色，为 B 则被染成蓝色。接下来的 n−1 行，每行输入两个正整数 u 和 v ，代表节点 u 和节点 v 有一条边相连。1 <= n <= 200000

输出描述 : 一个正整数，代表所有节点的权值之和。

# 样例
# 输入：
4
BBRR
1 2
3 2
4 1
# 输出：
2

思路： dp[i] 表示以 i 为根的子树中同色联通块的个数。如果从 1 号节点开始枚举，最后 dp[1] 得到就是整棵树的同色连通块个数，考虑转移方程：

计算 dp[n]

base case：节点 i 只有一个子结点 j，$dp[i]=dp[j] + (color[i] \neq color[j])$

两种情况：① i 和 j 颜色不同，连通块个数 +1；② i 和 j 颜色相同，连通块个数不变

假设 节点 i 有多个子节点 j，考虑子节点一个一个拼接在节点 i 上，这个过程分阶段进行，反复进行 base case 的转换就可以，得到 $dp[i]=\Sigma dp[j] + (color[i] \neq color[j])$

计算权值 ans

枚举每条边 u --> v，断开之后原图分成两个部分，子树部分显然是 dp[v]，而子树的子集就是整体的同色连通块个数 dp[1] - dp[v]，但是需要注意如果两个节点颜色相同，补集同色连通块个数需要 +1，这个过程也可以 dfs 实现

代码参考：baidu_0313_3.cpp

搜索架构

2021.4.26 一面

C++

1、C++文本文件到可执行文件的过程：预编译，编译，汇编，链接
  • 参考：hello.c 程序的编译过程
2、C++的多态了解吗
3、map 和 set 的区别，set中插入相同的值会发生什么
4、红黑树了解吗，二叉树？
  • 出现原因：二叉搜索数最极端的情况是退化成链表，查找效率变低，平衡二叉树其实也可以解决效率低的问题，但是他要求每个节点的左右子树的高度差不大于1，因此在大量数据插入或者删除时需要经常调整，效率也不高。
  • 性质：
    • 节点只有黑色和红色
    • 根节点是黑色
    • 每个叶子节点是黑色
    • 每个红色节点的两个子节点一定是黑色，不能有两个红色节点相连
    • 任意一个节点到每个叶子节点的路径都包含数量相同的黑节点，黑高
  • 查找：和搜索二叉树相同
  • 插入：插入节点必须是红色
5、new、delete 以及 malloc、free 区别

  • 相同点：都可以用于内存的动态申请和释放

  • 不同点：

    • new/delete是C++运算符，支持重载，不需要库文件；malloc/free是C/C++语言标准库函数，支持覆盖，需要库文件

    • new自动计算要分配的空间大小，malloc需要手工计算

    • new是类型安全的，malloc不是

      int *p = new float[2]; //编译错误 
int *p = (int*)malloc(2 * sizeof(double));//编译无错误

    • new封装了malloc，直接free不会报错，但是只是释放内存，而不会析构对象

    • new调用名为operator new的标准库函数分配足够空间并调用相关对象的构造函数，delete对指针所指对象运行适当的析构函数；然后通过调用名为operator delete的标准库函数释放该对象所用内存。后者均没有相关调用

    • malloc仅仅分配内存空间，free仅仅回收空间，不具备调用构造函数和析构函数功能，用malloc分配空间存储类的对象存在风险；new和delete除了分配回收功能外，还会调用构造函数和析构函数。

    • malloc和free返回的是void类型指针（必须进行类型转换），new和delete返回的是具体类型指针。

  • delete和delete[]区别？

    • delete只会调用一次析构函数。 delete[]会调用数组中每个元素的析构函数。
6、为什么需要分虚函数和纯虚函数
  1. 虚函数和纯虚函数都可以在子类中被重写，前者既有定义也有实现代码，后者一般没有实现的代码
  2. 含有纯虚函数的类不能实例化，也就是只能被继承到子类中去实现，含有此函数的类被称为抽象类。另外虚函数在子类中可以不重载，但是纯虚函数必须重载
  3. 含有纯虚函数的类一般用于定义一些公有的方法
7、智能指针了解吗
  1. 原理：是一个类，存储指向动态分配对象的指针，负责自动释放动态分配的对象，防止堆内存泄漏。动态分配的资源，交给一个类对象去管理，当类对象声明周期结束时，自动调用析构函数释放资源
  2. 常用的智能指针：shared_ptr、unique_ptr、weak_ptr、auto_ptr

Network OS DB

1、如何优化查询过程
2、left join 和 right join 区别 ，联合索引了解吗
  • 指对表上的多个列进行索引，联合索引也是一棵B+树，不同的是联合索引的键值数量不是1，而是大于等于2.
  • 优化：在联合索引中将选择性最高的列放在索引最前面。
3、乐观锁和悲观锁了解吗 参考ByteDanceGuide.md
4、网页请求过程 参考
5、死锁了解吗

进程和线程区别：进程是分配资源单位，线程是调度单位

虚拟内存了解吗，相比于使用物理内存的优点在哪

  • 虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

  • 为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。**这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。**当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

  • 从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。

    例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

6、[算法] 一串数字任意排列，处理一下，奇数在前升序，偶数在后逆序

当时有点紧张，只完成了80%，那个sort的自定义排序还是不熟悉啊

7、[场景] 海量数据100G选择TOP 100个单词

注意只需要选取每个文件中前100个单词，然后再归并

推荐融合

2023.06.16 15:00-16:00

1、自我介绍、项目收获

2、C++ 新特性

3、share_ptr 是线程安全的吗，引用计数如何设计

线程安全：多线程操作一个共享数据的时候，能够保证所有线程的行为是符合预期的

share_ptr 的线程安全隐患：

  • 引用计数的加减操作是否线程安全
  • shared_ptr修改指向时，是否线程安全
  • 作为类模板，shared_ptr<T>的T的并发操作的安全性也要考虑

share_ptr 中含有两个指针：

  • 除了有一个指针，指向所管理数据的地址
  • 还有一个指针指向一个控制块的地址，控制块中存放所管理数据的数量（常说的引用计数）、weak_ptr 的数量、删除器、分配器

① 引用计数是否线程安全

对于引用计数这一变量的存储，是在堆上的，多个shared_ptr的对象都指向同一个堆地址，在多线程环境下，管理同一个数据的 share_ptr 在进行计数的增加或减少的时候是线程安全的，因为这一操作是原子操作

To satisfy thread safety requirements, the reference counters are typically incremented using an equivalent of std::atomic::fetch_add with std::memory_order_relaxed (decrementing requires stronger ordering to safely destroy the control block)

② 修改指向是否线程安全

  • 多线程代码操作的是同一个 share_ptr 的对象，例如 通过引用捕获的 lambda 表达式、函数传指针或者引用 时，此时是线程不安全的
  • 多线程代码操作的不是同一个 share_ptr 的对象，指的是管理的数据是同一份，而shared_ptr不是同一个对象，例如通过 值捕获的 lambda 表达、函数值值传递时，是线程安全的

③ 所管理数据的线程安全

一般来说，多线程如果存在同时修改 STL 容器的情况是极有可能引发线程安全问题的，例如多线程同时对一个 vector 进行 push_back

参考：c++ 11 的shared_ptr多线程安全？

4、mutex 和 mysql 中的读写锁区别

5、Makefile 原理，代码编译过程，代码检查在哪一个阶段

  • 预处理（Preprocessing）：预处理器根据预处理指令（例如#include、#define等）对源代码进行处理，展开宏定义、包含头文件等。预处理后的代码被称为"翻译单元"（translation unit）

  • 编译（Compilation）：编译器将预处理后的翻译单元转换为汇编代码。在这个阶段，编译器会对代码进行语法和语义检查，包括变量和函数的声明和定义是否一致，是否使用了未声明的标识符等

    如果在代码中将一个字符串变量赋值给一个整型变量，编译器会在编译阶段发现类型不匹配的错误，并生成编译错误报告

  • 汇编（Assembly）：汇编器将编译生成的汇编代码转换为机器代码（目标代码）

  • 链接（Linking）：链接器将目标代码与所需的库函数和其他目标代码进行链接，生成可执行文件。在这个阶段，符号解析和地址重定位等操作被执行

6、实现一个单例

7、找出 1-n 乱序数组中缺失的那一个元素

原地交换

网盘国际部

一面

2023.08.22 11:00-12:00 服务端 Golang、MySQL、Redis、消息队列

1、MySQL 事务 ACID、MVCC 原理

2、索引 B+ 树结构，如何优化索引、索引失效情况、分析耗时操作

3、TCP SYN 攻击、怎么解决，拥塞控制算法

  • 了解半连接队列（SYN队列）和全连接队列（Accept队列），参考：xiaolincoding
  • SYN 攻击 是一种常见的 DoS/DoSS 攻击

4、算法：279. 完全平方数

二面

2023.08.25 18:00-19:00

1、TCP CLOSE_WAIT 是什么，断开连接的各种状态

  • 主动断开方有 TIME_WAIT，被动方才有 CLOSE_WAIT（收到 FIN 就会进入），别弄混了
  • 考虑常见客户端主动断开连接、服务端被动断开的情况
    • 客户端：FIN_WAIT_1 --> FIN_WAIT_2 --> TIME_WAIT --> CLOSED
    • 服务端：CLOSE_WAIT（收到 FIN） --> LAST_ACK --> CLOSED

2、TCP 半连接队列

3、epoll 原理，有什么不同的触发方式

4、协程了解吗

5、DASH 协议，连接过程

6、MySQL 脏读和幻读，有哪些锁

7、Redis 结构，跳表（没看过...）

8、手撕 LRU

网盘技术部

一面

2023.12.05 — 15:00-16:00

  • const 和 define 区别，const 可以 debug 吗

  • 引用和指针区别

  • C++ 智能指针，unordered_map

  • 1000 有毒的药水，只有一瓶药水有毒，最少用多少老鼠可以判断

    二分查找 + 布隆过滤器，2^10 = 1024 --> 10 只老鼠，参考

    位运算：参考

  • 堆和栈的区别，如何分配堆内存

    malloc 底层通过 brk 和 mmap 分配内存，都是分配的虚拟内存

    • brk：将进程的数据段（data segment）末尾地址（通常是_edata）往高地址推，从而扩展进程的堆空间；一般用于小型的内存分配，因为它在物理内存上是连续的，可能存在内存碎片的问题
    • mmap: 在进程的虚拟地址空间中映射一块新的内存区域，适用于大型的内存分配，因为 mmap 不要求内存是连续的，它可以映射非连续的物理内存页，可以避免内存碎片
    #include <unistd.h>
// end_data_segment参数是指向新的数据段末尾地址的指针
// 如果brk调用成功，它将返回0；否则，返回-1，并设置errno变量以指示错误原因
int brk(void *end_data_segment);

#include <sys/mman.h>
// addr参数是指定映射区域的起始地址（通常为NULL，表示由系统自动分配）
// length参数指定映射区域的大小；prot参数指定映射区域的访问权限
// flags参数指定映射区域的其他属性；fd参数是指定文件描述符（通常为-1）
// offset参数是指定文件偏移量（通常为0）
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

  • 进程通信方式，进程和线程区别

  • TCP 为什么需要四次挥手，TCP 和 UDP 区别，拥塞控制算法

  • 算法：189. 轮转数组

二面

2023.12.13 — 16:00-16:40

  • 自我介绍，以后从事的工作技术栈有倾向吗，算法还是工程，可以实习吗

  • 访问 www.baidu.com 的具体过程

  • IO 复用、重载和重写区别

  • RPC 和部署方式有关系吗

  • MySQL 使用过哪些场景，微博大V和粉丝场景如何设计表结构

    User 用户表：user_id, username, email, password, ...

    Weibo 微博表：weibo_id, user_id, content, timestamp, ...

    Follow 关注表：follower_id, following_id, timestamp, ... （前两个是用户表的外键）

    Like 点赞表：user_id（用户表外键）, weibo_id（微博表外键）, timestamp, ...

    • 大V和粉丝的关系通过 Follow 表进行管理。当一个用户关注另一个用户时，在 Follow 表中插入一条记录
    • 用户发表微博时，将微博信息插入到 Weibo 表中
    • 用户之间的关系和点赞关系通过外键关联进行维护

  • 算法：1. 两数之和 （我似乎做成了三数之和...

最后直接被感谢... 面完即挂