字节一面，轻松通过！

哈喽~，大家好，我是千羽。

下面分享我认识的一位大佬华中科技大学985硕，字节机器学习暑期实习一面，

这一面整体上问的不难，主要问基础和基本算法，轻松oc。

• 1. Java的vector和list有什么区别？
• 2. ArrayList和LinkedList有什么区别
• 3. 说一下C++的多态
• 4. 有了解C++的shared_ptr 吗？
• 5. 算法题：二分模板题

字节-机器学习系统研发一面(pass)

1、先是问项目，就是Deep Java Library深度学习的项目，然后字节夏令营的二等奖项目，然后问了下有没有分布式的经验，我说有一点，做过简单的GRPC

1. Java的vector和list有什么区别？

1. 线程安全性：
   • Vector是线程安全的类，它的方法都是同步的（synchronized），因此可以在多线程环境下安全地使用。
   • List是一个接口，具体的实现类比如ArrayList和LinkedList通常不是线程安全的。如果需要在多线程环境下使用，可以通过Collections.synchronizedList方法来获得一个线程安全的List，但这样可能会降低性能。
2. 增长策略：
   • 在元素数量超过当前容量时，Vector和ArrayList都会自动增长其容量。但是，Vector的增长策略是加倍当前容量，而ArrayList是增加50%。
3. 性能：
   • 由于Vector的方法都是同步的，因此在单线程环境下性能可能会略低于ArrayList。
   • ArrayList通常在大多数情况下会比Vector具有更好的性能，因为ArrayList不需要进行同步操作。
4. 遍历：
   • 对于遍历操作，Vector和ArrayList使用迭代器（Iterator）进行遍历，而LinkedList有自己特有的遍历方式。

2. ArrayList和LinkedList有什么区别

ArrayList和LinkedList都是Java中的List接口的实现类，它们在内部实现和性能方面有一些区别。

1. 内部实现：
   • ArrayList基于动态数组实现。它使用数组来存储元素，支持随机访问，可以根据索引直接访问元素。当容量不足时，ArrayList会自动增长数组的大小。
   • LinkedList基于双向链表实现。每个元素在内存中都保留了对前一个和后一个元素的引用，因此在添加或删除元素时，不需要像ArrayList那样移动元素，只需改变引用即可。
2. 随机访问性能：
   • ArrayList支持随机访问，可以通过索引直接访问元素。因为基于数组实现，所以在访问特定位置的元素时效率较高。
   • LinkedList不支持随机访问，需要从头或尾部开始遍历链表以获取特定位置的元素，因此在访问元素时效率较低。
3. 插入和删除性能：
   • 在ArrayList中，插入和删除元素可能涉及到数组元素的移动，特别是在数组中间插入或删除元素时，需要移动后续元素的位置，因此性能可能较低。
   • LinkedList在插入和删除元素时通常性能较好，因为只需要修改链表中相邻元素的引用即可，不需要像数组一样移动大量元素。
4. 空间占用：
   • ArrayList在不考虑实际存储元素数量时，会预先分配一定的容量。因此，可能会浪费一些内存空间，尤其是在容量设置过大但实际元素数量较少时。
   • LinkedList每个元素都需要额外的空间存储前后元素的引用，因此可能会消耗更多的内存。

3. 说一下C++的多态

C++中的多态性是面向对象编程的一个重要概念，它允许不同类的对象对同一消息做出不同的响应。C++实现多态性主要通过虚函数（virtual function）和继承来实现。

虚函数和多态性

虚函数： 在基类中声明的虚函数可以被子类重写（覆盖）并在运行时动态绑定到相应的函数。使用 virtual 关键字声明函数为虚函数。

class Base {
public:
    virtual void display() {
        cout << "Base display() called" << endl;
    }
};

class Derived : public Base {
public:
    void display() override {
        cout << "Derived display() called" << endl;
    }
};

多态性： 当基类指针或引用指向派生类对象时，通过基类的虚函数进行调用时，会根据实际对象的类型调用对应的函数，这种行为称为多态性。

Base* ptr = new Derived();
ptr->display(); // 调用Derived类中的display()函数

虚函数表（vtable）

