Hi! Have a good day!
0%

4-22美团笔试

发表于 更新于

4-22美团笔试

19：00 - 21：00 第二个算法题没写出来，估摸着也寄了

20个专业单选 10个应用算术题 2个编程题

1. 单选

  1. 作业调度

    HRRN（Highest Response Ratio Next，最高响应比优先）调度算法是一种用于作业调度的非抢占式算法，是对响应比优先（RR）算法的改进。

    HRRN调度算法中，每个作业的响应比定义为（等待时间 + 服务时间）/服务时间。当一个作业被放到CPU中运行时，它的响应比将随时发生变化。每当一个作业加入就绪队列时，将对每个作业的响应比计算一次，并选取响应比最高的作业进行调度。

  2. 二叉树中序/后序遍历

    二叉树遍历是指按照一定的规则对二叉树中的节点进行访问。常用的二叉树遍历方式包括前序遍历、中序遍历和后序遍历。以下是它们的具体定义：

    • 前序遍历（先序遍历）：先访问根节点，然后访问左子树，最后访问右子树。
    • 中序遍历：先访问左子树，然后访问根节点，最后访问右子树。
    • 后序遍历：先访问左子树，然后访问右子树，最后访问根节点。

  3. 同步请求子进程还是主进程

    在浏览器环境中，同步请求通常是在主进程中执行的，而不是在子进程中执行。这是因为主进程是负责整个页面加载和渲染的进程，在执行同步请求时，它会被阻塞，直到请求完成并返回结果。如果同步请求在子进程中执行，那么子进程将会被阻塞，导致页面响应速度变慢，甚至出现假死现象。

  4. 大数据量高并发如何缓解

    Q：分库分表都可以缓解写入压力吗

    A：分库分表可以缓解单台MySQL服务器的写入压力，但是并不能完全解决高并发写入压力。因为在分库分表之后，写入压力是分散到了多台MySQL服务器上，但是每台MySQL服务器上的写入压力仍然可能会很高，会导致单台MySQL服务器的性能瓶颈和故障。分库分表只是将写入压力分散到多台服务器上，从而可以提高系统的并发能力和稳定性，但单台服务器的写入性能仍然可能成为瓶颈。

    Q：数据库分离可以缓解写入压力吗

    A：数据库分离可以缓解写入压力。在数据库分离的情况下，可以将不同的数据和应用程序分布在不同的数据库中，从而减少单个数据库的写入压力，提高整个系统的性能。

  5. SQL

  6. 进程 并发性

    进程的并发性是指多个进程在同一时间内同时运行的能力。在计算机系统中，多个进程可以在同一时刻被操作系统调度到不同的 CPU 核心或者处理器中并行执行，从而实现进程的并发性。

  7. 查找效率

    提高查找效率的方式有很多，主要包括以下几种：

    1. 索引优化：创建合适的索引，可以大大提高查找效率。索引可以加速数据的查找以及表的连接等操作，如 B+ 树索引、哈希索引、全文索引等。
    2. 分区技术：在大型数据表中，可以将表根据某个字段进行分区，从而实现数据的快速查找。在进行查询时，只需要对某个分区进行查询即可，而不需要扫描整张表。
    3. 缓存技术：可以将常用或热门的数据缓存起来，以减少查询次数，提高查询速度，如 Redis、Memcached 等缓存技术。
    4. 搜索引擎：通过搭建搜索引擎，可以实现全文检索功能，提高查询效率，如 Solr、Elasticsearch 等搜索引擎。
    5. 分布式查询：在大型数据处理场景下，可以通过分布式查询的方式，将查询请求分散到多个节点上进行处理，提高查询效率，如 Hive、SparkSQL、Hadoop 等大数据处理框架。

    除了上述方式，还可以采用优化 SQL 语句、硬件性能优化、使用缓存或者 NoSQL 数据库等方式来提高查询效率。不同的场景和需求需要不同的优化方式进行结合使用，以满足具体的业务需求。

  8. epoll 查找元素的时间复杂度：O(1)

    epoll 是一种高效的 I/O 事件通知机制，在 Linux 操作系统中被广泛应用于网络编程中，能够有效避免传统 select 和 poll 模型中，随着监听文件描述符数量增多，事件通知效率下降的问题。epoll 的事件管理模型是基于事件触发实现的。它通过 epoll_ctl 将需要监听的 socket 文件描述符注册到 epoll 模型中，再通过 epoll_wait 系统调用来等待这些事件的发生。

    epoll 的时间复杂度是 O(1)，因为它用红黑树来存储文件描述符，而红黑树具有对数时间复杂度 O(logn) 的特点，它可以在一些比较大的 file descriptor 中快速定位到要处理的事件，而不需要轮询，因此效率高于 select 和 poll 模型。

    综上所述，epoll 作为一种高效的 I/O 事件通知机制，它具有时间复杂度低、高效性强、可扩展性好的特点，被广泛应用于大规模高并发的网络编程中。

  9. BFS

    BFS（Breadth First Search），又称广度优先搜索，是从起始点开始逐层扫描整张图，先一层一层搜索，直到找到目标点为止。在搜索过程中，使用一个队列来保存每一层的所有节点，先进先出，逐层递进，直到搜索到目标节点为止。BFS 的时间复杂度为 O(|V|+|E|)，其中 |V| 表示节点个数，|E| 表示边数。

    DFS（Depth First Search），又称深度优先搜索，是从起始点开始一直往深处搜索，直到找到目标节点为止。在搜索过程中，从起始节点开始，递归地搜索它的相邻节点，每次只选择其中一个节点继续深入，直到找到目标节点或者没有相邻节点为止。DFS 的时间复杂度为 O(|V|+|E|)，其中 |V| 表示节点个数，|E| 表示边数。

    BFS 和 DFS 都有各自的优缺点，在不同的应用场景中可以选择不同的算法。BFS 算法可以找到最短路径，但是需要占用大量的存储空间，其空间复杂度为 O(|V|)，当图中节点较多时，空间开销较大；DFS 算法则可以快速地搜索整张图，但是不能一定找到最短路径，存在搜索深度较深时容易陷入死循环的问题。因此，在实际应用中，需要综合考虑应用场景、搜索结果等的优缺点进行选择。

  10. 适配器模式本质

    适配器模式的本质是将一个已有的接口转化为另一个客户端所需要的接口，以适应不同的环境和需求。它属于结构型设计模式，可以在不改变接口前提下，将原始接口转换为目标接口，使得不兼容的类可以一起工作。

    适配器模式的主要作用是提高代码的复用性和可扩展性。

  11. 递归成立的条件

    递归需要满足以下两个条件才能实现：

    1. 递归调用：在函数体内直接或间接地调用自身。
    2. 结束条件：在递归调用的过程中，一定要存在一个条件，当满足这个条件时，递归调用停止，从而结束递归。

  12. SQL

  13. 图

    连通图是指无向图或有向图中，任意两个顶点之间都存在一条路径，也就是说图中的任意两个顶点都是连通的。无向图中的连通图也被称为连通分量。如果一个无向图有 k 个连通分量，则该图的连通性为 k。

    不连通图是指无向图或有向图中，存在某些顶点之间没有直接相连的路径，也就是说图中有些顶点是不连通的。无向图中，不连通的部分可以被视为若干个由连通部分组成的图，每个连通部分都是一个连通分量。

  14. 水题

  15. 表字段 NULL

    非空是 NOT NULL

  16. ARP协议 单播 广播

    ARP（Address Resolution Protocol）是用于将IP地址转换为MAC地址的协议，常用于局域网中。在ARP请求中，主机会向网络中的所有主机广播ARP请求，以获取某个IP地址对应的MAC地址。因此，ARP协议接收时是广播的。

  17. 辗转相除

  18. 信号量可用资源

    当前信号量表示目前剩余资源，临界区 = 总信号量 - 当前信号量，等待 = 待处理信号 - 剩余资源

  19. GDB打印元素

    GDB（GNU Debugger）是一种功能强大的调试器，是 GNU 软件开发工具集的一部分。

  20. IMAP协议

    IMAP（Internet Message Access Protocol，互联网邮件访问协议）是一个用于从邮件服务器上获取邮件的标准协议。

    IMAP协议的主要功能是让客户端可以直接在邮件服务器上管理邮件，有如下主要特点：

    1. 支持多个客户端同时访问同一个邮箱，比POP3更加适合多设备使用，如手机、平板、笔记本等。
    2. 支持在线邮件阅读，可实现邮件在服务器上的搜索、筛选、排序等高级功能。
    3. 支持邮件的部分下载，节省网络流量，提高效率。
    4. 通过IMAP客户端，可以在邮件服务器上创建、删除、移动邮件，比POP3更加强大和灵活。
    5. IMAP协议和邮件本身的数据结构更加复杂，需要在服务器上消耗更多的资源和时间，因此需要更高的硬件配置。
    6. 支持通过字符串搜索邮件内容。

    IMAP协议在电子邮件传输和管理中扮演着重要的角色，具有更丰富的功能和更强的灵活性，也成为了当前比较流行的邮件协议。

