拓蛮八方(2022.07.16)
算法题:10辆一模一样的小车,油箱最多装10升油,最多跑10公里。如何使得其中一辆小车跑出最大距离。例如:A车和B车同跑5公里,然后A车把剩下的油给B车加满,这样B车可以跑15公里。
- Python迭代器,生成器
- Python多进程,多线程,协程
- Python list,append复杂度,remove复杂度
- 快排思想,最坏,如何改进
-
首先,清楚快排原理的同志都知道,快排特别热衷于凌乱的数据,最好情况下时间复杂度能达到O(nlogn),空间复杂度为O(logn);但是对于基本有序或者倒序的数据则无能为力,时间复杂度直接降到O(n^2),空间复杂度为O( n ) 。对于这种情况,取一个合理的基准值就很重要了。
一种较为稳妥的方法是随机选取数组中的某个位置,而不是总是顽固地选择最右端的元素,这样确实可以避免排序的退化。
再回想我们为什么要取随机值?就是为了避免输入数据有序造成的异常,如果一种方法能够在这种情况下利用这种原有的有序性岂不是更好吗?三值取中法就是这样的方法,它的选取方法是先从数组的开头、结尾和中间选取3个元素,再取这3个元素的中间值作为划分的基准。首先,三值取中法本身带有一定的随机性,所以能够很好的处理随机数据;其次,它使得最坏情况几乎不可能发生,如果数组原本就具有有序性,那么按照原始的划分方法,取到的3个元素中必然有2个将被划分到大于(或小于)v的值所在的数组中,而三值取中法则扭转了这种不利;最后,与随机化方法相比,三值取中法省去了生成随机数的开销。
-
其次,在快速排序算法的递归实现中,存在一种不太好的现象:随着递归层层深入,大量数据被分割成了小数组;快排对于大数组的划分可以迅速地将元素移动到它正确位置的附近,比如说对1024进行一次均等划分,那么某个元素可能会移动数百个单位位置,若进行4次均等划分,元素在正确位置上的概率就从1/1024骤升到1/64,考虑到64与1024的绝对数值,这是相当高的效率;然而对于小数组,快速排序的效率就不那么理想了,对于16个元素的数组,快速排序也要划分4次才能把它移动到正确的位置上,相对于之前几百个位置的移动,小数组排序一次只能移动几个单位的位置。
换句话说,快速排序对少量数据的划分远不如它对大量数据的划分这么划算,当排序进入到小数组阶段后,它将多次因为这些小数组而频繁调用自身,但获得的收益并不大,我姑且把这种现象叫做小数组的边际效益。采取分治递归策略的排序算法(如归并排序)都存在同样的问题,所以这类排序都可以在这方面优化。对大量数据排序时,我们应该在前期利用快速排序的特点,让这些数据迅速移动到正确位置附近,然后在后期消除小数组的边际效应。
消除边际效应的一个方法就是设定一个M值,当数组元素个数小于M时,视为小数组,此时快速排序就直接返回,最后把数组处理得差不多时,再用其它排序方法对数组进行最终排序。那么M值应该取多少?又应该选择何种排序算法进行最终排序?
首先回答第二个问题,因为它的答案是显而易见的。对接近有序的数据排序,没有什么算法比插入排序更合适了,插入排序的执行开销与所有元素偏离自己正确位置的距离成正比。
Cf. https://blog.csdn.net/u013257679/article/details/79633299 and here
-
- 数据库,内存数据库,redis
- Linux中如何实现一个timer
- 一个大文件(10GB+),如何获取其中指定行数的数据
- TCP的保序性,快速重传,拥塞控制
- UDP和TCP的区别,如何实现可靠的TCP
- HTTP的报文格式
- 平时开发中有没有遇到进程阻塞,孤儿进程,内存泄漏
- 死锁的形成
蒙玺投资(2022.07.22)
- std::atomic使用场景(多读一写)
- linux STL 标准库容器的内存分配策略
- map和unordered_map的区别
- python如何提高并发量,多线程怎么管理
二面(2022.07.26)
sizeof(std::vector)是多少- 工作中有没有用到过将c++的一块内存交给python层管理的情况?
- 在一台CPU负载很高的机器上,优先使用互斥锁还是自旋锁?
- 当一个线程没有拿到互斥锁,他什么时候会再去尝试拿锁?
- 死锁是什么,怎么形成的?
- 如何避免,解决死锁问题?(破除循环等待?)
- 你提到了条件变量,条件变量的典型使用场景是什么?
- 常用的原子操作有哪些?
sizeof(int)和sizeof(std::atomic<int>)分别是多少?- TCP拆包,粘包有了解吗?
class Base {
public:
virtual ~Base() {}
};
class Derived : public Base {
public:
virtual ~Derived() {}
};
// 1
sizeof(Base) = ?
sizeof(Derived) = ?Base* p = xx;
p->virutal_mfunc();
/**
* 这样调用虚函数成员,会根据具体对象类型,查找vtbl进而调用各自的成员。
* 当p指向基类对象时,和指向派生类对象时,这样的调用在时间和空间复杂度
* 方面有什么区别?
*/以下是map和unordered_map的定义
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T> >
> class map;- 为什么unordered_map模板特化既需要传
Hash,有需要传KeyEqual - 为什么map模板不需要
KeyEqual?
test
#include <vector>
#include <stdio.h>
#include <stdint.h>
#include <typeinfo>
#include <cstring>
#include <atomic>
using namespace std;
#define PRINT_FUNC(tag) do { \
if (strlen(tag) > 0) { \
printf("__%s__", tag); \
} \
printf("call %s\n", __func__); } while (0)
class Base {
public:
inline virtual ~Base() { PRINT_FUNC(""); }
};
class Derived : public Base
{
public:
virtual ~Derived() override { PRINT_FUNC("dd"); }
};
template<typename T>
void PrintSize(T /* t */)
{
printf("the size of %s is %lu\n", typeid(T).name(), sizeof(T));
}
int main()
{
printf("size of vector is %lu\n", sizeof(vector<int>));
vector<uint32_t> a;
printf("a.size=%lu, a.capacity=%lu\n", a.size(), a.capacity());
PrintSize(vector<int>());
PrintSize(Base());
PrintSize(Derived());
printf("size of atomic int is %lu\n", sizeof(atomic<uint32_t>));
uint32_t u = 0;
PrintSize(u);
return 0;
}输出
size of vector is 24
a.size=0, a.capacity=0
the size of St6vectorIiSaIiEE is 24
the size of 4Base is 8
call ~Base
the size of 7Derived is 8
__dd__call ~Derived
call ~Base
size of atomic int is 4
the size of j is 4
see also 202604161330cpp中stl_list的size
砺算科技(2022.08.04)
两个面试官依次上阵,以下问题汇总在一起。
- 描述工作中遇到过的一个bug
- 说说python中赋值、浅拷贝、深拷贝的区别(一直在问我自己的理解,不知道想问啥)
- 说说进程和线程之间的区别
- 在x86平台机器上(32位),一个进程的虚拟地址空间有多大?
- 说说虚函数
- 纯虚函数呢?
- 平时有用过gdb吗
- 一个函数A调另一个函数B,要在B中开辟一块内存,如何在A中拿到指向这块内存的指针?
- 函数B return这个指针
- 函数A中定义一个指针变量,以引用或地址(二级指针)的方式传给函数B,在B中给这个指针赋值
- 说说内联函数的作用
- 函数调用有什么开销?
- 压栈都会压些什么东西?
- 说说动态链接库和静态链接库的区别,优缺点?
- 手写代码:合并两个升序链表,使其仍保持升序。循环+递归写法(循环写失败了QAQ)
- 说说重载,重写,覆盖三者的区别
- 说说模板工作的机制?
- 每个特化的模板都会生成一份独立的代码,根据模板参数类型调用对应的版本。
- 我们知道频繁创建,销毁小对象会造成内存碎片。如何通过预先申请一片连续的内存,然后控制这些小对象的创建和销毁都在这块内存上?
- 回答了对象池,但又问:如果这些小对象中可能会申请新内存,如何确保这些能够受控制,通过constructor和destructor构造和析构对象,但不发生内存申请和释放,而是利用那一块预先申请好的内存。(答不上来)
- 说说宏和constant区别
玄信资产(2022.12.01)
- 自我介绍
- 手写一个vector类,实现push_back, pop_back方法
- 必须使用模板写
- 考虑模板参数为指针类型
- 考虑模板参数为自己(你正在写的这个vector类)
- 实现默认构造函数,拷贝构造函数,移动构造函数,析构函数
- 手写一个PriorityQueue,可以使用std::vector(不会)
- 给定三个整数:a, b, n;求第n个能被a或b整除的数。例如a=2,b=4,n=2,则第一个被a或b整除的是2,第二个被a或b整除的是4,所以结果为4.
- 说了暴力求解(这个区间内一定含有至少n个被a或被b整除的数,排个序,取第n个),人家说不行
- 要了个提示,人家说这是个数学题
- 又要了个提示:不能暴力求解(),那往下的复杂度只有()了呀
- 又问了是什么算法:不就只有二分法么
- 终于在沟通之中得到答案,但这题已经失败了
- 方案:取a、b的最小公倍数记为c,则之间至少存在n个被a或b整除的数。向下折半取整,算出之间有多少个被a或b整除的数:
- 可得有这么多被a整除的数,
- 可得有这么多被b整除的数,
- 可得有这么多被a和b同时整除的数,
- 因此,区间共有个被a或b整除的数
- 判断其与n的关系,如果比n大,向左搜索,反之向右搜索
- 给定一棵二叉搜索树,以及一个vector,批量搜索vector中的值,返回搜到的节点指针列表。(搜单个,遍历,如何优化)
芯华章(2022.12.12)
- 算法题:求top k大的数?(当时知道求第k大的数,但不知道怎么求前k大的数。查询之后发现思路是一样的,用快排的分割法,如果pivot的索引恰好是k,则k之前的恰好就是前k小的数。如果比k大,则在左边继续分割;如果比k小,则在右边继续分割。如是直到找出索引为k的pivot,即可得到前k小的数,自然得到前n-k大的数。)
- 变通问法,如果序列长度超过内存可读取的上限,应该如何?(等于在前面的基础上加了个限制,没法读完整个序列。此时可以利用小顶堆「注意是小顶堆」来处理。先读出k个元素,建立一个大小为k的小顶堆,再依次读这个序列,如果读出来的数a大于堆顶元素b,则丢弃堆顶元素,a入堆。这样,不用一次读完所有数据,但在遍历完之后,留下的也就是前k大的数了。)
- std::vector的push_back和emplace_back的区别?
- 是否任何场景下都偏向于用emplace_back?(答到对于POD类型,可能用push_back更好,但也没有实测过性能开销;面试官指导:当empalce_back一个临时对象,这个对象内部有个指针,管理了一块内存,如果用emplace_back,但vector扩容失败,比如内存满了,此时临时对象的布道析构)
- c++11中一般如何创建一个线程?
- 传给线程的方法,如果需要传参,对参数有什么要求吗?(答到了参数的生命周期必须维持到线程结束)
- 如果没法保证传的参数生命周期大于线程本身,比如传了一个引用,编译器会报错吗?
- shared_ptr和auto_ptr的区别?
- 多线程中对shared_ptr的操作需要加锁吗?(=shared_ptr是线程安全的吗?)
- 仅引用计数更新线程安全
- 读写指向的对象,非线程安全
- 直接修改shared_ptr本身的指向,非线程安全
- tcp的三次握手
- tcp连接是通过调用什么系统API实现的?(答到client: connect, server: listen)
- 连接断开呢是通过什么系统调用?
- 对于server,如何得知一个包是申请断开连接的包呢?(答到了tpc的包头,人家说这个实在协议层,应用层如何区分呢)
二面(2022.12.15)
- 手写vector的insert,erase
H3C
主管面(2023.02.04)
- 一致性哈希:假如hash有10个桶,分别位于不同的设备上。现在有一个设备坏了,如何将坏掉的桶里的数据迁移至其他9个(或9个当中的几个)桶中,而不影响好数据(即,如果hash到另外9个桶,照样可以取到正确的数据)?
- 说一下工作中遇到的难题,如何解决的。
- 设想一个场景,一个进程误写了一段内存,但没造成crash,也就是说这个进程现在带病运行。之后某个进程,读取这段内存中错误的数据,引发段错误。如何定位是哪个进程写坏了这段内存?不会;
- 对linux了解到什么程度?知道linux的进程管理,内核调度吗?
- B树和跳表的区别,各自有何优缺点?
中电28所(2023.03.03)
- 说说内存泄漏,如何定位,如何产生,如何避免?
- 堆踩踏、堆溢出
- map和unordered_map
- c++11的新特性
- linux find命令
- linux运行程序是,如何链接动态库?
- 介绍下无锁队列
小米汽车(2024.9.19)
算法题(leetcode 110):从数组构建二叉树,并判断是否为平衡二叉树(此处平衡是指任意一个节点,其左右子树高度差不超过1)
时间太紧,从数组构建二叉树,利用一个队列即可;判断是否平衡使用暴力求法,不太行
// Build binary tree from an array.
TreeNode* build_binary_tree(const vector<int>& arr)
{
if (arr.empty()) return nullptr;
auto root = new TreeNode(arr[0]);
queue<TreeNode*> ptr_q;
ptr_q.push(root);
for (int i = 1; !ptr_q.empty() && i < arr.size(); i += 2)
{
auto p = ptr_q.front();
ptr_q.pop();
if (arr[i] != -1)
{
p->left = new TreeNode(arr[i]);
ptr_q.push(p->left);
}
if (i + 1 < arr.size() && arr[i+1] != -1)
{
p->right = new TreeNode(arr[i+1]);
ptr_q.push(p->right);
}
}
return root;
}
int calc_tree_height(TreeNode* root)
{
if (!root) return 0;
int lh = calc_tree_height(root->left);
int rh = calc_tree_height(root->right);
return 1 + std::max(lh, rh);
}
bool is_balanced_tree(TreeNode *root)
{
if (!root) return true;
int lh = calc_tree_height(root->left);
int rh = calc_tree_height(root->right);
if (std::abs(lh - rh) > 1) return false;
return is_balanced_tree(root->left) && is_balanced_tree(root->right);
}以上暴力的原因在于计算高度的函数对于同一个节点会被调用多次(有多少个祖先就调用多少次)。所以可以简单优化一下,采用自底向上的递归。
int judge_tree_height(TreeNode* root)
{
if (!root) return 0;
int lh = judge_tree_height(root->left);
if (lh == -1) return -1;
int rh = judge_tree_height(root->right);
// Note this: when calc tree height, we can do on more thing together
// that is judging the balance of the tree.
if (rh == -1 || std::abs(lh - rh) > 1) return -1;
return 1 + std::max(lh, rh);
}
bool is_balanced_tree_bottom_up(TreeNode* root)
{
return judge_tree_height(root) >= 0;
}AlphaGrep(2026.5.18)
- 了解虚拟内存吗?一个程序能不能申请比物理内存还大的虚拟内存?
- 不了解,不可以。答错!
- 可以申请比物理内存更大的虚拟内存。实际用不上这么多,系统只会把正在用的映射到物理内存。剩下的延后分配,或分配在磁盘上。如果程序确实占用了超过物理内存的量,就会触发磁盘页和内存页的交换,如果程序访问的地址空间在磁盘上,会先卸载一部分内存,读入磁盘上对应的地址空间;后续如果访问卸掉的地址空间,又会触发这样的交换。读内存的速度会显著降低!
- ---分割线---
- AI回答:程序看到的是虚拟地址,不是直接操作物理内存。操作系统会把“正在用”的那部分虚拟页映射到物理内存,把暂时不用的页放到磁盘上的交换区或按需延后分配。所以,一个进程的虚拟地址空间可以很大,但真正占用的物理内存,只是其中当前被访问、被装入的那一部分。
- AI回答:如果程序实际用到的内存持续超过物理内存,系统就会频繁换页,把不常用的页写到磁盘,再把需要的页读回来。这样会明显变慢,严重时会出现卡顿甚至性能崩溃。
- 了解红黑树吗?红黑树和AVL树有何区别?std::map底层结构为什么不用AVL树。
- 不会。据说AVL数增删过程中需要频繁调整以维持AVL属性,反之红黑树就还好。而AVL树仅仅比红黑树查找效率在概率上高那么一点。因为AVL树比红黑树更平衡。
- 说说堆排序?
- 强制类型转换有哪些?什么时候用 static_cast?static_cast有没有运行时检查?dynamic_cast呢?
- 什么时候用static_case?
- 基本类型转换(int、float、double等等)
- 枚举和整数之间
- 派生类转基类(指针,引用)
- void* 转具体指针
- static_cast用于编译期就能确定、逻辑上合理的类型转换。不做运行时检查。
- dynamic_cast用于基类向派生类转换,会做运行时检查。转换失败返回空指针。
- 什么时候用static_case?
- new做了什么?如果有一块申请好的内存,如何在上面创建自己的对象?
- 回答申请内存+调用构造函数。
- see also 202605181622placement-new
- 了解共享内存吗?
- 不太了解。
- AI回答:每个进程都有自己的虚拟地址空间,默认情况下,同一个虚拟地址在不同进程里可能对应不同的物理地址。共享内存做的事情,就是通过内核把某段虚拟地址和同一组物理页关联起来,让进程 A 和进程 B “看见”的是同一块内存。
- 什么是完美转发?完美转发的实现原理是什么?
- 答到了
std::forward以及完美转发的作用。看我提到了模板,面试官给我挖坑,反问我“只有模板函数能用完美转发吗?普通函数可不可以?”我被他语气唬住了,答了可以。而事实上**完美转发是一种模板技术**!所以普通函数不存在完美转发一说。
- 答到了
- 基类和派生类是否共享虚表。
- 答共享。实际是不共享!不同的类有不同的布局,要是共享就太复杂了。但是类的所有对象共享虚表,对象持有虚指针,指向类的虚表。
- 构造函数可以是虚函数吗?析构函数呢? — cpp-learn, 多态
- 给你一个tcp连接,如何尽量让它延迟更低?
- const 和 constexpr 的区别,constexpr 能修饰函数吗?
- 代码考察:手写一个std::shared_ptr
下面代码输出什么?
int b = 10;
if (fork()==0)
b = b + 5;
else
b = b - 5;
cout << b << ':' << &b << endl;- 我以为fork成功输出0,答15,错!
- fork返回子进程pid,在子进程中返回0.
- 搜索得知,这是fork的经典场景,fork之后,父子进程同时执行fork返回后往下的代码。
- 所以输出两次,一次是父进程打印,一次是子进程打印。顺序不定,但地址一样,因为fork复制了父进程的状态。而不同进程之间有独立的状态。
- 样例输出:
5:0x7fff0f609504
15:0x7fff0f609504
下面代码有何问题?
template<typename T>
class A {
public:
using type = T;
type var1;
A(type var1): var1(var1) {}
virtual void print() {
cout << "A:print" << var1 << endl;
}
};
template<typename T>
class B: public A<T> {
public:
using Base = A<T>;
Base::type var2; // #1
B(T var1, T var2): Base(var1), var2(var2) {}
void print() {
cout << "B:print" << var1 << endl; // #2
}
};
int main() {
B<int> b(10, 20);
b.print();
return 0;
}- 我是真没看出问题!还是模板写少了唉。
- 第一处,
Base::type需要加类型限定词typename修饰,即typename Base::type var2.- 在模板里,凡是依赖模板参数的名字,都叫依赖名。其特点是模板定义阶段不能完全确定含义,必须等实例化阶段再决定。
- 依赖名作为类型时,必须使用
typename修饰,告诉编译期按照一个类型的规则去处理它。 T::value_type x;→typename T::value_type x;
- 第二处,var1会报错找不到。
- 在普通继承里,基类是确定的,编译器在编译派生类时就能把基类成员一起看清楚。但在模板继承里,基类
A<T>依赖于模板参数T,在模板还没实例化之前,编译器并不知道A<T>具体长什么样,所以不会把它里面的成员都提前纳入未限定名查找。可改为Base::var1或this->var1。
- 在普通继承里,基类是确定的,编译器在编译派生类时就能把基类成员一起看清楚。但在模板继承里,基类
芯行纪(2026/06/25)
两个面时官,一个看着很实在,一个很亲和。感觉团队氛围应该不错。主要是挑着简历上的内容问。
- 如何杀死一个僵尸进程?答错,当时和孤儿进程有点搞混了。
- 僵尸进程是指进程本身已经运行结束,不占用系统资源(CPU/内存),但没有被父进程正确处理1。从而导致它一直占着一个进程号。由于进程号资源是有限的,极限情况下,可能导致新的进程创建失败(没有可分配的进程号)。
- 僵尸进程会占用进程表表项,和少量内核信息。
- 如何杀死呢?答案是要杀掉他的父进程,通过 ps/top 查找僵尸进程,ps 会显示
<defunct>表示进程已经失效;top 会显示进程状态为Z/Z+. 然后进一步查找父进程 pid(对应子进程条目的 ppid 那一栏)。kill 掉父进程,僵尸进程才会被杀死2。 - 好奇的你可能会问了,那如果父进程先被杀了,子进程后运行结束,是否会成为僵尸进程呢?
- 不会。因为父进程先死了,子进程会被进程号为 1 的 init 进程接管,由它来负责子进程的残留信息回收。顺便说下,这时候的子进程就叫做孤儿进程。
- vector扩容机制,如何减少扩容次数。
- 如果无需随机访问,数据量也不大的情况,请问选用什么数据结构?没太懂问的意图,答了vector。
- 如何在一个目录下所有文件中查找给定字符串?grep -r
- std::list如何获取链表长度?答了成员函数size()
- 这个函数时间复杂度多少?答了O(1),但不太确定,如何增删时维护了size,就是O(1),否则O(n)。实际上确实是在增删节点时维护了头节点记录的size
- list只有head存了size吗?是的,参考202604161330cpp中stl_list的size
- shell脚本写过吗?说说常用的linux命令?
- python和c++有何区别?解释型和编译型
- python有没有预生成的代码?答了有
- AI回答:
- 当你运行一个
.py文件时,大致会经历三步:- 解析源码,生成抽象语法树(AST)。
- 编译 AST,生成 字节码(bytecode)。
- 由 Python 虚拟机(解释器)逐条执行字节码。
- 其中第 2 步就是“预生成代码”的环节:把源码编译成字节码。
- 为了避免每次运行都重新编译,Python 会把字节码缓存到磁盘上:
- 在模块第一次被导入时,会在同级目录下的
__pycache__文件夹中生成一个.pyc文件。 - 下次再导入这个模块时,如果:
- 源码没变,
- Python 版本匹配,
- 就可以直接加载
.pyc,跳过“解析+编译”的步骤,加快启动/导入速度。
- 在模块第一次被导入时,会在同级目录下的
- 仍然是解释执行吗?
- 是的,
.pyc只是 Python 字节码,不是 CPU 直接执行的本地机器码:.pyc只是让“编译这一步”提前或缓存下来。- 运行时依然需要 Python 解释器读取字节码并解释执行。
- 是的,
- map查询复杂度?答了O(log n)和底层红黑树实现
- map插入元素会导致什么?答了维护红黑树性质,但具体细节著清楚
- unordered_map查询复杂度?插入元素和map有何区别?
- hash值算出来之后,怎么知道对应的bucket在哪里?怎么知道数据存哪里?没答上来
- unordered_map算出hash值后,一般通过取余(不同平台、不同编译期可能有差异)的方式确定bucket索引。言外之意就是底层的存储桶还是用一个顺序容器存的,类似于一个
vector<bucket>, hash完了之后对桶个数取模。
- unordered_map算出hash值后,一般通过取余(不同平台、不同编译期可能有差异)的方式确定bucket索引。言外之意就是底层的存储桶还是用一个顺序容器存的,类似于一个
- stl泛型算法用过哪些?std::remove用过吗?
see also 校招经历