C++ 使用虚函数表（vtable）来实现虚函数的动态绑定。每个包含虚函数的类都有一个对应的虚函数表，表中存储了虚函数的地址。在运行时，编译器根据对象的实际类型查找虚函数表，并调用相应的函数。

纯虚函数和抽象类

纯虚函数： 一个类中可以包含纯虚函数，通过在函数声明的末尾添加 = 0 来声明纯虚函数。含有纯虚函数的类是抽象类，无法实例化，只能用作基类。

class AbstractBase {
public:
    virtual void show() = 0; // 纯虚函数
};

抽象类： 包含至少一个纯虚函数的类被称为抽象类。派生类必须实现（覆盖）抽象类中的纯虚函数，否则它们也会成为抽象类。

4. 有了解C++的shared_ptr 吗？

std::shared_ptr 是 C++11 引入的智能指针，用于管理动态分配的对象。它允许多个指针共享对同一对象的所有权，提供了一种更安全和方便的内存管理方式，避免了内存泄漏和悬空指针的问题。

特点和用法

共享所有权： std::shared_ptr 允许多个智能指针共同拥有同一个对象，并且在最后一个引用被销毁时自动释放所持有的资源。

#include <memory>
// 创建一个 shared_ptr 指向整型对象
std::shared_ptr<int> ptr1 = std::make_shared<int>(42);

// 共享同一个对象
std::shared_ptr<int> ptr2 = ptr1;

动态内存管理： 使用 std::make_shared 或 std::shared_ptr 的构造函数来动态分配对象，避免显式地使用 new 和 delete。

std::shared_ptr<int> ptr = std::make_shared<int>(10);

引用计数： std::shared_ptr 内部使用引用计数（reference counting）来记录有多少个指针共享同一对象。当最后一个指针被销毁时，它会自动释放所管理的对象。

自定义删除器（Deleter）： 可以提供一个自定义的删除器函数（deleter function）来处理特定的资源释放操作。

auto deleter = [](int* p) {
    // 自定义释放资源的操作
    delete p;
};
std::shared_ptr<int> customPtr(new int(20), deleter);

使用注意事项

• 避免循环引用：std::shared_ptr 可能会出现循环引用导致资源无法释放的问题。可以使用 std::weak_ptr 来解决这个问题。
• 不要将裸指针和 std::shared_ptr 混合使用，以免发生悬空指针或重复释放的问题。
• 使用 std::make_shared 来分配动态对象，因为它能更好地管理内存。
• 当共享同一个资源时，确保在不再需要时及时释放智能指针。

std::shared_ptr 是 C++ 中常用的智能指针之一，可以帮助管理动态分配的资源，避免内存泄漏，并提高代码的安全性和可维护性。

5. 算法题：二分模板题

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid; // 找到目标，返回索引
        } else if (nums[mid] < target) {
            left = mid + 1; // 目标在右侧
        } else {
            right = mid - 1; // 目标在左侧
        }
    }
    
    return -1; // 目标不存在，返回 -1
}

解释与注意事项

1. 初始化左右边界： 初始时 left 指向数组开头，right 指向数组末尾。
2. 循环条件： 只要 left <= right，就继续循环。
3. 计算中间值 mid： 使用 (left + right) / 2 可能会出现整数溢出问题，建议使用 left + (right - left) / 2 来计算中间位置。
4. 比较中间值和目标值：
   • 如果 nums[mid] == target，表示找到目标，返回 mid。
   • 如果 nums[mid] < target，说明目标在右侧，更新 left = mid + 1。
   • 如果 nums[mid] > target，说明目标在左侧，更新 right = mid - 1。
5. 循环结束： 如果循环结束仍未找到目标，则返回 -1 表示目标不存在。

• 原文链接：https://github.com/warthecatalyst/What-to-in-Graduate-School/blob/main/%E7%A7%8B%E6%8B%9B%E7%9A%84%E9%9D%A2%E7%BB%8F/%E5%8D%8E%E7%A7%91%E8%AE%A1%E7%A7%91%E7%AC%AC%E4%BA%8C%E4%BA%BA%E7%9A%84%E7%A7%8B%E6%8B%9B%E6%8A%A5%E5%91%8A.md