2. 算法题

1. 计算水题

好久没写 C++ 了，要注意多个变量初始化的时候记得分开写。

√：

double up = 0, down = 0;

X：

double up, down = 0;

写 js 写习惯了是这样的。

#include 
using namespace std;
int point[2000];
int score[2000];

int main()
{
  int T;
  scanf ("%d", &T);
  while (T--) {
    int n, x = 0;
    scanf("%d%d", &n, &x);
    for (int i = 0; i < n; ++i) {
        scanf ("%d", &point[i]);
    }
    for (int i = 0; i < n; ++i) {
        scanf ("%d", &score[i]);
    }

    bool flag;
    flag = true;
    double up = 0, down = 0;
    for (int i = 0; i < n; ++i) {
        if (score[i] < 60) {
            flag = false;
            break;
        }
    }
    if (flag == false) {
        printf("No\n");
        continue;
    }
    for (int i = 0; i < n; ++i) {
        up += point[i] * score[i];
        down += point[i];
    }
    double res = up / down;
    if (res >= x) {
        printf("Yes\n");
        continue;
    } else {
        printf("No\n");
    }
  };
  return 0;
}

2. 完全背包问题

n种作物，m的时间，接下来三行

第一行t，表示每种作物成熟所需时间

第二行a，表示作物成本

第三行b，表示卖出作物的价格

输出最大收益

c[i]=b[i]-a[i]表示单一作物的收益

f[i][j]表示可以选择前i种作物，总时间为j的情况下的最优解

f[n] [m]==>最终结果

f[ 0 ] [j]=0
f[i][0]=0

状态转移方程
f[i][j]=max(f [ i - 1 ] [ j ],c[i]+f[i][j-t[i]])

计算第i行的时候，确定的是第i种作物种几个
决策： 0/1 01背包
k 完全背包

for i=1..n
for j=1..m
f[i][j]=k* c[i]+f[ i-1 ] [j-k * t[i]]

把第三次循环的 k 优化掉了，原因是不需要计算同一行前一个已经计算过的冗余部分，直接拿前一个的计算结果即可，因为前面计算过的已经找到了最优的解。

示例

#include 
using namespace std;

int main() {
    int n, V;
    cin >> n >> V;

    int w[n+1], v[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    int dp[V+1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        for (int j = w[i]; j <= V; j++) {
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }

    cout << dp[V] << endl;
    return 0;
}