Skip to content

Latest commit

 

History

History
378 lines (212 loc) · 19.9 KB

Tencent.md

File metadata and controls

378 lines (212 loc) · 19.9 KB

Tencent

WXG—微信支付

2023.04.28—19:00-20:00

1、[算法] 334. 递增的三元子序列 16. 最接近的三数之和

  • 第一题没想到贪心的做法，太紧张也没找到 leftMin 和 rightMax 的写法

  • 第二题直接秒了：排序+双指针

2、deque 和 queue 的不同，底层实现

vector是单向开口（尾部）的连续线性空间，deque则是一种双向开口的连续线性空间，虽然 vector 也可以在头尾进行元素操作，但是其头部操作的效率十分低下（主要是涉及到整体的移动）

img

deque 和 vector 的最大差异一个是 deque 运行在常数时间内对头端进行元素操作，二是 deque 没有容量的概念，它是动态地以分段连续空间组合而成，可以随时增加一段新的空间并链接起来

deque虽然也提供随机访问的迭代器，但是其迭代器并不是普通的指针，其复杂程度比vector高很多，因此除非必要，否则一般使用vector而非deque。如果需要对deque排序，可以先将deque中的元素复制到vector中，利用sort对vector排序，再将结果复制回deque

deque由一段一段的定量连续空间组成，一旦需要增加新的空间，只要配置一段定量连续空间拼接在头部或尾部即可，因此deque的最大任务是如何维护这个整体的连续性

class deque
{
    ...
protected:
    typedef pointer* map_pointer;//指向map指针的指针
    map_pointer map;//指向map
    size_type map_size;//map的大小
public:
    ...
    iterator begin();
    iterator end();
    ...
}

deque内部有一个指针指向map，map是一小块连续空间，其中的每个元素称为一个节点 node，每个 node 都是一个指针，指向另一段较大的连续空间，称为缓冲区，这里就是deque中实际存放数据的区域，默认大小512bytes。结构如下：

img

stack 和 queue 是一种 container adapter，底层可以通过 deque 和 list 实现

3、move 用在哪，是不是所有赋值都可以换成 move

  • 和右值引用一起实现移动语义

  • 肯定不是所有地方都使用 move，因为会将原有的左值置空

move 使用前提：① 定义的类使用了资源并定义了移动构造函数和移动赋值运算符；② 该变量即将不再使用

4、MySQL 设计一张表怎样考虑，一张表很大怎么办

考虑表和字段的命名、字段类型和长度、索引设计、主键和外键的设计、数据库的范式理论

当一张表非常大时，可能会对性能和可维护性造成负面影响。以下是一些处理大表的常见技术：

  1. 分区：将大表分成多个逻辑部分，以减少在单个表上执行的操作。例如，按时间范围将表分成多个分区，或者按地理位置将表分成多个分区。
  2. 水平拆分：将表中的行分成多个表。例如，按照某个关键字或 ID 将表拆分成多个表，可以减少在单个表上执行的操作，提高性能。
  3. 垂直拆分：将表中的列拆分成多个表。例如，将大表拆分为只包含少量高频列的主表和包含大量低频列的附属表，可以减少在读取数据时所需的 I/O 操作次数，提高性能。
  4. 增加索引：对于大表的查询操作，增加合适的索引可以加速查询速度。
  5. 数据归档：将旧数据归档到其他存储介质，如归档到 Hadoop 或其他云服务平台。

5、union 和 join 的区别

join

  • 内连接：也是等值连接，inner join

  • 自连接：内连接的一种，连接表自身，更特殊的是自然连接，natrual join

    内连接和自然连接的区别：内连接提供连接的列，而自然连接自动连接所有同名列

  • 外连接：左外连接 left outer join，右外连接 right outer join，全外连接

union

  • 每个查询必须包含相同的列、表达式和聚集函数

  • 默认会去除相同行，如果需要保留相同行，使用 UNION ALL

  • 只能包含一个 ORDER BY 子句，并且必须位于语句的最后

4、进程、线程、协程区别

  1. 进程（Process）： 进程是操作系统资源分配的基本单位，每个进程都有独立的内存空间、独立的运行环境、独立的代码空间，它们之间通过进程间通信（IPC）来进行通信和协作。在Linux中，进程通过fork()系统调用创建，并可以通过exec()系统调用来替换自己的代码和数据。每个进程都有自己的pid（进程号）。
  2. 线程（Thread）： 线程是进程内部的一条执行路径，多个线程可以共享进程的代码、数据和打开的文件等资源，但每个线程都有自己的栈空间。线程之间的通信和协作可以通过共享内存等方式实现。在Linux中，线程通过pthread_create()函数创建，它们共享同一个进程号。
  3. 协程（Coroutine）： 协程是一种用户态的轻量级线程，它可以在同一个线程内部实现多个执行路径的切换，比线程更加轻量级，没有进程、线程上下文切换的开销。协程的切换是由程序员手动控制的，可以使用协程库来简化实现。在Linux中，协程可以使用第三方库（如Boost.Coroutine或Coroutine.h）实现。

