三星 AI Infra 一面 (1)

发表于 更新于 分类于 ，

Q: 给一串数字形如”000…011111…1”，找第一个1的位置？

由于字符串具有单调性（所有0在前，所有1在后），这是经典的二分查找问题，可以在O(log n)时间内定位第一个1的位置。

算法思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
int findFirst1(const string& s) {
    int left = 0, right = s.size() - 1, ans = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (s[mid] == '1') {
            ans = mid;        // 记录候选答案
            right = mid - 1;  // 继续往左搜索更早的1
        } else {
            left = mid + 1;   // 0区域，搜索右半段
        }
    }
    return ans;
}

关键点：

  • 这是二分查找”左边界”的变体——找满足条件的最小索引
  • 每次取中点：若为0说明第一个1在右侧，若为1说明可能是答案但左侧可能还有1
  • 时间复杂度O(log n)，空间复杂度O(1)
  • 对比线性扫描O(n)，当n=10^9时二分只需约30次比较

常见变体：

  • 旋转排序数组找最小值（同样利用单调性二分）
  • 有序数组找目标值的第一个/最后一个位置（LeetCode 34）

Q: 判断回文字符串？

使用双指针法，一个从头一个从尾向中间移动，逐个比较字符是否相等。

1
2
3
4
5
6
7
8
9
bool isPalindrome(const string& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

时间复杂度O(n)，空间复杂度O(1)。

为什么不用反转字符串比较？ 反转需要O(n)额外空间，且需要遍历两次（反转一次+比较一次），双指针方案更优。

常见扩展与陷阱：

变体 处理方式
忽略大小写和非字母字符（LeetCode 125） 跳过非字母数字字符，统一转小写比较
最长回文子串（LeetCode 5） 中心扩展法或Manacher算法
回文链表（LeetCode 234） 快慢指针找中点+反转后半段+比较
判断一个整数是否回文 反转一半数字比较，避免字符串转换开销

Q: C++中static关键字的作用？

static在C++中有三种不同含义，取决于使用位置：

1. 局部静态变量（函数内）：

1
2
3
4
5
void counter() {
    static int count = 0;  // 只初始化一次，生命周期延长到程序结束
    count++;
    cout << count << endl;
}
  • 生命周期延长到程序结束，但作用域仅限函数内
  • 存储在静态区（非栈上），程序启动时分配
  • C++11保证初始化是线程安全的（编译器插入双重检查锁）
  • 常用于实现Meyers’ Singleton

2. 静态成员变量/函数（类内）：

1
2
3
4
5
class MyClass {
    static int instanceCount;  // 属于类，所有对象共享
    static void printCount();  // 无this指针，不能访问非static成员
};
int MyClass::instanceCount = 0;  // 类外定义初始化
  • 属于类而非对象实例，所有实例共享同一份
  • 静态成员函数没有this指针，只能访问其他static成员
  • 需要在类外单独定义（C++17可用inline static在类内定义）

3. 文件作用域static（全局/自由函数）：

1
2
static int globalVar = 0;     // 内部链接，仅本编译单元可见
static void helperFunc() {}   // 其他.cpp文件无法链接到该函数
  • 限制符号的链接性为内部链接（internal linkage）
  • 防止符号在不同编译单元间冲突
  • C++中推荐使用匿名命名空间替代文件作用域static

对比总结：

用法 存储位置 生命周期 作用域
局部static 静态区 程序全程 函数内
类static成员 静态区 程序全程 受访问控制
文件作用域static 静态区 程序全程 本编译单元

Q: TCP三次握手的流程？

TCP三次握手用于在客户端和服务端之间建立可靠连接，确认双方的发送和接收能力。

完整流程：

1
2
3
4
5
6
7
8
客户端                          服务端
  |                               |
  |------- SYN (seq=x) -------->  |  客户端进入 SYN_SENT
  |                               |  服务端进入 SYN_RCVD
  |<-- SYN+ACK (seq=y, ack=x+1)--|
  |                               |
  |------- ACK (ack=y+1) ------>  |  双方进入 ESTABLISHED
  |                               |

每次握手的目的：

  1. 第一次：客户端告知服务端”我要建连”，发送初始序列号x（证明客户端发送能力正常）
  2. 第二次：服务端确认收到请求，同时发送自己的初始序列号y（证明服务端接收+发送能力正常）
  3. 第三次：客户端确认收到服务端的响应（证明客户端接收能力正常，服务端发送被确认）

为什么需要三次而非两次？

  • 两次握手无法防止历史连接的重复初始化：假设客户端发了一个旧SYN包（网络延迟），服务端收到后建立连接分配资源，但客户端早已不需要该连接——浪费资源
  • 三次握手中，客户端收到SYN+ACK后可以判断是否是自己期望的连接，若是旧连接则发RST拒绝

关键数值：

  • SYN报文不携带数据但消耗一个序列号
  • 初始序列号(ISN)由时钟+随机算法生成，防止被猜测（安全性）
  • SYN重传超时：Linux默认初始1秒，指数退避（1s, 2s, 4s…），最多重试5次

Q: DFS和BFS的性质、数据结构和使用场景？

对比总结：

特性 DFS（深度优先） BFS（广度优先）
数据结构 栈（递归/显式栈） 队列
遍历方式 沿一条路径尽可能深入，回溯后探索其他路径 逐层扩展，先访问所有近邻
空间复杂度 O(h)，h为树的深度/图的最长路径 O(w)，w为最大层宽度
完备性 有环图中可能陷入无限循环（需标记visited） 一定能找到解（如果存在）
最优性 不保证最短路径 无权图中保证最短路径

DFS适用场景：

  • 路径搜索和回溯问题（如N皇后、数独、全排列）
  • 拓扑排序（后序遍历的逆序）
  • 强连通分量（Tarjan算法）
  • 检测环的存在
  • 适合解空间深但宽度有限的问题

BFS适用场景：

  • 无权图最短路径（如走迷宫最少步数）
  • 层序遍历（如二叉树按层输出）
  • 多源BFS（如腐烂橘子问题）
  • 状态空间搜索中找最少变换次数
  • 适合解在浅层（目标距离起点近）的问题

实际应用中的选择建议：

  • 图很深但解在浅层 → BFS
  • 图很宽但解在深层 → DFS（BFS可能爆内存）
  • 需要遍历所有可能路径 → DFS
  • 需要最短路径 → BFS（无权图）或 Dijkstra（有权图）

Q: C++函数重载是什么？

函数重载(Function Overloading)指同一作用域内可以定义多个同名函数，但参数列表（参数个数、类型或顺序）必须不同。编译器在编译期根据调用时传入的实参类型和数量决定调用哪个版本。

实现原理——名称修饰(Name Mangling)：

编译器将函数名+参数类型编码为唯一的内部符号名。例如：

1
2
3
void print(int x);      // 编码为 _Z5printi
void print(double x);   // 编码为 _Z5printd
void print(int x, int y); // 编码为 _Z5printii

链接器通过不同的符号名区分这些函数。这也是为什么C语言不支持重载——C没有名称修饰（extern "C"会禁用修饰）。

重要规则：

  • 返回值类型不同不构成重载（调用时无法仅靠返回值区分）
  • const和非const参数构成重载（对引用和指针有效）
  • 默认参数可能导致歧义：void f(int a, int b=0) 和 void f(int a) 调用f(1)时编译错误

与重写(Override)和隐藏(Hide)的区别：

概念 作用域 条件 时机
重载(Overload) 同一作用域 参数列表不同 编译期
重写(Override) 基类与派生类 虚函数+签名完全相同 运行期
隐藏(Hide) 基类与派生类 同名函数（非虚/签名不同） 编译期

Q: 设计模式中单例模式如何实现？

单例模式保证一个类只有一个实例，并提供全局访问点。

C++11推荐实现——Meyers’ Singleton：

1
2
3
4
5
6
7
8
9
10
11
12
class Singleton {
public:
    static Singleton& getInstance() {
        static Singleton instance;  // C++11保证线程安全
        return instance;
    }
    // 禁止拷贝和移动
    Singleton(const Singleton&) = delete;
    Singleton& operator=(const Singleton&) = delete;
private:
    Singleton() {}  // 构造函数私有
};

为什么C++11后这种写法是线程安全的？

C++11标准规定：如果多个线程同时首次执行到static局部变量声明处，只有一个线程会执行初始化，其他线程会阻塞等待。编译器在底层使用类似双重检查锁(DCLP)+原子标志的机制实现。

各种实现方式对比：

方式 特点 线程安全 延迟初始化
Meyers’ Singleton (C++11) 最简洁，推荐 是 是
饿汉式（全局static对象） main前创建 是 否
双重检查锁(DCLP) C++11前的方案，需memory_order 手动保证 是
std::call_once + once_flag 显式线程安全初始化 是 是

常见陷阱：

  • 析构顺序问题：全局单例间如果有依赖关系，析构顺序可能导致使用已销毁的对象
  • 单元测试困难：全局状态难以mock/reset
  • 隐藏依赖：代码中到处调用getInstance()使依赖关系不透明

Q: C++构造函数能是虚函数吗？

不能。 构造函数不允许声明为virtual，这是C++语言规则所禁止的。

根本原因——虚函数的调用依赖vptr，而vptr在构造函数中才被设置：

  1. 虚函数调用的前提是对象已经有正确的vptr指向对应类的vtable
  2. vptr是在构造函数的初始化阶段设置的
  3. 构造顺序：先构造基类部分（此时vptr指向基类vtable），再构造派生类部分（此时vptr更新为派生类vtable）
  4. 如果构造函数本身是虚函数，在调用构造函数时vptr尚不存在，无法做虚分派

构造函数中调用虚函数的行为：

1
2
3
4
5
6
7
8
9
10
class Base {
public:
    Base() { init(); }     // 这里调用的是Base::init()，不是Derived::init()
    virtual void init() { cout << "Base::init" << endl; }
};
class Derived : public Base {
public:
    void init() override { cout << "Derived::init" << endl; }
};
Derived d;  // 输出"Base::init"！因为Base构造时vptr指向Base的vtable

如何实现”虚构造”——工厂模式：

1
2
3
4
5
6
class Shape {
public:
    virtual ~Shape() {}
    virtual Shape* clone() const = 0;  // 虚拷贝构造（原型模式）
    static unique_ptr<Shape> create(const string& type);  // 工厂方法
};

对比：析构函数应该是虚函数：

  • 多态基类的析构函数必须声明为virtual
  • 否则通过基类指针delete派生类对象时，只调用基类析构函数，派生类资源泄漏
  • 析构时对象是完整的（先析构派生类再析构基类），vptr有效