算法笔试 | 某厂测开复盘

发表于 分类于

今天笔试某厂测开岗，选择还行，算法全寄，遂复盘之

操作系统八股 内存的分页和分段

分页

分页是一种内存管理方案，它将程序的虚拟地址空间和物理内存都划分成固定大小的块。虚拟内存的块称为“页”，物理内存的块称为“页框”或“帧”。页和页框的大小通常相同（例如 4KB）。

虚拟地址 = 页号 + 页内偏移量 物理地址 = 页框号 + 页内偏移量

分段

分段是一种更符合程序员视角的内存管理方案。一个程序被划分为若干个逻辑段，例如：代码段、数据段、堆段、栈段等。每个段都有其特定的用途（如代码段可读可执行但不可写）。

操作系统为每个进程维护一张段表，该表记录了每个段的基地址（在物理内存中的起始地址）和段长（段的界限）。

特性 分页（一维） 分段（二维）
地址空间视图 一个连续的线性空间 多个独立的逻辑空间（段）
“号”的含义 系统管理的索引号（第几页） 程序定义的逻辑标识（哪个段）
对程序员可见 透明（由硬件和OS管理） 可见（通常由编译器管理，但理念上符合程序员思维）
类比 一本书：只需要一个页码和行号 文件柜：需要先选抽屉，再选文件

操作系统八股 银行家算法（Banker's Algorithm）。

银行家算法用于检查系统是否处于安全状态，即是否存在一个安全序列，每个进程按顺序执行，执行完后释放所有资源，使得所有进程都能完成而不导致死锁。

算法题 分零食

题目：小明和弟弟分零食，分零食的次数为c，每次会给到零食的数量n和最便宜的零食价格m,在价目表中，每个零食的价格是前一个零食的m倍（第一个零食价格为m）,小明想给弟弟总和比自己贵的零食，但为了弟弟的自尊心他想自己和弟弟的零食价格差尽量小，每次请输出小明的零食数和小明每个零食的单价

为什么贪心算法是最优的？

  1. 几何序列的超级递增性质：当 (m > 1) 时，零食价格序列是超级递增的，即每个后续零食的价格都大于之前所有零食价格之和。例如，对于 (m=2)，序列为 (2, 4, 8, 16, )，其中 (4 > 2), (8 > 2+4), (16 > 2+4+8)，等等。这种性质意味着贪心算法从大到小选择零食可以确保得到最接近总价一半的子集和，从而最小化价格差。
  2. 对于 (m = 1) 的情况：所有零食价格均为 1。小明最多能拿的零食数为 (k = (n-1)/2 )，这样弟弟拿 (n-k) 个零食，总价差为 1（最小可能值）。贪心算法在这里本质上是直接计算最大 (k) 使得 (k < n/2)。

因此，贪心算法在两种情况下都能保证找到最优解，使价格差最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    int c;
    cin >> c;
    while (c--) {
        int n, m;
        cin >> n >> m;
        
        if (m == 1) {
            // 所有零食价格均为1：小明拿k个，使得k < n/2，且k尽可能大
            int k = (n - 1) / 2;
            cout << k << endl;
            for (int i = 0; i < k; i++) {
                cout << 1 << " ";
            }
            cout << endl;
        } else {
            // 计算零食价格序列和总价S
            vector<ll> prices(n);
            ll total_sum = 0;
            ll current = m;
            for (int i = 0; i < n; i++) {
                prices[i] = current;
                total_sum += current;
                current *= m;
            }
            
            ll小明_sum = 0;
            vector<ll> xiaoming_prices;
            // 从最贵的零食（序列末尾）开始贪心选择
            for (int i = n - 1; i >= 0; i--) {
                if (2 * (小明_sum + prices[i]) <= total_sum) {
                    小明_sum += prices[i];
                    xiaoming_prices.push_back(prices[i]);
                }
            }
            
            // 输出小明的零食数量和每个零食的单价（价格从大到小）
            cout << xiaoming_prices.size() << endl;
            for (int i = xiaoming_prices.size() - 1; i >= 0; i--) {
                cout << xiaoming_prices[i] << " ";
            }
            cout << endl;
        }
    }
    return 0;
}