并不是所有的线程都可以替换成协程

  • 线程是由操作系统内核调度和管理的独立执行单元，它拥有自己的堆栈、寄存器和状态信息，可以通过系统调用实现阻塞、唤醒和同步等操作。而协程则是由程序员手动控制的执行单元，它共享线程的堆栈和寄存器，不需要系统调用，可以通过协作式调度实现非抢占式的多任务并发执行。
  • 线程之间的切换需要内核介入，会涉及到上下文切换和调度开销，需要保护和恢复线程的状态和资源，可能会导致性能和可伸缩性问题。而协程之间的切换是在用户态完成的，不需要内核介入，切换开销很小，不需要保护和恢复线程的状态和资源，可以实现更高的并发性和更低的延迟。
  • 线程可以利用多核CPU的优势，可以将多个线程分配到不同的CPU核心上并行执行。而协程默认运行在同一个线程中，不能直接利用多核CPU的优势，但是可以通过多线程加协程的方式实现并行执行。
  • 线程是基于进程的，每个进程都有自己的虚拟地址空间和系统资源，不同进程之间的通信需要通过IPC机制实现。而协程没有自己的虚拟地址空间和系统资源，可以在同一个进程内共享数据和资源，通信方式更加简单和高效。

7、TCP 如何保证可靠，流量控制和拥塞控制区别，TIME_WAIT 作用

  • TCP 可靠性：校验和、分段、流量控制、拥塞控制、RTO 重传
  • 流量控制是点到点/端到端的；拥塞控制是全局性的，涉及到所有的主机、路由器，以及与降低网络性能有关的所有因素
  • TIME_WAIT 在四次挥手客户端这点收到 FIN 报文之后启动计时器

8、HTTPS 如何实现可靠

在 HTTP 基础上基于 Transport Layer Secure/Secure Socket Layer 协议实现可靠传输，HTTP 默认 80 端口，HTTPS 默认 443 端口，HTTPS 需要到 Certificate Authority 申请数字证书，证书就是「数字签名+原信息」，里面包含服务器的公钥，客户端收到之后会将一个「随机值」（对称密钥）加密传输给服务端，服务端收到之后就可以通过这个「对称密钥」进行加密传输了

扩展：如何用 UDP 实现可靠传输？

9、ping 的原理

Ping 的原理是通过向目的主机发送 ICMP Echo 请求报文，目的主机收到之后会发送 Echo 回答报文。Ping 会根据时间和成功响应的次数估算出数据包往返时间以及丢包率

ICMP 报文分为：

  • 差错报告报文：终点不可达、时间超时、参数问题、改变路由
  • 询问报文：会送 Echo 请求或回答、时间戳 Timestamp 请求或回答

TME—QQ音乐后台

2023.06.15 19:30-20:10 —— go 会员业务

  • 自我介绍、单组播项目（码率、帧率多少）
  • 多态 和 模版：模板实际上就是静态多态
  • 1w 个字符串的数组，如何去重
  • 进程线程区别，为什么线程切换开销比较大
  • TCP 三次握手，第三次握手的 ACK 丢失会怎样

PCG—在线视频游戏产品部

2023.08.14 10:30-11:40

  • 线程进程区别，多进程比多线程一定好吗？实际中有哪些场景是使用多进程

    1. 并发与隔离要求高： 当应用需要隔离性较高且不同任务间需要较强的隔离，可以使用多进程。每个进程有自己独立的地址空间，因此可以实现高度的隔离。
    2. 安全性要求高： 如果应用程序需要高度的安全性，多进程可以减少由于共享内存造成的潜在风险，因为进程之间没有共享的内存。
    3. 稳定性和可靠性： 在某些情况下，进程的崩溃不会影响其他进程，因为它们有独立的地址空间。这可以提高应用的稳定性和可靠性。
    4. 充分利用多核CPU： 多进程可以更好地充分利用多核CPU，因为每个进程可以在不同的核心上并行执行。因此涉及 IO 密集型最好使用多线程、计算密集型使用多进程。
    5. 避免GIL限制： 在某些编程语言（如Python）中，由于全局解释器锁（GIL）的存在，多线程无法充分利用多核CPU。在这种情况下，多进程可以避免GIL限制，实现真正的并行计算。
    6. 可伸缩性： 对于一些需要水平扩展的应用，多进程可以更容易地实现在多台服务器上分布式运行。

  • 程序的内存分区：.text, .bss, .data, heap, stack

  • new/malloc 4G 的内存空间就一定返回 4G 的内存空间吗

    • 显然不是，内存管理都是也页面为单位的，分配的页面数总内存可能大于 4G

  • Linux 系统上 iptable 使用过吗

  • TCP 建立连接过程，如何保证可靠传输

  • TCP 中初始序列号都从零开始吗，什么时候确定的

  • MySQL组成结构 --> 索引结构，相比于二叉树、红黑树，B+ 树好在哪

  • 基于红黑树的定时器中，除了 set 之后还能使用什么

  • 编程：环形数组循环右移

