字节跳动面试题 I

面试/笔试题 阅读量

机会留给有准备的人

一面(约1h)

在面对未知的流量暴增, 可以预先怎么处理

流量暴增的原因?

    1. 不可预测流量: 网站被恶意刷量; CDN回源抓取数据; 合作业务平台调取平台数据等;
    1. 可预测流量: 突然爆发的社会热点;营销活动的宣传

不管是可预测流量还是不可预测流量都会表现在带宽和网站整体架构的应对方案上

  • 如果是由于带宽原因引起, 由于网站的并发量太高,达到了服务器的吞吐极限, 导致服务器宕机;这时就需要临时申请加大带宽,做负载均衡分流

  • 如果由于外网请求数据库,导致数据库频繁读写,数据库处理能力低,导致大量请求积压;如果是这种情况就需要优化SQL, 存储过程等;如果是请求过大就需要考虑做集群;

  • 面对可预测流量的暴增:

    • 增加后端应用服务器的数量, 数据库读写分离, 分库分表

预备方案

  • 流量估算
  • 降级方案
  • 限流方案

参考: 如何应对网站流量暴增

如何限流, 限流算法, 对于ddos攻击怎么处理

  • 计数器
  • 滑动窗口
  • 漏桶
  • 令牌

参考: 限流方案

ddos攻击处理

高防IP流量迁移

  • 遇到1G以下的攻击，使用防火墙就可以搞定（或者使用一些免费的云防御产品）
  • 流量1G—10G时可以选择机房进行流量迁移和清洗
  • 大于10G时使用高防CDN（云防御）是相对最靠谱并且价钱最能接受的

参考: 分享：一次从遭遇DDoS攻击到解决的亲身经历
参考: 记一次DDOS攻击防御实录

PHP数组的底层实现

  • hashTable

PHP 中的数组实际上是一个有序映射。映射是一种把 values 关联到 keys 的类型。

PHP 数组的底层实现是散列表（也叫 hashTable 哈希表)，散列表是根据键（Key）直接访问内存存储位置的数据结构，它的key - value 之间存在一个映射函数，可以根据 key 通过映射函数得到的散列值直接索引到对应的 value 值，无需通过关键字比较，在理想情况下，不考虑散列冲突，散列表的查找效率是非常高的，时间复杂度是 O(1)。

到这里有个问题出现了：存储在散列表里的元素是无序的，PHP 数组如何做到按顺序读取的呢？

答案是中间映射表

分布式事务

分布式事务指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于不同的分布式系统的不同节点之上。
简单的说，就是一次大的操作由不同的小操作组成，这些小的操作分布在不同的服务器上，且属于不同的应用，分布式事务需要保证这些小操作要么全部成功，要么全部失败。
本质上来说，分布式事务就是为了保证不同数据库的数据一致性。

  • 首先答事务是什么, 然后答分布式事务是什么

RPC相对于传统的API调用的优点

RPC (Remote Procedure Call 远程过程调用)
简单理解就是: 一个节点请求另外一个节点提供的服务 本地过程调用

  • 区别:

    • REST (HTTP-Based)
    • RPC (Socket-Based)

  • RPC优点

      1. 方便使用RPC调用远程函数, 并得到相应的结果,就像调用本地方法一样
      1. 编写分布式应用程序更加简单,容易,因为RPC将所有的网络代码都隐藏到了存根函数中
      1. RPC是跨语言的

服务调度中心的感知与动态上下线

  • zookeeper

在实际的生产环境中我们一般都是集群环境部署的，同一个程序我们会部署在相同的几台服务器中，这时我们可以通过负载均衡服务器去调度，但是我们并不能很快速的获知哪台服务器挂掉了，这时我们就可以使用zookeeper来解决这个问题。

参考: 分布式服务动态上下线感知

MySQL的索引, 为什么是B+而不是平衡二叉树

  • B+数的磁盘读写代价更低: B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
  • B+树的查询效率更加稳定: 由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
  • B+树的数据都存储在叶子节点中,分支节点均为索引,方便扫库,只需要扫一遍叶子节点即可

B树在提高了IO性能的同时并没有解决元素遍历的效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

