首页 > 字节广告日常实习一面/二面/三面/加面1(凉)
头像
叮当201809270912458
编辑于 2020-12-29 12:58
+ 关注

字节广告日常实习一面/二面/三面/加面1(凉)

字节跳动_日常实习

一面2020/12/20/14:00-14:50

  1. 自我介绍(2分钟)
  2. 你说你读过 redis 源码,那说一下常用的数据结构:字符串、跳表、字典、压缩列表、链表
  3. 介绍一下跳表:它在初始化的时候会分配一个头,它也是和链表一样链起来一个表嘛,它会给每个节点随机分配一个层,然后它从它的头部给每个节点进行每一层的连接,它的层数越高,它就会直接连到后面去,中间低的层就不连了,包括它的遍历也是一样,从高到低来找哪个数,这样它就可以跳着遍历了。
  4. 查找的时间复杂度是多少:log(n)
  5. 空间占用呢,相对于链表多了什么:主要是多出了那个层嘛,它每个节点的层数是不一样的,如果层都是1,也就退化成链表了。
  6. vector push_back 扩容:2倍扩容,实际上可能更复杂一点
  7. 扩容以后,它的内存地址会变化嘛:会变化。以前的话,它是会把原来的元素重新复制过去,开辟一个新空间,复制过去,再把它之前的空间 free 掉。但是现在的话,是通过移动语义 move 来的
  8. 说一说 move 语义:相对于以前的复制来说,是把元素复制一遍,再把之前的销毁掉。现在的 move 相当于是把它直接搬走了。也就是,我再想一种说法,也就是延长了它的生命周期,然后把新的指针直到原先的那个位置去,然后把原先的指针赋为空,差不多这样。
  9. move 底层的实现:emm,我看到了有 static_cast ,但是具体的,没有完全了解过
  10. 右值引用:把那种临时的变量,或者说马上就要消亡,那个叫将亡值,把它的生命周期给延长,变成左值。
  11. 什么时候被释放:我的理解是它相当于一个左值了(意思和左值一样)
  12. 怎么把 vector 里面存数据的所有内存空间都释放掉:先说的 resize ,后面改说是另一个函数,不记得名字了
  13. 说一下虚函数:子类对父类的函数进行一个重写。
  14. 举个例子详细说一下吧:举例说了动物(父类)吃东西,其他子类吃的动作不一样。这个时候对吃这个函数使用虚函数。
  15. 虚函数和函数重写有什么区别呢:(乱七八糟猜了一同)我这样猜的
  16. 再具体说说:但是我不知道这样猜的对不对
  17. 那换个问题吧,说说引用和指针:1. 内存占用;2. 初始化;3. 可修改指向
  18. 还有嘛:没了
  19. 引用可以销毁嘛:不知道了
  20. 智能指针了解过嘛,说说怎么实现的:增加了一个引用计数
  21. 具体说说:不同的智能指针指向同一个对象,有一个指针指向,它的引用计数就+1,最后变为0的时候,它就自动的销毁了。
  22. 多线程中可以使用智能指针嘛:不同线程里面的智能指针都是指向同一个对象嘛?
  23. 是的:我觉得应该是适用的吧
  24. 你不知道是吧,确实是适用的,你是怎么想的呢:它不同的线程是共享资源的吧,所以它们是可以指到同一个对象上的吧
  25. 会有读写冲突嘛:会有的
  26. 怎么解决:应该通过加锁来解决

手撕

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

  1. 自我介绍
  2. 简历有写c++,接受其他语言嘛:具体什么语言
  3. golang,python:可以接受,只是偏向c++
  4. 实习时间:没有其他问题,可以实习到转正
  5. 说明转正时间(提醒我时间很长):没特殊情况,希望实习到转正
  6. base上海?:是的
  7. 阐述实习的工作(3分钟)
  8. 说说进程、线程、协程:说了进程是资源调度单位,线程是cpu调度单位,协程有个通道可以传输数据。粒度上:进程 > 线程 > 协程
  9. 可以试着说说它们的优缺点:进程切换的缺点,时间开销;其他的我可能不太了解,就说这么多吧
  10. 说说进程、线程的通信:进程:通道(口误把管道说成了通道。。)、信号,socket也算吧;线程用信号比较多吧。

算法题

  1. 说一说lru,缓存大小为K,怎么设计数据结构:用链表保存缓存数据,说了访问的过程;继续说链表查找上的缺点,时间复杂度为O(n),所以用哈希来查找,时间复杂度可以降为O(1)。(2分钟)
  2. 如果加上过期时间呢:在链表节点中加一个更新时间,在访问数据的时候,判断一下时间有没有过期,就行了吧。(3分钟)
  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;
            }
        }
    }
}
  1. 如果是多线程里面会出错嘛:会出错
  2. 那怎么解决呢:在对数据结构内部进行修改的时候加锁
  3. 具体点:
// 这里加写锁
l.erase(p);
l.push_back(*p);
m[x] = l.rbegin();
  1. mysql 的索引数据结构:B+树
  2. 说说为什么用 B+ 树:说了范围查找的优点
  3. 说说 git merge 和 git rebase 哪个好:rebase
  4. 说说有什么优点:不太清楚

反问

  1. 看源码和做项目,从面试和自我提升的角度哪个更好:都很重要。后者重要一点
  2. 面的哪个组:广告创意
  3. 面试官介绍了4分钟:感觉还挺有意思的