CDG—广告后台开发

2023.09.15 19:00-20:00

  • 做题：归并排序

  • 简答：MySQL 事务隔离级别，默认的可重复度隔离级别，那其他的有还有用吗，有哪些应用场景

    未提交读也是有应用场景，那些需要快速读取最新数据的业务，数据读取之后交给业务自己处理是否丢弃

  • 悲观锁和乐观锁的使用场景

  • MySQL 一张表最多能插入多少行数据

  • 10亿条句子（每个句子不超过 1M），给定10个关键词，打印包含1个及以上关键词的所有句子

    倒排？不需要分文件吗

    好像不太是海量数据处理，可以一行一行的读取，然后按照关键字

    以下是使用倒排索引来查找包含关键字的句子的一般步骤：

    1. 建立倒排索引：遍历所有句子，并为每个关键字维护一个包含该关键字的句子列表。
    2. 查询：当需要查找包含特定关键字的句子时，只需查询倒排索引，而不必遍历整个数据集。

有点迷，完全没怎么问八股，问项目，就简单聊天... 面完即挂

CDG—金融科技

一面

2023.11.09 17:00-18:00

  • 自我介绍之后，问了求职意向以及offer情况

  • 做题：手撕高效的饿汉式单例模式；442. 数组中重复的数据

    • 单例模式：static 没有初始化、static 变量没有 new 对象
    • 原地哈希注释太多？

  • cpp 实际项目经历比较少啊，大家都写 muduo 和 mprpc 项目

  • 线程池如何设计的，线程数量一般是如何考虑的，线程数量为什么和 cpu 核心数相等

    任务分为 CPU 密集型、IO密集型和混合型。

    • 对于 CPU 密集型任务，应配置尽可能小的线程，如配置CPU个数+1的线程数；
    • 对于IO密集型任务，应配置尽可能多的线程，以充分利用CPU资源，如配置两倍CPU个数+1的线程数。

    对于IO密集型任务，线程池的核心线程数可以设置为CPU核心数的两倍以上。这是因为IO操作会导致线程阻塞，如果线程数不足，会导致任务等待的时间过长，影响任务的执行效率。例如，假设有4个CPU核心，那么线程池的大小可以设置为8或10。这样可以充分利用CPU时间，当一个线程在等待IO的时候，其他线程可以继续处理任务。

  • 数据库索引如何设计，结合实际的开发经验说一下

    常用的字段简历索引，前缀索引、联合索引

  • 使用联合索引需要注意什么

    b c 联合条件失效问题，b c a 又是如何处理的？（应该有优化）

  • 反问：主要做什么业务（微信支付中的金融框架开发，主要是 C++、少量 golang

    实际开发经验比较少，缺少后台开发的经验...

二面

2023.11.15 16:00-17:00

两道算法题就做了40min，第一道题还只是说了思路，第二题A了，第二天流程结束...

腾讯视频

一面

2023.12.08 — 11:00 - 11:30

二面

2023.12.12 — 14:00 - 15:00

  • RPC 项目：muduo 网络如何实现高并发的，IO线程和业务线程分离好处？
  • 线程池如果没有空闲线程如何处理
  • 线程池可以对于执行任务时间过长的线程如何处理
  • RPC server 发送数据失败的情况如何处理的？
  • RPC client 传输数据使用 TCP 吗，如何区分，粘包问题？
  • 实习中 Dash.js 执行码率决策的过程
  • 算法：输出字典序最小的最长递增子序列 可能还不太一样，这个是数值最小，还有要求 ASCII 字符最小

IEG—光子工作室