参考: 为什么MySQL数据库索引选择使用B+树？
参考: 快速理解平衡二叉树、B-tree、B+tree、B*tree

索引查找在Linux的磁盘上是怎么操作的

根据文件路径查询索引节点

参考: 【Linux】Linux根据文件路径查找索引节点

聚簇索引相对于B+索引的优点

InnoDB默认会为每个表创建这样一个索引，叫做聚簇索引。
聚簇索引只能在搜索条件是主键值时才能发挥作用。

加了主键以后，整个表变成了一个索引，也就是所谓的「聚簇索引」。 这就是为什么一个表只能有一个主键， 一个表只能有一个「聚簇索引索引」，因为主键的作用就是把「表」的数据格式转换成「索引（平衡树）」的格式放置。

因为由存储引擎实现索引，所以，并不是所有的引擎都支持聚簇索引。目前，只有solidDB和InnoDB（MySQL的支持）。

非聚簇索引和聚簇索引的区别在于: 通过聚簇索引可以查到需要查找的数据， 而通过非聚簇索引可以查到记录对应的主键值 ， 再使用主键的值通过聚集索引查找到需要的数据

参考: 数据库索引（索引的优缺点、创建原则、B树与B+树、聚簇索引与非聚簇索引）

回表

当我们需要根据指定列查询完整的用户记录时，我们需要根据二级索引查找到记录的主键值，然后再根据主键值使用聚簇索引查询完整的用户记录，这一过程叫做回表。

如何分析SQL执行慢的原因

  • SQL偶尔执行慢
    • 网络抖动
    • Innodb脏页刷新
    • 操作等待锁资源
  • SQL一直执行慢
    • 首先肯定,这个SQL肯定有问题, 需要排查原因
    • SQL执行没有索引
    • SQL执行走了索引, 但是类型是ALL
    • 单表数据量过大 (InnoDB的数据表数量级超过千万后，性能会出现下降，核心是由于B+Tree的数据结构导致的)

参考: SQL执行慢的原因分析

Redis连接时的connect和pconnect的区别

  • connect: 脚本结束后连接就释放了

  • pconnect: 脚本结束后连接不释放,连接保持再php-fpm的进程中

  • 本站pconnect 有什么问题

参考: Redis中connect与pconnect区别？

Redis有哪些结构时间复杂度较高

时间复杂度由低到高:
常数阶O(1) < 对数阶O(logN) < 线性阶O(n) < 线性对数阶O(nlogN) < 平方阶O(n²) < 立方阶O(n³) < K次方阶O(n^k) < 指数阶(2^n)

  • String: 最高是O(n) (mset, msetnx)
  • List: 最高是O(n) (lpush, lrange)
  • Hash: 最高是O(n) (hmset/hmget, hdel, hgetall, hkeys/hvals)
  • Set: 最高是O(n) (sadd, srem, srandmember, spop)
  • SortedSet: 最高是O(nlogN) (zadd, zrem)

Redis hash的实现

Redis的数据库就是使用字典作为底层实现的，通过key和value的键值对形式，代表了数据库中全部数据。而且，所有对数据库的增、删、查、改的命令，都是建立在对字典的操作上。

参考: Redis之Hash数据结构

算法题

在1个10G大小的文件中, 存储的都是int型的数据, 如何在内存使用小于8M的情况进行排序

参考: 归并排序，外排序，10G文件500M内存的排序

设计题

以微博为例, 有1个亿的用户,同事用户之间有关注和粉丝,用户的关注和取关操作比较频繁, 如何设计架构和API接口

参考: 新浪微博技术架构分析和设计

二面 (约1.5h)

二面主要以自己的项目为切入点，进一步考察你对项目中知识点的把握程度

守护进程是什么, 怎么实现

守护进程（Daemon）是运行在后台的一种特殊进程，也称为精灵进程。

实现守护进程的一般步骤:

  1. 父进程fork出子进程并exit退出
  2. 子进程调用setsid创建新会话
  3. 子进程调用系统函数chdir将根目录”/“修改成为子进程的工作目录
  4. 子进程调用系统函数umask将该进程的umask设置为0
  5. 子进程关闭从父进程继承的所有不需要的文件描述符

