Post

【暑期实习面经】字节跳动-穿山甲-后端开发(接受offer)

一面

2021年3月23日
1小时
自我介绍

线程有哪些状态
什么是死锁,如何恢复和避免

算法题
1.长度为n+1的数组,元素为1~n,有一个数字出现了两次,找出出现两次的数字
要求:时间复杂度O(n),空间复杂度O(1)
方法1:sum(a) - sum(range(1, n + 1)) 问题:可能溢出
方法2:xor(a) ^ xor(range(1, n + 1)) 其中xor表示将所有元素异或起来

2.判断一棵二叉树是否是另一棵二叉树的子树
方法1:递归,时间复杂度? 极端情况:只有叶节点不同,O(mn)
方法2:中序遍历+子串判断 KMP算法

3.最长递增子序列
动态规划(没想出来)
(力扣300)

简历项目
ES的底层实现(不了解)

计网:TCP三次握手四次挥手,TCP和UDP的区别

数据库:MySQL存储引擎,索引的优缺点,MySQL索引类型(B+树、哈希,用B+树的好处,为什么不用B树/红黑树?),事务的四个特性

评价:还可以,要注重底层原理

二面

2021年3月28日
1小时

自我介绍
简历项目

编程
1.Python yield语句
2.字典的底层结构(不知道)(使用伪随机探测的散列表)
3.Java的HashMap如何实现(数组+链表/红黑树)
4.Python中如何创建一个进程(Process类),进程如何通信
5.一个线程从数据库读取URL,10个线程负责爬取,如何设计(生产者消费者模式,信号量?)→Java线程池,创建的方法和核心参数
6.垃圾收集算法CMS/G1(不知道)
7.SpringBoot启动过程(不知道)

计网
1.输入网址到显示页面的过程
2.DNS解析之后如何根据IP地址找到主机(路由器路由功能,转发表)
3.如何处理HTTP请求(Web服务器:匹配URL,调用视图函数,匹配不上的404)

数据库
1.事务

1
2
3
4
5
6
7
8
9
10
ID | AGE 
1 | 10

A                      B
---------begin   -----------begin
select -> 10
                      update -> 20
                     -----------commit
select -> ?
-----------commit

可重复读,仍然是10
此时A是否可以更新?有冲突?

2.索引

1
2
ID | AGE | NAME(uniq_key)
1 | 10  | zhangsan

主键索引和unique索引的性能差别?(都是B+树,性能一样)

3.主从同步(不了解)

操作系统
用户态、内核态的区别,进程如何从用户态进入内核态(忘了)(系统调用、异常、外部设备中断)

编程
1.给定一个无序数组,查找第一个缺失的正整数

1
2
3
4
5
6
Example 1:
Input: 1,2,0 Output: 3
Example 2:
Input: 3,4,-1,1 Output: 2
Example 3:
Input: 7,8,9,11,12 Output: 1

散列表:时间复杂度O(n),空间复杂度O(n)
排序:时间复杂度O(nlog n),空间复杂度O(1)
还能优化空间吗→散列表的元素改成区间,难点是如何合并→bitset
(力扣41原题!)

2.给定一个二叉树和一个数字n,判断二叉树中是否有一个路径上的数字之和等于给定的数字n
如果要输出路径如何做(增加path参数)

三面

2021年3月31日
30分钟

自我介绍

简历项目:数据处理
1.导出原始数据时如何验证,写伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def valid(paper, validators):
    for key in validators:
        if not validators[key](paper[key]):
            return False
    return True

if __name__ == '__main__':
    paper = {'id': 1, 'title': 'foo', 'keywords': 'a;b;c', 'authors': 'a[A];b[B]'}
    validators = {
        'title': lambda s: len(s) > 0,
        'authors': lambda s: re.fullmatch(r'([A-Za-z]+\[[A-Za-z]+\];)*[A-Za-z]+\[[A-Za-z]+\]', s)
    }
    print(valid(paper, validators))

2.如何从MySQL导入图数据库,写伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Paper:
    id 
    title
    authors: str

class PaperVertex:
    id
    title
    authors: List[AuthorDO]

class EntityUtils:
    def paper2paperVertex(paper):
        authors = paper.authors.split(';')
        paperVertex
        vertex_id = g.addV().property(...).next()
        paper.vertex_id = vertex_id

3.ES的原理(不了解),如果让你设计会怎么设计(B+树)

反问

HR面

2021年4月1日
10分钟

自我介绍
遇到过的困难
职业规划
业务方向:后端开发
有没有面其他公司,拿到offer会怎么选择
实习时间(出勤要求:每周4~5天,大小周)

This post is licensed under CC BY 4.0 by the author.