三面2020/12/24/14:00-14:55

  1. 自我介绍(2分钟)
  2. 实习介绍(12分钟)
  3. redis常用数据结构:字符串、字典、链表、跳表、压缩列表、集合、有序集合
  4. 有序集合的实现方式:跳表和压缩列表
  5. 具体说说:压缩列表用于数据量小的情况,存储方式是线性的;数据量大的时候会自动转换为跳表,跳表和链表一样,由一个一个节点链起来,但是它的节点和链表不一样,它的节点会被随机分配一个层数,相同的层数链接起来。
  6. 跳表查询的时间复杂度:log(n)
  7. 有序集合中有查询时间复杂度为O(1)的实现吗:有序集合应该是没有的。
  8. redis 的过期策略:有好几种吧,常见的lru
  9. 不是说这种,redis里面不是有好多不同的键、值,它们的过期策略:哦,在时间事件里面,会对过期的东西直接删掉。另外,访问到的时候,如果它过期了,也会进行删除
  10. 之前用的数据库是什么:mysql
  11. 引擎是什么:innodb
  12. 隔离级别是:可重复读
  13. 怎么实现的可重复读:MVCC
  14. 使用的乐观锁还是悲观锁:乐观锁
  15. MVCC的实现:增加了版本号,有个版本链,每次事务开始的时候有一个快照,其他事务读取的时候,读取那个快照。事务内部修改的时候有一个日志,日志会记录事务内部对这一行的修改,会用于事务的回滚。
  16. binlog、redolog(也可能是undo log)听说过吗:听说过,但是没深入了解过
  17. innodb的索引数据结构是什么:B+树
  18. 主键和非主键的索引呢:它一开始只会对主键建索引吧
  19. 非主键呢:不清楚
  20. B+树的叶子节点存放的什么:整体的数据,包括索引,都在里面
  21. 浏览器输入一个url,返回了一个error,怎么找出错的地方:通过状态码
  22. 没有状态码,只有一个error:啥都没有吗。。。
  23. dns的返回标志:那可能是dns上的错误,可能不存在这个域名
  24. 但是我输入的toutiao.com,我知道是存在的:是的。那可能是dns查询的时候出现了错误,那可以一步一步的查,它刚出去的时候访问的那个dns服务器(应该都是有的,小声bb)。可能最近的那个路由器或者电脑里面没有配dns。有没有可能(强颜欢笑)
  25. 你怎么知道最近的呢:查询dns的路径,好像是有一个命令的
  26. 什么命令呢:这命令名字我不记得了。。。
  27. linux怎么查看系统的状态呢:top
  28. top出来显示什么:cpu占用率,内存占用率、一些进程的信息
  29. 实习中,python后端,是怎么实现的http连接,是django吗:emm,是通过webpy的api直接调用的。。。。
  30. 你的request,post,具体实现是什么:emmm,我可以从c++方面来说吗
  31. 嗯:它要创建一个套接字,给套接字分配一个端口,等待连接的到来,连接来了之后,像redis的话,它收到连接,会复制一个socket,分配一个新端口,把这个连接分配给新socket,原先的socket继续listen。连接之后,读取socket里面缓冲区的内容,再内部进行处理,再通过socket传输出去。
  32. socket监听是哪个层:tcp
  33. 之前问的是http,这方面是不是不太了解:嗯
  34. 你还有什么领域没问你的吗:操作系统,计算机网络,你们应该用golang,python比较多吧
  35. 也有用c++的:那还有c++这些,了解的多一些
  36. 段页式存储执行的时候会访问几次内存:访问内存会通过页的级数也有关系,如果它是一级页表的话,它取页号一次,取物理地址一次,如果没有在内存中的话,还会访问磁盘
  37. 我问的段页式:段页式先取它的段内偏移量,然后再访问物理地址,是两次
  38. 进程的存储分布:栈、堆、数据区、代码区、共享库
  39. 代码放在哪:代码区
  40. 变量放在哪:静态变量放在静态的变量区,局部变量会放在栈中
  41. 指针呢:指针也是有静态的吧(小声(不确定)),直接声明的会放在栈中
  42. 指针指向的地址分配的空间呢,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 更新

加面一

  1. 自我介绍

  2. 实习介绍

    • 怎么实现版本管理
  3. 直接开始做题吧

    描述信息
    已知一天内用户登录登出的日志(数据量较大),求这一天用户在线的最大峰值和持续时间段

    • 日志包含字段(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. 再来个题吧

    条件:
    1.64匹马
    2.8个赛道
    3.每次比赛只能知道比赛结果名次,不能知道具体时间
    求:
    用最少的比赛次数,找出最快的4匹

    (这个我就不记录面试过程了,直接放一张图吧)

    图片说明

  2. redis 的数据结构:(同上)

  3. szet 的实现:(同上)

  4. 跳表:(同上)

  5. redis 的分布式:主从复制和哨兵模式。

  6. 怎么扩容:不清楚

  7. 一致性哈希知道吗:没了解过

  8. redis 分布式锁用过吗:没用过

  9. 死锁的条件:

  10. 如何避免死锁:

  11. 反问:

    • 部门和组:素材优化
    • 具体做什么呢
    • 技术栈:go,python,c++
    • 组里多少人

2020.12.29 更新

已挂

更多模拟面试

全部评论

(12) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