BAT机器学习面试1000题系列(第41~45题)

2017 年 10 月 6 日 七月在线实验室 人工智能面试题

(点击上方公众号,快速关注一起学AI)


41. 当不知道数据所带标签时,可以使用哪种技术促使带同类标签的数据与带其他标签的数据相分离?(B)
  A. 分类       B. 聚类      C. 关联分析      D. 隐马尔可夫链


42. 建立一个模型,通过这个模型根据已知的变量值来预测其他某个变量值属于数据挖掘的哪一类任务?(C)

  A. 根据内容检索    B. 建模描述
  C. 预测建模  D. 寻找模式和规则


43. 以下哪种方法不属于特征选择的标准方法?(D)
A嵌入  B 过滤    C  包装   D  抽样      


44. 请用python编写函数find_string,从文本中搜索并打印内容,要求支持通配符星号和问号。
例子:

 >>>find_string('hello\nworld\n','wor')
['wor']
>>>find_string('hello\nworld\n','l*d')
['ld']
>>>find_string('hello\nworld\n','o.')
['or']
答案
def find_string(str,pat):
 import re
 return re.findall(pat,str,re.I) 


45. 说下红黑树的五个性质
红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

红黑树,作为一棵二叉查找树,满足二叉查找树的一般性质。下面,来了解下 二叉查找树的一般性质。
二叉查找树,也称有序二叉树(ordered binary tree),或已排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:
若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
任意节点的左、右子树也分别为二叉查找树。
没有键值相等的节点(no duplicate nodes)。
因为一棵由n个结点随机构造的二叉查找树的高度为lgn,所以顺理成章,二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后,则这些操作最坏情况运行时间为O(n)。
红黑树虽然本质上是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢?这就引出了红黑树的5个性质:
每个结点要么是红的要么是黑的。  
根结点是黑的。  
每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。  
如果一个结点是红的,那么它的两个儿子都是黑的。  
 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。 
正是红黑树的这5条性质,使一棵n个结点的红黑树始终保持了logn的高度,从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。更多请参见此文:《教你初步了解红黑树》(链接:http://blog.csdn.net/v_july_v/article/details/6105630)。



有好的见解或者面试题目欢迎在评论区留言,一起交流探讨。

欢迎转发,让更多小伙伴收益!

登录查看更多
1

相关内容

自回归模型:PixelCNN
专知会员服务
26+阅读 · 2020年3月21日
【干货书】机器学习Python实战教程,366页pdf
专知会员服务
338+阅读 · 2020年3月17日
机器学习速查手册,135页pdf
专知会员服务
338+阅读 · 2020年3月15日
【新书】Python中的经典计算机科学问题,224页PDF
专知会员服务
52+阅读 · 2019年12月31日
【机器学习课程】Google机器学习速成课程
专知会员服务
164+阅读 · 2019年12月2日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
BAT机器学习面试题1000题(376~380题)
七月在线实验室
9+阅读 · 2018年8月27日
BAT机器学习面试题1000题(316~320题)
七月在线实验室
14+阅读 · 2018年1月18日
机器学习面试题精讲(一)
七月在线实验室
4+阅读 · 2018年1月11日
BAT题库 | 机器学习面试1000题系列(第226~230题)
七月在线实验室
9+阅读 · 2017年11月27日
BAT题库 | 机器学习面试1000题系列(第196~200题)
七月在线实验室
17+阅读 · 2017年11月16日
BAT题库 | 机器学习面试1000题系列(第191~195题)
七月在线实验室
6+阅读 · 2017年11月15日
BAT机器学习面试1000题系列(第116~120题)
七月在线实验室
16+阅读 · 2017年10月24日
BAT机器学习面试1000题系列(第76~80题)
七月在线实验室
5+阅读 · 2017年10月13日
BAT机器学习面试1000题系列(第46~50题)
七月在线实验室
7+阅读 · 2017年10月7日
BAT机器学习面试1000题系列(第36~40题)
七月在线实验室
8+阅读 · 2017年10月3日
Deep Learning for Energy Markets
Arxiv
9+阅读 · 2019年4月10日
Parsimonious Bayesian deep networks
Arxiv
5+阅读 · 2018年10月17日
Hierarchical Deep Multiagent Reinforcement Learning
Arxiv
8+阅读 · 2018年9月25日
Arxiv
5+阅读 · 2018年6月12日
Arxiv
15+阅读 · 2018年4月5日
VIP会员
相关VIP内容
自回归模型:PixelCNN
专知会员服务
26+阅读 · 2020年3月21日
【干货书】机器学习Python实战教程,366页pdf
专知会员服务
338+阅读 · 2020年3月17日
机器学习速查手册,135页pdf
专知会员服务
338+阅读 · 2020年3月15日
【新书】Python中的经典计算机科学问题,224页PDF
专知会员服务
52+阅读 · 2019年12月31日
【机器学习课程】Google机器学习速成课程
专知会员服务
164+阅读 · 2019年12月2日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
BAT机器学习面试题1000题(376~380题)
七月在线实验室
9+阅读 · 2018年8月27日
BAT机器学习面试题1000题(316~320题)
七月在线实验室
14+阅读 · 2018年1月18日
机器学习面试题精讲(一)
七月在线实验室
4+阅读 · 2018年1月11日
BAT题库 | 机器学习面试1000题系列(第226~230题)
七月在线实验室
9+阅读 · 2017年11月27日
BAT题库 | 机器学习面试1000题系列(第196~200题)
七月在线实验室
17+阅读 · 2017年11月16日
BAT题库 | 机器学习面试1000题系列(第191~195题)
七月在线实验室
6+阅读 · 2017年11月15日
BAT机器学习面试1000题系列(第116~120题)
七月在线实验室
16+阅读 · 2017年10月24日
BAT机器学习面试1000题系列(第76~80题)
七月在线实验室
5+阅读 · 2017年10月13日
BAT机器学习面试1000题系列(第46~50题)
七月在线实验室
7+阅读 · 2017年10月7日
BAT机器学习面试1000题系列(第36~40题)
七月在线实验室
8+阅读 · 2017年10月3日
相关论文
Deep Learning for Energy Markets
Arxiv
9+阅读 · 2019年4月10日
Parsimonious Bayesian deep networks
Arxiv
5+阅读 · 2018年10月17日
Hierarchical Deep Multiagent Reinforcement Learning
Arxiv
8+阅读 · 2018年9月25日
Arxiv
5+阅读 · 2018年6月12日
Arxiv
15+阅读 · 2018年4月5日
Top
微信扫码咨询专知VIP会员