哈喽~,大家好,我是千羽。
下面分享我认识的一位大佬华中科技大学985硕,字节机器学习暑期实习一面,
这一面整体上问的不难,主要问基础和基本算法,轻松oc。
1、先是问项目,就是Deep Java Library深度学习的项目,然后字节夏令营的二等奖项目,然后问了下有没有分布式的经验,我说有一点,做过简单的GRPC
Vector
是线程安全的类,它的方法都是同步的(synchronized),因此可以在多线程环境下安全地使用。List
是一个接口,具体的实现类比如ArrayList
和LinkedList
通常不是线程安全的。如果需要在多线程环境下使用,可以通过Collections.synchronizedList
方法来获得一个线程安全的List
,但这样可能会降低性能。Vector
和ArrayList
都会自动增长其容量。但是,Vector
的增长策略是加倍当前容量,而ArrayList
是增加50%。Vector
的方法都是同步的,因此在单线程环境下性能可能会略低于ArrayList
。ArrayList
通常在大多数情况下会比Vector
具有更好的性能,因为ArrayList
不需要进行同步操作。Vector
和ArrayList
使用迭代器(Iterator)进行遍历,而LinkedList
有自己特有的遍历方式。ArrayList
和LinkedList
都是Java中的List
接口的实现类,它们在内部实现和性能方面有一些区别。
ArrayList
基于动态数组实现。它使用数组来存储元素,支持随机访问,可以根据索引直接访问元素。当容量不足时,ArrayList
会自动增长数组的大小。LinkedList
基于双向链表实现。每个元素在内存中都保留了对前一个和后一个元素的引用,因此在添加或删除元素时,不需要像ArrayList
那样移动元素,只需改变引用即可。ArrayList
支持随机访问,可以通过索引直接访问元素。因为基于数组实现,所以在访问特定位置的元素时效率较高。LinkedList
不支持随机访问,需要从头或尾部开始遍历链表以获取特定位置的元素,因此在访问元素时效率较低。ArrayList
中,插入和删除元素可能涉及到数组元素的移动,特别是在数组中间插入或删除元素时,需要移动后续元素的位置,因此性能可能较低。LinkedList
在插入和删除元素时通常性能较好,因为只需要修改链表中相邻元素的引用即可,不需要像数组一样移动大量元素。ArrayList
在不考虑实际存储元素数量时,会预先分配一定的容量。因此,可能会浪费一些内存空间,尤其是在容量设置过大但实际元素数量较少时。LinkedList
每个元素都需要额外的空间存储前后元素的引用,因此可能会消耗更多的内存。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; // 纯虚函数
};
抽象类: 包含至少一个纯虚函数的类被称为抽象类。派生类必须实现(覆盖)抽象类中的纯虚函数,否则它们也会成为抽象类。
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++ 中常用的智能指针之一,可以帮助管理动态分配的资源,避免内存泄漏,并提高代码的安全性和可维护性。
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
}
解释与注意事项
left
指向数组开头,right
指向数组末尾。left <= right
,就继续循环。mid
: 使用 (left + right) / 2
可能会出现整数溢出问题,建议使用 left + (right - left) / 2
来计算中间位置。nums[mid] == target
,表示找到目标,返回 mid
。nums[mid] < target
,说明目标在右侧,更新 left = mid + 1
。nums[mid] > target
,说明目标在左侧,更新 right = mid - 1
。-1
表示目标不存在。