58同城2021校招笔试-算法
时长:120分钟 总分:100分
139浏览 0人已完成答题
题型介绍
| 题型 | 单选题 | 填空题 |
|---|---|---|
| 数量 | 20 | 3 |
2.
一棵红黑树，从根节点(包含根节点)开始到某个nil叶子节点的父节点的最短路...
一棵红黑树，从根节点(包含根节点)开始到某个nil叶子节点的父节点的最短路径节点数为2，那么当前树中根节点(包含根节点)到某个nil叶子节点的父节点的最长路径中节点的个数最多为几个?
3.
LRU-K是LRU算法的变种，K代表最近使用的次数，LRU可以认为是LRU...
LRU-K是LRU算法的变种，K代表最近使用的次数，LRU可以认为是LRU-1。不同于LRU算法的是，LRU-K算法需要维护两套队列（历史访问队列，缓存队列）。当历史访问队列中的数据被命中K次后，数据才会移动至缓存队列中。假设所有队列长度为5，历史访问队列采用FIFO淘汰策略，初始内存中没有数据，使用LRU-2算法，数据访问顺序如下：
9，5，6，7，8，3，8，9，5，9，8，3，4，7，5，6
请问最终内存中缓存队列是（队尾-队头）
5.
程序段:count=0for(k=1k<=nk=k*2){fo...
程序段:
count=0
for(k=1k<=nk=k*2){
for(j=1j<=nj+1){
count++
}
}, 运行该程序段的时间复杂度是多少
count=0
for(k=1k<=nk=k*2){
for(j=1j<=nj+1){
count++
}
}, 运行该程序段的时间复杂度是多少
8.
有一个序列为{7，9，11，16，19，20，27，40，48，55，67...
有一个序列为{7，9，11，16，19，20，27，40，48，55，67，69，71，83，89，97}，如果使用二分查找法查找到89，那么经过（ ）次比较后查找成功。
10.
假设有一个栈，栈底到顶的存放的元素是K、J、G、L，现有一个元素E要入栈，...
假设有一个栈，栈底到顶的存放的元素是K、J、G、L，现有一个元素E要入栈，同时栈中的元素要出栈，则出栈顺序有可能是：（ ）
20.
下图是某个模型的学习曲线（横轴是样本数，纵轴为训练集和交叉验证集的误差），...
下图是某个模型的学习曲线（横轴是样本数，纵轴为训练集和交叉验证集的误差），以下说法正确的数量有多少个？
(2). 上图表示的模型表现不佳，且出现的问题是高偏差问题
(3). 高方差需要增加特征数量（描述与上图无关，不考虑上图）
(4). 高偏差需要引入更多的相关特征（描述与上图无关，不考虑上图）
(5). 高偏差需要减少正则化参数（描述与上图无关，不考虑上图）
22.
等频离散化
为了提高鲁棒性，连续特征在输入模型前，通常会通过“等频”离散化算子将连续特征转化成离散特征。“等频”离散化的定义如下：
给定从小到大已排序整数数组A，和划分段数K，“等频”离散化操作会将A划分成K个子集，且子集满足如下条件:
- 子集之间没有重复元素
- 在所有可能划分中，离散化输出的划分子集长度的方差最小
比如:
A=[1, 1, 2, 2], K=2，则[1, 1]，[2, 2] 是满足定义的划分（子集[1, 1]和[2, 2]之间没有重复元素），且方差为0、最小。 划分的平均长度E为(2+2)/2=2, 划分子集长度的方差为( (2-E)^2 + (2-E)^2 ) / 2 = ( (2-2)^2 + (2-2)^2 ) / 2 = 0。
A=[1, 1, 1, 2, 2 , 4, 5, 5], K=3, 侧可能的子集间没有重复元素的划分有: （1）[1, 1, 1], [2, 2, 4], [5, 5] （2）[1, 1, 1], [2, 2], [4, 5, 5] （3）[1, 1, 1, 2, 2], [4], [5, 5] 其中（1）和(2)均是满足定义的划分，且方差为0.22、最小。以[1, 1, 1], [2, 2, 4], [5, 5]为例: 划分的平均长度E为(3+3+2)/3=8/3, 划分子集长度的方差为( (3-8/3)^2 + (3-8/3)^2 + (2-8/3)^2 ) / 3 = 0.22。
请设计算法，实现如上定义的“等频”离散化算子。
输入输出说明
- 输入: 整数数组A和划分K(整数)。A非空且长度小于65,535，A中的整数取值范围为[-32,768, 32,767]，K的长度范围为[1, 100]。A中必然存在至少K个不同的元素。
- 输出: 算子输出的划分。如果有满足约束的多组划分，输出任一组。
23.
二叉树遍历
对给定的二叉树依次完成前序，中序，后序遍历，并输出遍历结果。
每行输入为一个二叉树，一维数组形式。其中-1表示Nil节点，例如：1,7,2,6,-1,4,8 构成的二叉树如下图所示：
结果以二维数组形式输出(前序，中序，后序遍历的结果)，其中Nil节点不用输出。