参考: 实现守护进程
参考: 守护进程详解及其代码实现

PHP是否适合做守护进程, 为什么 (内存管理这一块)

不适合, 可能有内存泄露问题

PHP的垃圾回收机制

1.引用计数 2.写时拷贝

进程间的通信方式

  1. 匿名管道
  2. 高级管道
  3. 命名管道
  4. 消息队列
  5. 信号量
  6. 信号
  7. 共享内存
  8. 套接字

参考: 进程间8种通信方式详解
参考: 进程间的五种通信方式介绍

共享内存是怎么实现的

共享内存（share memory）是一种最为高效的进程间通信方式，是因为进程能够直接对内存进行读写，且不需要进行数据的保存与复制。

共享内存的实现较为简单，一共分为两个步骤：

  1. 创建共享内存: 通过函数shmget()从内存中获取一块共享内存区域,该函数返回值为共享内存的ID
  2. 映射共享内存: 通过函数shmat()将上一步获取的共享内存映射到具体的内存空间

怎么查看Linux服务器的负载, 及判断哪些操作引起的负载过高

查看服务器负载有多种命令，w或者uptime都可以直接展示负载

  • uptime
1
2
[root@iZuf6e3565o1e3wg8p9os5Z ~]# uptime
14:57:56 up 82 days, 23:22,  1 user,  load average: 0.08, 0.07, 0.01

load average分别对应于过去1分钟，5分钟，15分钟的负载平均值。

  • w
1
2
3
4
[root@iZuf6e3565o1e3wg8p9os5Z ~]# w
14:59:40 up 82 days, 23:24,  1 user,  load average: 0.01, 0.05, 0.00
USER     TTY      FROM              LOGIN@   IDLE   JCPU   PCPU WHAT
root     pts/0    183.62.22.202    14:59    0.00s  0.00s  0.00s w

这两个命令只是单纯的反映出负载，linux提供了更为强大，也更为实用的top命令来查看服务器负载。

  • top
1
2
3
4
5
top - 15:00:51 up 82 days, 23:25,  1 user,  load average: 0.11, 0.08, 0.01
Tasks: 495 total,   1 running, 494 sleeping,   0 stopped,   0 zombie
Cpu(s):  2.8%us,  0.7%sy,  0.0%ni, 96.5%id,  0.0%wa,  0.0%hi,  0.1%si,  0.0%st
Mem:  15930632k total, 15374752k used,   555880k free,   326284k buffers
Swap:        0k total,        0k used,        0k free, 11117084k cached
  • Tasks行展示了目前的进程总数及所处状态，要注意zombie，表示僵尸进程，不为0则表示有进程出现问题。
  • Cpu(s)行展示了当前CPU的状态，us表示用户进程占用CPU比例，sy表示内核进程占用CPU比例，id表示空闲CPU百分比，wa表示IO等待所占用的CPU时间的百分比。wa占用
  • Mem行展示了当前内存的状态，total是总的内存大小，userd是已使用的，free是剩余的，buffers是目录缓存。
  • Swap行同Mem行，cached表示缓存，用户已打开的文件。

在top命令下，按1，则可以展示出服务器有多少CPU，及每个CPU的使用情况

一般而言，服务器的合理负载是CPU核数*2。也就是说对于8核的CPU，负载在16以内表明机器运行很稳定流畅。如果负载超过16了，就说明服务器的运行有一定的压力了。

判断哪些操作引起的负载过高

  • vmstat
1
2
3
4
[root@iZuf62rvlhskrte5956lmlZ ~]# vmstat
procs -----------memory---------- ---swap-- -----io---- --system-- -----cpu-----
r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
0  0      0 4397908 381736 29914792    0    0     0     4    0    0  3  1 96  0  0
  • r 列表示运行和等待cpu时间片的进程数，如果长期大于1，说明cpu不足，需要增加cpu。
  • b 列表示在等待资源的进程数，比如正在等待I/O、或者内存交换等。
  • us 列显示了用户方式下所花费 CPU 时间的百分比。us的值比较高时，说明用户进程消耗的cpu时间多，但是如果长期大于50%，需要考虑优化用户的程序
  • sy 列显示了内核进程所花费的cpu时间的百分比。这里us + sy的参考值为80%，如果us+sy 大于 80%说明可能存在CPU不足。

