字节跳动_日常实习
一面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) 回帖