百度测开牛客面经的整理
之前的面经都只是给了题目，我加上了一些自己在准备时查找到的答案，或者一些自己的理解，有错误还请谅解。（不知道还有没有要面试百度测开岗位的同学，希望有帮助）
自我介绍、项目介绍
内存分配方式
- 堆区：由程序员手动分配和释放 内存泄漏是指分配的内存空间无法被系统回收也无法被继续使用
- 栈区：由编译器自动分配自动释放，用于存放局部变量和参数，栈区的对象先进后出
- 常量区：存放常量字符串，程序结束后系统释放
- 静态变量区：存放全局变量和静态变量，在变量在程序运行期间都存在
进程和线程（协程）
- 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，线程是进程的一个实体，是cpu调度和分配的基本单位，是比进程更小的能独立运行的基本单位。协程是轻量级线程
- 进程是资源分配的基本单位，线程是调度的基本单位。
- 进程和线程的关系：
- 资源分配给进程，所有线程共享这个进程的所有资源
- 处理机分给线程，即真正在处理机上运行的是线程
- 线程在运行时过程中，需要协作同步。不同的进程的线程间要利用消息通信的办法实现同步
- 进程和线程的区别
- 调度：
- 并发性
- 拥有资源
- 系统开销
- 死锁、产生死锁的原因及必要条件
- 概念：多个线程因争夺资源而造成的僵局
- 条件：
- 资源不可剥夺
- 请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
- 不剥夺条件：进程已获得的资源在未使用之前，不能剥夺，只能自己释放
- 环路等待条件 即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。
- IPC 通信方式
- 管道
- 消息队列
- 信号量
- 共享内存
排序算法
各种排序算法总结分类
- 基于比较的排序算法：时间复杂度
O(nlog(n))~O(n^2)主要有 冒泡、选择、插入、归并、快排、堆排序。 - 非比较排序：时间复杂度
O(n),计数、基数、桶排序 - 重点：
- 快排的partition
def partition(arr,left:int,right:int,pivot:int) ->int : # pass # 返回分割点的下标
- 归并的merge
def merge(arr,left,right) # pass # 返回的是合并之后的列表
- 归并的merge
- 快排的partition
## 判断链表有环
## 提高检索效率
## 最大子数组和
```python
def func(nums):
n = len(nums)
dp = [0 for _ in range(n)]
dp[0] = nums[0]
for i in range(1,n):
dp[i] = max(dp[i]+nums[i],nums[i])
return max(dp)数组中超过一半的数字
def func(nums):
nums.sort()
mid = len(nums) >> 1 # 左移动一位 代表除以2
res = nums[mid]
return res
TCP和UDP tCP五层协议 TCPsyn攻击原理
数据库
基本增删查改
Linux基本命令行
查询CPU使用情况
Top命令
对测试的了解
Linux及命令
- 找名为"XX"的文件
- find [path] -name filename # 查找文件名
- find -size [+-]SIZE # 查找比SIZE大或者小的文件
- 名为"XX"文件，输出第一行的内容
- head -n 1 filename # 查看第一行内容
- tail -n 1 filename #查看最后一行内容
- 怎样一页一页地查看大文件的内容
- cat filename.txt | more
- Linux开机启动顺序
- 加载BIOS
- 读取MBR
- 启动Boot Loader
- 加载内核
- 初始化工作
- 启动开机自启动软件
- 进入登录状态
- 查看进程
- ps aux : 查看系统所有的进程数据
- ps -ef|grep XXXX #得到XXXX进程的pid
- 查看CPU使用的情况
- top
- gerp awk sed
- awk :
- sed ：
- 查看磁盘空间
- free df
- 熟悉的shell命令
- echo 用于字符串的输出 echo "hello world"
- $(var) ： 传递参数
- 可以直接在shell里面运行command命令行
- 正则表达式:读懂正则表达式就这么简单
- ^:正则匹配的开始 $正则比配的结束
- \d 表示数字 [1-9]
- \w 表示 [A-Z][a-z]
- {m,n}匹配的个数
- .* (.表示匹配任意字符 *表示任意次数的 ？表示0次或者1次，匹配模式是非贪婪的)
设计模式
- 实现单例模式
- 线程安全的单例模式
class singleton():
def __init__(self):
pass
def __new__(cls):
if not hasattr(cls,"_instance"):
cls._instance = super().__new__(cls)
return cls._instance
else:
return cls._instance - 观察者模式
数据结构
- AVL树的用途，怎么删除一个节点 AVL树的特点
- AVL树本质是一颗二叉搜索树 left< root < right
- 增删查改的时间复杂度均为
log(n) - 增加节点 都是先在叶子节点添加，然后通过上浮的操作，找到最终的位置
- 删除节点 都是通过将其字结点代替该节点，在删除子节点。
- 单分支情况 ： replace操作
- 双分支情况 ：swap操作（后续在递归为删除交换后的节点）
数据库
- 数据库的事务概念和使用场景
- 概念：逻辑上的一组操作，组成这组操作的各个单元，要么全部成功，要么全部不成功
- 事务的四大特性（ACID）：
- 原子性：事务是指不可分割的工作单位
- 一致性：一篇文章看懂事务的一致性 快速理解脏读、不可重复读、幻读
- 一致性应该理解为动词：多个参与者达成一致，达成共识。
- 引出事务的概念，事务单元是完成一个具体业务的最小单元。和线程安全的内容相似，必须让访问的共享资源资源互斥。
- 强一致性：所有的事务串行的执行。事务隔离级别中的序列化
- 事务的隔离级别：
- 可重复读：读读 是可并行的，但是会出现幻读，因为，这个级别，表示不会被看作共享资源的，所以可以insert。
- 读已提交：读锁被升级为写锁，当对共享资源正在读时，可以被写升级为写锁，那么读读，读写可以并行，于是出现了幻读。不可重复读等等现象。
- 读未提交：只加写锁，读不用申请锁(这样读操作可以读取在写的过程中的中间数据)，这样读读、读写、写读都可以并行执行，但是写写还不能执行。出现脏读，不可重复读，幻读
- 事务的一致性和线程安全所面临的问题一模一样，想要维持一致性，需要保证两点：共享变量和可见性、临界区代码访问的顺序性。
- 隔离性
- 持久性：事务一旦提交，它对数据库中的改变就是永久性的
- InnoDB引擎
- 深入了解MySQL存储引擎-------InnoDB
- InnoDB存储引擎
- InnoDB是事务型数据库的首选引擎，支持事务安全表（ACID）
- InnoDB是mySQL默认的存储引擎，默认的隔离级别是RR，并且在RR的隔离级别下更近一步，通过多版本并发控制（MVCC）解决不可重复读问题，加上间隙锁（也就是并发控制）解决幻读问题。因此InnoDB的RR隔离级别其实实现了串行化级别的效果，而保留了比较好的并发性能。
- InnoDB支持行级锁。行级锁可以最大程度的支持并发，行级锁是由存储引擎层实现的。
- InnoDB是为处理巨大数据量的最大性能设计。它的CPU效率可能是任何基于磁盘的关系型数据库引擎所不能匹敌的
- InnoDB引擎的底层实现
- InnoDB引擎采用B+Tree结构来作为索引结构
- 通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。
- B+Tree:B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，B-Tree中每个节点中有key，也有data，而每一页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小。当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。
- 索引
- 数据库查询 数据库中select 查询详解
- 查询所有数据
- 查询指定字段
- 消除重复数据 distinct
- 带条件查询 where 字句 where
- 比较运算符 = > < >=
- 逻辑运算符 and or not
- 模糊查询 like % _
- 范围查询 between and
- 空判断 is null / is not null
- 查询结果排序 order by
- 单字段
- 多字段
- 分页查询 limit startcount*
- 聚合函数
- sum
- avg
- max
- min
- count
- 分组 group by desc
- 建库、建表、插入元素。
creat DATABASE 'db_test'建库use 'db_test'选择数据库creat TABLE 'student'创建学生表drop TABLE 'student'删除表Python数据库连接
import pymysql
conn = pymysql.connect(
host="localhost",
port="3306",
user="root",
password="",
database="test",
charset="utf8" # 中间没有-
)
cursor = conn.cursor()
sql = """
select * from student;
"""
# 查询
sql = """
insert into student(name,age) values(%s,%s);
"""
#插入
res = cursor.execute(sql)
cursor.close()
conn.close() 计算机网络
-
- 浏览器对用户输入的网址做初步的格式化检查，补齐为https://或者HTTP
- 通过DNS将域名转换为ip地址：DNS 是个老实孩子，嫩自己查询的绝不会麻烦别人，这个机制感觉在局部变量，ARP中的查询都是类似的。（注意的是DNS使用的协议是UDP）
- DNS 先查询缓存，在查询本地的host文件，再通过DNS ip地址查询（例如 电信 114.114.114.114 谷歌的 8.8.8.8）
- Python之变量的作用域：LEGB 局部作用域local>嵌套作用域enclosing>全局作用域global>内置作用域build
- ARP先查询arp 高速缓存表
- 浏览器与该服务器建立TCP连接（默认80端口），浏览器向WEB服务器发送一个HTTP请求
- 服务器处理请求，返回一个HTTP响应
- 浏览器显示HTML
POST和GET方法区别
DNS
TCP和UDP
- 三次握手和四次挥手（每个过程中都会携带seq的信息）
- 三次握手
- TCP把把连接作为最基本的对象，每一条TCP连接都有两个端点，这种端点称之为套接字（socket）。定义为端口号拼接到IP地址即构成套接字，例如 192.168.0.1：80
- 主要关注几个标志为 SYN ACK seq 客户端和服务器端都会有这几个标志位。
- 首先两者都是closed的状态客户端是主动打开 服务器端是被动打开，都会建立一个TCB（Tcp 控制块）
- 客户端向服务器端发送连接请求，主要SYN标志为设置为1 seq = x 。TCP客户端此时进入SYN-SENT的状态。SYN报文段不携带数据 但是消耗掉一个序号
- 服务器端接收到连接请求，如果同意连接，则发出确认报文 确认报文中ACK = 1 SYN = 1 seq = y ack = x+1 (通过这个小写的ack进行对报文接收成功的确认，因为两边都会有一个ack的预期值，如果不一致，则会重新发送)。此时服务器端进入SYN-RCVD(同步收到)的状态。这个报文不能携带数据，但是要消耗一个序号
- 当客户端进程收到确认后，，还要想服务器给出确认。ACK = 1 seq = x+1 ack = y+1. 客户端进入ESTABLISHED 状态。当服务器收到客户端的确认后也进入ESTABLISHED状态。
- 四次挥手 （客户端的 seq第一次是u后，之后都是u+1）
- 客户端主动关闭，服务器被动关闭
- 客户端发出连接释放报文，并停止发送数据。释放数据报文首部 FIN =1 其序列号为seq = u,此时客户端进入FIN-WAIT-1 状态。
- 服务器收到连接释放的报文，发出确认报文。ACK = 1 ack = u+1 并且带上自己的序列号seq = v。 服务端进入CLOSE-WAIT 状态。此时进入了半关闭状态 客户端不能像服务器发送数据，但是能够接受服务器端发送的数据了
- 可端端收到服务器的确认请求后，客户端进入FIN_WAIT-2状态，等待服务器发送释放连接请求。
- 服务器端发送完一些数据之后，先客户端发送连接释放报文，FIN = 1 ack = u+1 ACK =1 .此时服务器端进入LAST-ACK（最后确认状态）。
- 客户端接收到服务器的连接释放报文后，必须发出确认，ACK = 1 ack = w+1。 客户端进入LIME-WAIT状态，此时TCP连接还没有释放，必须经过2*MSL（最大报文段寿命）的时间后。进入CLOSED的状态。
- 服务器收到客户端发出的确认后，立即进入CLOSED 的状态。（可以看出服务器端结束TCP连接的时间比客户端早一些）
socket编程实现过程
网络进程之间的通信。socket抽象层是在传输层和应用层之间（典型的例子可以从FQ的故事讲起。shadowsock和VPN的区别）。socket是在tcp/ip上编程的。大致过程如下
服务器端：- 创建socket socket()
- 绑定socket和端口号 bind()
- 监听该端口号 listen()
- 接收来自客户端的连接请求 accept()
HTTP返回码
FTP端口号
HTTP和HTTPS的区别
场景题
-
进程和线程
进程通信方式
进程个线程的区别
多线程如何保证数据同步？
进程死锁的概念
进程调度的方法
进程的状态，进程的相互转换
编程题
排序问题
编写一个diff函数：比较两个json文件，求差别率
查找只出现一次的数字：只有一个出现一次；有两个出现一次；非一次出现的数字出现次数为三次。（均使用位运算解决）
输入一个字符串类型的数字，有可能有正负号，或者0X开头的16进制，将其转换为int类型
链表反转
def reverseLinkedlist(head)： if not head: return None pre = None cur = head while(cur): _next = cur.next cur.next = pre pre = cur cur = _next return pre
字符串匹配
* 单链表找环入口
```python
def searchLoop(head):
fast,slow=head.next.next,head.next
while(fast == slow and fast is not NOne):
fast = fast.next.next
slow = slow.next
meeting = fast
cur = meeting.next
k= 0
while(cur != meeting):
k += 1
cur = cur.next
length = k
first,second = head,head
while(k != 0):
first = first.next
while(first != second):
first = first.next
second = second.next
res = second
return res
- n*n的正方形网格找长方形的个数
- 10进制转K进制
- 字符串反转
def reverse_arr(arr): l = len(arr) mid = l//2 for i in range(0, mid): arr[i] = arr[-(i+1)] return arr
* 二分查找
```python
def binary_search(arr,target):
l, r = 0,len(arr)-1
while(l<r>):
mid = (l+r)//2
if arr[mid]== target:
return mid
elif arr[mid] < target:
l = mid + 1
else：
r = mid-1
return None
def binary_search_recur(arr,target,l,r):
if l>r:
return -1
mid = (l+r)//2
if arr[mid]>target:
return binary_search_recur(arr,target,l,mid -1)
elif arr[mid]<target:
return binary_search_recur(arr,target,mid +1,r)
else:
return mid两个栈实现一个队列 剑指offer
class MyQueue(object): def __init__(self): """ Initialize your data structure here. """ self.stack1 = [] self.stack2 = [] def push(self, x): """ Push element x to the back of queue. :type x: int :rtype: void """ self.stack1.append(x) def pop(self): """ Removes the element from in front of queue and returns that element. :rtype: int """ if len(self.stack2) == 0: self.stack2 = self.stack1[::-1] self.stack1 = [] return self.stack2.pop() else: return self.stack2.pop() def peek(self): """ Get the front element. :rtype: int """ if len(self.stack2) == 0: return self.stack1[0] else: return self.stack2[-1] def empty(self): """ Returns whether the queue is empty. :rtype: bool """ if self.stack1 or self.stack2: return False else: return True
Your MyQueue object will be instantiated and called as such:
obj = MyQueue()
obj.push(x)
param_2 = obj.pop()
param_3 = obj.peek()
param_4 = obj.empty()
* 回字形依次输出一个矩阵中的数(顺时针打印矩阵)
```python
class Solution(object):
def printMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
res = []
while(matrix):
res.extend(matrix[0])
matrix = list(zip(*matrix[1:])) # 转置的操作 如果可以使用numpy，就可以直接.T就行了。
print(matrix)
matrix = matrix[::-1]
return res
给定一个有序数组，找出连续子串和为M的一个子串 和为S的连续正数序列
def func(target): res = [] left, right = 1,2 mid = (target + 1) // 2 while(right<= mid and left < right): tem = (left + right)*(right - left + 1) // 2 if tem == target: right += 1 res.append([x for x in range(left,right)]) elif tem < target: right += 1 else: left += 1 return res输入一行字符 分别统计中英文字母，空格，数字和其他字符个数
一个数组有n个元素，其中1<=a[i]<=n请找出[1,n]出现的元素
树的遍历（递归，非递归）
判断链表是否有环
微信发红包
字符串回文判断
字符串括号匹配
链表删除相同的节点
两个字符串的最长字符串
数组的最大子序列和
def maxSubArray(nums): n = len(nums) dp = [0 for _ in range(n)] dp[0] = nums[0] for i in range(1,n): dp[i] = max(dp[i-1]+nums[i],nums[i]) return max(dp)
* 连续子数组最大和 ```python # 使用动态规划 def maxSubArray(nums): pass
- 交换两个数字，不使用新的变量
* 数组第K小 * 有N个硬币，分别是一分，两分，五分的，加起来一起M元，写出所有硬币组合 * 快排 * 快速查找相同的字符串 * 给定一个字符串，包括字符串和空格，反转其中的字符串 * 链表中找出倒数的第K个节点 * 跳台阶问题 * 字符串中每个字符出现的次数 * 合并两个有序的数组 * 给一个数组，快拍一次后数组的情况 * 数组全排列 * 求m*n矩阵的逆转90度的矩阵 * 求3的n次方 * 一个数组的元素都可以乘以任意个2，可不可以调成都一样 ## 海量数据 * 10个1G的文件，找出出现次数的前10单词 * 给定一个文件，可能非常大，100G左右，如何统计其中重复的行，输出哪些行重复和重复次数 ## 智力题 * 两个桶 一个 5L一个6L,怎么量3L的水 * 四棵树，怎么两两相等 * 三等分一张纸 * 给你一个数n,求出所有和等于n的可能 * 有一个人流落荒岛，四天后才有人来救他，他有4个A药片和4个B药片，每天吃一个A一个B才能存活下来，但是A,B在外观上五法区分，问如何存活下来？ ## 测试相关 * 对测试的了解，为什么想要从事测开这个职位 * 登录界面的测试 * 搜索框测试 * selenium测页面的时候具体怎么实现 * 电梯怎么测 * 白盒测试有哪些方法 * 软件开发流程 * 软件测试方法 * bug的生存周期#百度##面经##校招##测试工程师#
投递京东等公司10个岗位 >