参考: linux 下查看系统资源和负载,以及性能监控

MySQL的IO过高怎么优化, 分库分表及分区

参考: mysql分区、分表、分库、数据分片

分库后的问题

  • 分布式事务
  • 跨库Join
  • 排序,分页,分组

MySQL的索引结果, MyISAM和Innodb的索引结构, Innodb为什么必须要有主键索引

  • MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址
  • 虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同
    • 第一个重大区别是InnoDB的数据文件本身就是索引文件
    • 第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址

参考: MySQL中myisam和innodb的主键索引有什么区别？

添加索引, 为什么可以减少io操作 (磁盘页)

DB在执行一条Sql语句的时候，默认的方式是根据搜索条件进行全表扫描，遇到匹配条件的就加入搜索结果集合。如果我们对某一字段增加索引，查询时就会先去索引列表中一次定位到特定值的行数，大大减少遍历匹配的行数，所以能明显增加查询的速度。

Nginx的负载均衡算法

  • 轮询round robin (默认): 轮询方式，依次将请求分配到各个后台服务器中，默认的负载均衡方式。
  • 权重weight: 根据权重来分发请求到不同的机器中，指定轮询几率，weight和访问比率成正比，用于后端服务器性能不均的情况。
  • ip_hash: 根据请求者ip的hash值将请求发送到后台服务器中，可以保证来自同一ip的请求被打到固定的机器上，可以解决session问题。
  • url_hash: 根据请求的url的hash值将请求分到不同的机器中，当后台服务器为缓存的时候效率高。
  • fair: 根据后台响应时间来分发请求，响应时间短的分发的请求多。

参考: Nginx的五种负载算法

算法题

查找一个字符串中最长的无重复字符串

我们可以定义字符到索引的映射 当我们找到重复的字符时，我们可以立即跳过该窗口。
也就是说, 如果 str[i] 在[i,j]范围内有与i重复的字符, 我们不需要逐渐增加j;我们可以直接跳过[i, j]范围内的所有元素, 并将j变成i+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function longestSubstring($str)
{
    $len = strlen($str);
    $i = 0;
    $j = 0;
    $maxStrLen = 0;
    $set = [];
    while ($i < $len) {
        // PHP中 [(下标)] 符号不仅可以应用于数组和对象，还可以应用于字符串
        if (array_key_exists($str[$i], $set)) {
            $j = max($j, $set[$str[$i]]);
        }
        $maxStrLen = max($maxStrLen, $i - $j + 1);
        $set[$str[$i]] = $i + 1;
        $i++;
    }
    return $maxStrLen;
}

三面 (约0.6h)

三面与二面的内容差不多，没有更深的问题，但是，需要注重细节，同时三面面试官有时间会放烟雾弹，坚定自己的立场就好

在一个横向和纵向都是递增的有界二维坐标轴中，如何快速判断某个数是否存在于这个二维坐标中

设计一个定时任务管理器

参考: golang实践-如何实现高性能的定时任务管理器

算法题

经典赛马问题,8个赛道,64匹马,比赛多少次可以找出前四名

  1. 赛8场, 每场后4名淘汰 (8次)
  2. 选择每组的第一名再出来跑一次，这样落后的第一名所在的整组都可以排除 (1次)
  3. 组间的第一名有了名次关系，可以发现一定不属于前4名，因为都在他们前面。同理可排除。同时是最快的，一定属于前4。那接下来只需在剩下的9匹中找出前3 (1次)
  4. 除去，其余8匹跑一次。如果在第3名或者更后，那说明已经选出了前3名，也不用再跑了，否则再取前3和一起跑一次，即可得结果。(1次)

最多11次一定可以选出最快的4匹

参考: 腾讯面试题：64匹马，8赛道，找出最快的4匹最少要几次?

Hr面 (约0.5h)

这个就是见仁见智了

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2023 Keep It Simple And Stupid All Rights Reserved.

访客数 : | 访问量 :