2023.12.17 — 17:00 - 18:00

  • 算法：146. LRU 缓存 和 378. 有序矩阵中第 K 小的元素

    为什么二分结果一定在矩阵中 参考

  • 操作系统进程调度算法

    RR 轮转、 SJN 最短作用优先、FCFS 先来先服务、优先级、多级反馈队列

  • Linux系统如何控制进程优先级以及默认的进程调度算法是啥

    nice命令可以在启动进程时设置初始nice值，而renice命令可以在进程运行时修改nice值。

    Linux中默认是基于时间片轮转（Round Robin）的多级反馈队列调度算法。这个调度算法在多个就绪队列之间切换，每个队列有不同的优先级，并且每个队列使用轮转调度策略。更具体地说，Linux使用CFS（Completely Fair Scheduler）调度器来实现这一算法。

  • 进程、线程、协程区别，线程有哪些独享的资源 🔥

    共享进程的资源：地址空间（代码段|数据段|堆|栈...）、全局和静态变量、fd、信号处理器、进程ID

    线程独占的空间：线程ID、寄存器集合、栈空间、线程局部存储、寄存器变脸、信号屏蔽字

    一般堆空间是共享的，需要保证线程的同步和互斥访问

  • TCP 和 UDP 区别，UDP 可以实现 TCP 的功能吗，QUIC细说？

  • TIME_WAIT 作用，等待时长

    Maxmiun Segment Lifetime 最大报文段的生存事件。因为客户端不知道服务端是否能收到ACK应答数据包，服务端如果没有收到ACK，会进行重传FIN，考虑最坏的一种情况：第四次挥手的ACK包的最大生存时长(MSL)+服务端重传的FIN包的最大生存时长(MSL)=2MSL

    MSL 和 MTU 并不直接相关：

    • MTU是指在网络上传输的数据帧中，能够携带的最大数据量。它通常是数据链路层的一个属性，表示在一个数据包中能够携带的最大字节数。

    • MSL是TCP协议中的一个参数，表示一个TCP报文段在网络中最长的存活时间。MSL的值通常设定为两分钟。除了重传可能丢失的 ACK 以外，还可以防止旧连接的混淆： 在某个连接被关闭后，可能过一段时间内会有新的连接尝试使用相同的本地端口和远程端口。如果没有TIME_WAIT状态，这可能导致新连接混淆并接收到错误的数据。

  • 如何两条链表是否相交以及交点在哪，除了两根指针还有其他方法吗？

    哈希表，双指针 参考

IEG—游戏用户与社区

2024.01.12 — 19:00-20:00

  • 算法：优先级的括号匹配 && 字符串相加

  • 比较有挑战的项目

  • TCP 和 UDP 区别，为什么 TCP 要三次握手

  • select 和 epoll 区别，epoll 两种触发模式及其使用场景

  • MySQL隔离级别，可重复读没有解决什么问题，幻读是什么

  • MySQL 存储引擎 InnoDB 和 MyISAM 的比较

    事务、锁粒度、数据和索引结构、外键约束

  • Redis 有哪些使用场景

心悦会员等 golang 语言

CSIG—腾讯云

2024.03.14 — 11:00-12:00

  • 虚函数继承原理、线程进程区别、进程调度算法

  • 进程内存空间分布 参考

  • 网卡接收到数据然后发送的具体过程 参考

  • TCP 保证可靠性

  • 最长上升子序列的长度、词频统计 TOPk、有环链表、二叉树遍历

  • IO 复用，select/poll/epoll，epoll_wait 等待的时候会释放 CPU 吗

    在IO多路复用中使用epoll_wait等待IO事件的时候，进程会释放CPU。在Linux中，进程状态将会变成"S"（可中断睡眠状态）或"D"（不可中断睡眠状态，通常等待IO）。两个状态下，进程都不会占用CPU资源，因为它们都是不同形式的睡眠状态，CPU会切换到其他进程或线程继续工作。

    "S"状态是可中断的睡眠状态，表示进程正在等待某个条件的满足或某个事件的发生。这种状态下的等待是可以被信号打断的，例如，系统调用如read()在没有数据可读时会使进程进入"S"状态，但接收到信号后，进程可以从系统调用中返回，处理信号。

    "D"状态则是不可中断的睡眠状态，进程在这种状态下一般是正在等待某个硬件级别的IO操作完成，例如，等待磁盘IO或网络IO。这种状态的进程不能被信号打断，因为它们通常涉及到一些必须完成的硬件操作。

    当你调用epoll_wait时，如果当前没有IO事件，进程会进入"S"状态。如果系统调用涉及到硬件级别的不可中断IO操作，进程可以进入"D"状态。这样设计是为了在IO操作期间不消耗CPU资源，同时允许其他进程或线程使用CPU。 所以使用epoll_wait时，进程会进入睡眠状态直到事件发生，从而释放CPU。

主要做存储