字节跳动_日常实习
一面2020/12/20/14：00-14：50
- 自我介绍（2分钟）
- 你说你读过 redis 源码，那说一下常用的数据结构：字符串、跳表、字典、压缩列表、链表
- 介绍一下跳表：它在初始化的时候会分配一个头，它也是和链表一样链起来一个表嘛，它会给每个节点随机分配一个层，然后它从它的头部给每个节点进行每一层的连接，它的层数越高，它就会直接连到后面去，中间低的层就不连了，包括它的遍历也是一样，从高到低来找哪个数，这样它就可以跳着遍历了。
- 查找的时间复杂度是多少：log(n)
- 空间占用呢，相对于链表多了什么：主要是多出了那个层嘛，它每个节点的层数是不一样的，如果层都是1，也就退化成链表了。
- vector push_back 扩容：2倍扩容，实际上可能更复杂一点
- 扩容以后，它的内存地址会变化嘛：会变化。以前的话，它是会把原来的元素重新复制过去，开辟一个新空间，复制过去，再把它之前的空间 free 掉。但是现在的话，是通过移动语义 move 来的
- 说一说 move 语义：相对于以前的复制来说，是把元素复制一遍，再把之前的销毁掉。现在的 move 相当于是把它直接搬走了。也就是，我再想一种说法，也就是延长了它的生命周期，然后把新的指针直到原先的那个位置去，然后把原先的指针赋为空，差不多这样。
- move 底层的实现：emm，我看到了有 static_cast ，但是具体的，没有完全了解过
- 右值引用：把那种临时的变量，或者说马上就要消亡，那个叫将亡值，把它的生命周期给延长，变成左值。
- 什么时候被释放：我的理解是它相当于一个左值了（意思和左值一样）
- 怎么把 vector 里面存数据的所有内存空间都释放掉：先说的 resize ，后面改说是另一个函数，不记得名字了
- 说一下虚函数：子类对父类的函数进行一个重写。
- 举个例子详细说一下吧：举例说了动物（父类）吃东西，其他子类吃的动作不一样。这个时候对吃这个函数使用虚函数。
- 虚函数和函数重写有什么区别呢：（乱七八糟猜了一同）我这样猜的
- 再具体说说：但是我不知道这样猜的对不对
- 那换个问题吧，说说引用和指针：1. 内存占用；2. 初始化；3. 可修改指向
- 还有嘛：没了
- 引用可以销毁嘛：不知道了
- 智能指针了解过嘛，说说怎么实现的：增加了一个引用计数
- 具体说说：不同的智能指针指向同一个对象，有一个指针指向，它的引用计数就+1，最后变为0的时候，它就自动的销毁了。
- 多线程中可以使用智能指针嘛：不同线程里面的智能指针都是指向同一个对象嘛？
- 是的：我觉得应该是适用的吧
- 你不知道是吧，确实是适用的，你是怎么想的呢：它不同的线程是共享资源的吧，所以它们是可以指到同一个对象上的吧
- 会有读写冲突嘛：会有的
- 怎么解决：应该通过加锁来解决
手撕
1. 中序遍历（迭代）
给定二叉树的，构造一个中序遍历的迭代器，对应的功能是返回二叉树上的下一个元素。
class Iterator {
public:
TreeNode* next();
} 1.1 思路讨论（6分钟左右）
- 我：在实现的过程中，需要把中序遍历给记录下来嘛
- 面：你具体说说
- 我：比如说，我在初始化的时候直接把它的中序遍历存在 vector 中，直接用 next 这样来访问
- 面：说说有什么优点和缺点
- 我：优点就是在调用 next 的时候复杂度是 O(1)，缺点就是在初始化的时候要把它完全遍历一遍，空间复杂度是O(n)
- 面：你可以试试其他方法
- 我：是不用额外的空间嘛
- 面：也不是不用，但是比 O(n) 小点，比如 O(logn) 就行了。
- 我：哦哦，那就是用一个栈，记录它balabala....
- 面：那你开始写吧
- 面：你先定义一个TreeNode
- 我：需要定义Tree嘛
- 面：这个不用
- 我：这个需要运行嘛
- 面：先不需要
1.2 代码编写（八分钟左右）
中途
- 面：根节点从构造函数传入
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left, *right;
};
class Iterator {
public:
stack<TreeNode*> s;
Iterator(TreeNode* root) {
// s.push(root);
TreeNode* t = root;
while (t) {
s.push(t);
t = root->left;
}
}
TreeNode* next() {
if (s.empty()) return nullptr; // 面试官后面提醒
TreeNode* ret = s.top();
TreeNode* t = ret;
if (t&&t->right) {
t = t->right;
while (t) {
s.push(t);
t = t->left;
}
} else {
TreeNode* tRight = t;
s.pop();
if (s.empty()) return ret; // 面试官后面提醒
t = s.top();
while (t->right == tRight) {
s.pop();
if (s.empty()) return ret; // 面试官后面提醒
tRight = t;
t = s.top();
}
}
return ret;
}
} 1.3 代码解释（4分钟）
写完之后，让我解释代码，并指出几个没有加特殊情况的位置。
2. 全排列
给定一个数组，打印它的全排列 [1,2] -> [1,2] [2,1]
2.1 说思路（2分钟）
- 面：说不太清，你觉得没问题就直接写吧
2.2 代码（7分钟）
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> ans;
void sol(vector<int>& v, vector<int> ret, vector<bool> flag) {
if (ret.size() == v.size()) ans.push_back(ret);
for (int i = 0; i < v.size(); ++ i) {
if (flag[i]) {
ret.push_back(v[i]);
flag[i] = false;
sol(v, ret, flag);
flag[i] = true;
ret.pop_back();
}
}
}
int main() {
vector<int> v;
for (int i = 1; i <= 3; ++ i)
v.push_back(i);
vector<int> ret;
vector<bool> flag(v.size(), true);
sol(v, ret, flag);
for (int i = 0; i < ans.size(); ++ i) {
for (int j = 0; j < ans[i].size(); ++ j)
cout << ans[i][j] << ' ';
cout << endl;
}
} 反问
- 我：你觉得我还有什么需要加强的地方嘛
- 面：你的广度还行，但是深度不够，比如虚函数和智能指针
二面2020/12/21/14：05-15：05
- 自我介绍
- 简历有写c++，接受其他语言嘛：具体什么语言
- golang，python：可以接受，只是偏向c++
- 实习时间：没有其他问题，可以实习到转正
- 说明转正时间（提醒我时间很长）：没特殊情况，希望实习到转正
- base上海？：是的
- 阐述实习的工作（3分钟）
- 说说进程、线程、协程：说了进程是资源调度单位，线程是cpu调度单位，协程有个通道可以传输数据。粒度上：进程 > 线程 > 协程
- 可以试着说说它们的优缺点：进程切换的缺点，时间开销；其他的我可能不太了解，就说这么多吧
- 说说进程、线程的通信：进程：通道（口误把管道说成了通道。。）、信号，socket也算吧；线程用信号比较多吧。
算法题
- 说一说lru，缓存大小为K，怎么设计数据结构：用链表保存缓存数据，说了访问的过程；继续说链表查找上的缺点，时间复杂度为O(n)，所以用哈希来查找，时间复杂度可以降为O(1)。（2分钟）
- 如果加上过期时间呢：在链表节点中加一个更新时间，在访问数据的时候，判断一下时间有没有过期，就行了吧。（3分钟）
- 写一下吧：
- （刚开始的时候自己实现的 list 来写的，挺麻烦的，我突然反应过来之前是用stl的。这时候已经过了15分钟）我：我可以改成用stl么。。。。
- 面：可以的，你改
- （15分钟后，写完了）
#include <iostream>
#include <unordered_map>
#include <list>
#include <pair>
using namespace std;
struct ListNode {
int val;
ListNode* next, *pri;
double update;
};
class lru {
// ListNode* head, *tail;
list<pair<int, double>> l;
unordered_map<int, list<pair<int, double>>::iterator > m;
int K;
int nums;
double T;
lru(int k, double t) {
K = k;
nums = 0;
T = t;
}
void set(int x) {
if (m.find(x) == m.end()) {
auto p = make_pair(x, time());
l.push_back(p);
m[x] = l.rbegin();
nums ++;
} else {
auto p = m[x];
p->first = x;
p->second = time();
l.erase(p);
l.push_back(*p);
m[x] = l.rbegin();
}
if (nums > K) {
l.pop_front();
nums --;
}
}
int get(int x) {
if (m.find(x) == m.end()) {
return 0;
} else {
auto p = m[x];
if (time() - p->second >= T) {
m.erase(x);
l.erase(p);
return 0;
} else {
p->second = time();
l.erase(p);
l.push_back(*p);
m[x] = l.rbegin();
return x;
}
}
}
} - 如果是多线程里面会出错嘛：会出错
- 那怎么解决呢：在对数据结构内部进行修改的时候加锁
- 具体点：
// 这里加写锁 l.erase(p); l.push_back(*p); m[x] = l.rbegin();
- mysql 的索引数据结构：B+树
- 说说为什么用 B+ 树：说了范围查找的优点
- 说说 git merge 和 git rebase 哪个好：rebase
- 说说有什么优点：不太清楚
反问
- 看源码和做项目，从面试和自我提升的角度哪个更好：都很重要。后者重要一点
- 面的哪个组：广告创意
- 面试官介绍了4分钟：感觉还挺有意思的
三面2020/12/24/14：00-14：55
- 自我介绍（2分钟）
- 实习介绍（12分钟）
- redis常用数据结构：字符串、字典、链表、跳表、压缩列表、集合、有序集合
- 有序集合的实现方式：跳表和压缩列表
- 具体说说：压缩列表用于数据量小的情况，存储方式是线性的；数据量大的时候会自动转换为跳表，跳表和链表一样，由一个一个节点链起来，但是它的节点和链表不一样，它的节点会被随机分配一个层数，相同的层数链接起来。
- 跳表查询的时间复杂度：log(n)
- 有序集合中有查询时间复杂度为O(1)的实现吗：有序集合应该是没有的。
- redis 的过期策略：有好几种吧，常见的lru
- 不是说这种，redis里面不是有好多不同的键、值，它们的过期策略：哦，在时间事件里面，会对过期的东西直接删掉。另外，访问到的时候，如果它过期了，也会进行删除
- 之前用的数据库是什么：mysql
- 引擎是什么：innodb
- 隔离级别是：可重复读
- 怎么实现的可重复读：MVCC
- 使用的乐观锁还是悲观锁：乐观锁
- MVCC的实现：增加了版本号，有个版本链，每次事务开始的时候有一个快照，其他事务读取的时候，读取那个快照。事务内部修改的时候有一个日志，日志会记录事务内部对这一行的修改，会用于事务的回滚。
- binlog、redolog(也可能是undo log)听说过吗：听说过，但是没深入了解过
- innodb的索引数据结构是什么：B+树
- 主键和非主键的索引呢：它一开始只会对主键建索引吧
- 非主键呢：不清楚
- B+树的叶子节点存放的什么：整体的数据，包括索引，都在里面
- 浏览器输入一个url，返回了一个error，怎么找出错的地方：通过状态码
- 没有状态码，只有一个error：啥都没有吗。。。
- dns的返回标志：那可能是dns上的错误，可能不存在这个域名
- 但是我输入的toutiao.com，我知道是存在的：是的。那可能是dns查询的时候出现了错误，那可以一步一步的查，它刚出去的时候访问的那个dns服务器（应该都是有的，小声bb）。可能最近的那个路由器或者电脑里面没有配dns。有没有可能（强颜欢笑）
- 你怎么知道最近的呢：查询dns的路径，好像是有一个命令的
- 什么命令呢：这命令名字我不记得了。。。
- linux怎么查看系统的状态呢：top
- top出来显示什么：cpu占用率，内存占用率、一些进程的信息
- 实习中，python后端，是怎么实现的http连接，是django吗：emm，是通过webpy的api直接调用的。。。。
- 你的request，post，具体实现是什么：emmm，我可以从c++方面来说吗
- 嗯：它要创建一个套接字，给套接字分配一个端口，等待连接的到来，连接来了之后，像redis的话，它收到连接，会复制一个socket，分配一个新端口，把这个连接分配给新socket，原先的socket继续listen。连接之后，读取socket里面缓冲区的内容，再内部进行处理，再通过socket传输出去。
- socket监听是哪个层：tcp
- 之前问的是http，这方面是不是不太了解：嗯
- 你还有什么领域没问你的吗：操作系统，计算机网络，你们应该用golang，python比较多吧
- 也有用c++的：那还有c++这些，了解的多一些
- 段页式存储执行的时候会访问几次内存：访问内存会通过页的级数也有关系，如果它是一级页表的话，它取页号一次，取物理地址一次，如果没有在内存中的话，还会访问磁盘
- 我问的段页式：段页式先取它的段内偏移量，然后再访问物理地址，是两次
- 进程的存储分布：栈、堆、数据区、代码区、共享库
- 代码放在哪：代码区
- 变量放在哪：静态变量放在静态的变量区，局部变量会放在栈中
- 指针呢：指针也是有静态的吧（小声（不确定）），直接声明的会放在栈中
- 指针指向的地址分配的空间呢，malloc的：放在堆中
算法
做题吧，我先看看你之前做的什么题
求s1中包含s2中字符（不用考虑顺序）的最小子串（长度最小） s1 = "abcedeabd" s2 = "abe"
思路
滑动窗口：
可以先找到第一个包含s2字符的字串，比如例子中的abce，然后往右移，把a提出去，找到右边第一个提出去的a，这就是下一个子串。把所有子串找出来，再找最短的。
面：你这个会有问题，你先写代码吧。
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
using namespace std;
int main() {
unordered_map<char, int> um1, um2;
unordered_set<char> us;
string s1 = "abcedeabd";
string s2 = "abe";
vector<string> ans;
int left, right;
left = right = 0;
int sum = 0;
for (int i = 0; i < s2.length(); ++ i) {
us.insert(s2[i]);
um1[s2[i]] ++;
sum ++;
}
string s;
um2 = um1;
int i = 0;
while (i < s1.length() && um2[s1[i]] == 0)
i ++;
while (sum > 0) {
if (um2[s1[i]]) {
um2[s1[i]] --;
sum --;
}
s += s1[i];
i ++;
}
ans.push_back(s);
for (; i < s1.length(); ++ i) {
char ch = s[0];
int cnt = 1;
// 找到截取的地方
if (um1[s[0]] == 1) {
while (us.find(s[cnt]) == us.end()) {
// TODO
}
}
while (s[cnt] )
s = s.strsub(1, s.length() -1);
while ()
if (sum == 0){
ans.push_back(s);
um2 = um1;
}
}
cout << "Hello World!" << endl;
} （17分钟后）
面：没什么时间了，说说代码吧
我：（对着代码）先找到第一个符合条件的子串，然后移除掉第一个字符s[0]，这里需要把s中，非s2字符的其他字符也移除掉，这里就有问题了，如果后面的s[cnt]（已经是s[cnt] in s2了），正好是移除掉的s[0]，这里有两种情况，如果s2中只有一个s[0]，那么这个时候right不用右移，如果s2有多个s[0]，则与其他字符做同样的处理。感觉后面还有挺多要写的。。。
面：还有更好的解法，你可以之后去想一想。
反问
问：推荐一本书
面：这种主观的推荐我们是规定不能说的哈
问：上下班时间
面：10105.5，你们应该都知道
我：不同组也有差异吧哈哈
面：那你想要多呢还是少呢（笑）
以上都是面试过程中的回答，没有加其他东西，也没有修改错误，有错误的地方欢迎大家纠正！
对了，大部分的冒号，左边是面试官，右边是我的回答。
三面没过，换了个组继续加面两轮，会继续在本贴更新。
算法题：
lc 94. 二叉树的中序遍历
lc 46. 全排列
lc 47. 全排列 II
lc 146. LRU 缓存机制
lc 76. 最小覆盖子串
2020/12/28 更新
加面一
自我介绍
实习介绍
- 怎么实现版本管理
直接开始做题吧
描述信息
已知一天内用户登录登出的日志（数据量较大），求这一天用户在线的最大峰值和持续时间段日志包含字段（userid, login_time, logout_time）
登录登出时间精确到秒
我：如果抛弃数据量比较大的条件的话，我是这样想的，先给他排序，按
login_time顺序。有以下三种情况
。。。。。。 //峰值的区间
。。。。。。。
》》
。。。。
。。。。。。
。。。
》》
。。。
。。。。。。
。。。。。。
》》
。。。。。。 我：你觉得我说的这种方法是可行的吗？
面：其实我没太听懂，用伪代码写写吧
#include <iostream>
using namespace std;
int main() {
pair<int, int> ans1;
int ans2;
pair<int, int> p;
int nums;
p = 第一条日志
nums = 1;
for (每一条日志 i ) {
if (i.login_time < p.second && i.logout_time > p.second) {
p.first = i.login_time;
nums ++;
} else if (i.logout_time < p.second) {
p.first = i.login_time;
p.second = i.logout_time;
nums ++;
} else if (i.login_time > p.second) {
if (nums > ans2) {
ans1 = p;
ans2 = nums;
}
pair<int, int> t = i;
// 下面这个循环是写完之后自己看出来要加的
while (t.second < i.first) {
// second 不是有序的
// 这里会需要把之前的全循环一遍，复杂度很高
// 这里是有问题的
t 向前遍历
}
p = i;
}
}
} 我：解释代码思路，说到上面的注释之后，说这思路是有问题的。重新想思路
（3分钟后）我：给点提示吧。。。
面：你得反过来想这个，这里的时间是一天
我：按小时分桶，统计一个小时里面的包含的人
面：不用按小时，按秒也行
我：哦哦，以秒分桶，这个桶是可以放进内存的，哦没问题了，那一个日志的登入登出时间差会有可能小于1秒吗
面：不会呀，时间最小就是秒
我：哦~那就是变成了一个8w+的数组，粒度是这么多，就是直接求它们的最大值就行了。哦通过这个条件去思考这个处理的方法。
再来个题吧
条件：
1.64匹马
2.8个赛道
3.每次比赛只能知道比赛结果名次，不能知道具体时间
求：
用最少的比赛次数，找出最快的4匹（这个我就不记录面试过程了，直接放一张图吧）
redis 的数据结构：（同上）
szet 的实现：（同上）
跳表：（同上）
redis 的分布式：主从复制和哨兵模式。
怎么扩容：不清楚
一致性哈希知道吗：没了解过
redis 分布式锁用过吗：没用过
死锁的条件：
如何避免死锁：
反问：
- 部门和组：素材优化
- 具体做什么呢
- 技术栈：go，python，c++
- 组里多少人
2020.12.29 更新
已挂
全部评论
(12) 回帖