每日三问合辑二

19.最长公共子序列与最长公共子串的区别？

最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。

20.如何用代码实现最长公共子序列

# -*- coding: utf-8 -*-

#!/usr/bin/python

import numpy

def find_lcseque(s1, s2):

#生成字符串长度加1的矩阵，m用来保存对应位置匹配的结果

m = [ [ 0 for x in range(len(s2)+1) ] for y in range(len(s1)+1) ]

# d用来记录转移方向

d = [ [ None for x in range(len(s2)+1) ] for y in range(len(s1)+1) ]

for p1 in range(len(s1)):

for p2 in range(len(s2)):

if s1[p1] == s2[p2]: #字符匹配成功，则该位置的值为左上方的值加1

m[p1+1][p2+1] = m[p1][p2]+1

d[p1+1][p2+1] = 'ok'

elif m[p1+1][p2] > m[p1][p2+1]: #左大于上，则该位置为左值，并标记回溯的方向

m[p1+1][p2+1] = m[p1+1][p2]

d[p1+1][p2+1] = 'left'

else: #上值大于左值，则该位置的值为上值，并标记方向up

m[p1+1][p2+1] = m[p1][p2+1]

d[p1+1][p2+1] = 'up'

(p1, p2) = (len(s1), len(s2))

print numpy.array(d)

s = []

while m[p1][p2]: #不为None时

c = d[p1][p2]

if c == 'ok': #匹配成功，插入该字符，并向左上角找下一个

s.append(s1[p1-1])

p1-=1

p2-=1

if c =='left': #根据标记，向左找下一个

p2 -= 1

if c == 'up': #根据标记，向上找下一个

p1 -= 1

s.reverse()

return ''.join(s)

print find_lcseque('abdfg','abcdfg')

若提示安装numpy包，尝试按照以下步骤：

step1：先安装setuptools

1.wget --no-check-certificatehttps://pypi.python.org/packages/source/s/setuptools/setuptools-0.6c11.tar.gz

2.解压

3.cd进入解压后的路径

4.输入命令：python setup.py install

step2：再安装numpy

1.在官网上下载该包：http://sourceforge.net/projects/numpy/files/

2.解压

3.cd进入解压后的路径

4.输入命令：python setup.py install

5.安装完成

6.测试代码

21.如何用代码实现最长公共子串

# -*- coding: utf-8 -*-

#!/usr/bin/python

def find_lcsubstr(s1, s2):

m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成矩阵，为方便后续计算，比字符串长度多了一列

mmax=0 #最长匹配的长度

p=0 #最长匹配对应在s1中的最后一位

for i in range(len(s1)):

for j in range(len(s2)):

if s1[i]==s2[j]:

m[i+1][j+1]=m[i][j]+1

if m[i+1][j+1]>mmax:

mmax=m[i+1][j+1]

p=i+1

return s1[p-mmax:p],mmax #返回最长子串及其长度

print find_lcsubstr('abcdfg','abdfg')

22.linux中wget 、apt-get、yum rpm区别？

wget是一种下载工具，类似于迅雷。

rpm:软件管理的软件，全称为redhat package management，用于安装卸载.rpm软件

yum:是linux系统下的一种软件安装方式，全称为Yellow dog Updater Modified，基于RPM包管理，能够从指定的服务器自动下载RPM包并且安装，可以自动处理依赖性关系，并且一次安装所有依赖的软件包。

串联一下：

使用wget下载一个rpm包,然后用rpm -ivh xxx.rpm安装这个软件。嫌麻烦的话，就可以直接用yum install xxx来自动下载和安装依赖的rpm软件。

23.先验概率和后验概率的区别？

先验概率（prior probability）是指根据以往经验和分析得到的概率，如全概率公式，它往往作为"由因求果"问题中的"因"出现的概率。

后验概率( posterior probability)是指通过调查或其它方式获取新的附加信息，利用贝叶斯公式对先验概率进行修正，而后得到的概率，而且在利用样本资料计算逻辑概率时，还要使用理论概率分布，需要更多的数理统计知识。

举一个简单的例子：一口袋里有3只红球、2只白球，采用不放回方式摸取，求：

第一次摸到红球（记作A）的概率；

第二次摸到红球（记作B）的概率；

已知第二次摸到了红球，求第一次摸到的是红球的概率。

解：

P(A)=3/5，这就是验前概率；

P(B)=P(A)P(BA)+P(A逆)P(BA逆)=3/5；

P(AB)=P(A)P(BA)/P(B)=1/2，这就是验后概率。

24.一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。

这题是考虑时间效率，用trie树统计每个词出现的次数，时间复杂度是O（n*len）(len表示单词的平均长度)。然后是找出出现最频繁的前10个词，可以用堆实现，时间复杂度是O（n*lg10）,所以总的时间复杂度是O（n*len+n*lg10)。

25.Trie树和Hashmap的适用情况？

HashMap哈希表：用于解决O(1)的精确查找，无论是内存中实现程序逻辑还是外存中实现key - value存储，几乎无处不用

Trie字典树：用于解决前缀检索，属于模糊查找，最经典的应用就是搜索suggest，搜索"变形"，suggest给你"变形金刚"

区别：最基本的用处不一样。Trie在前缀查询方面应用是要比hashmap快的多的。举个栗子，你有一篇动漫分析文章，外加一个动漫人物名称字典dict，怎么从文章中直接把所有动漫人物爬出来。如果你要用hashmap（或者hashset），最基本的用法就是把动漫人物名全存到map或者set里，扫描文章的每一个字，以这个字为人名开头，向后搜索若干位，知道最大人名长度，如果hashset里都没有的话，扫描下一个字作为人名开头。可以发现巨慢无比，时间复杂度O（mn）。用trie的话不用重复搜索，复杂度O（n）可以实现。

原答案链接：

https://www.zhihu.com/question/264056945/answer/276580308

26.数据库和数据仓库的区别？OLTP和OLAP的区别？

数据库（DataBase，DB）：数据库是计算机应用系统中的一种专门管理数据资源的系统。管理数据库的软件称为数据库管理系统（DataBase Management System，DBMS），如SYBASE、DB2、ORACLE、MySQL、ACCESS等。

数据仓库（DataWareHouse，DWH）：是为企业所有级别的决策制定过程，提供所有类型数据支持的战略集合。 在数据库已经大量存在的情况下，为了进一步挖掘数据资源、为了决策需要而产生。

当今的数据处理大致可以分成两大类：联机事务处理OLTP（on-line transaction processing）、联机分析处理OLAP（On-Line Analytical Processing）。OLTP是传统的关系型数据库的主要应用，主要是基本的、日常的事务处理，例如银行交易。OLAP是数据仓库系统的主要应用，支持复杂的分析操作，侧重决策支持，并且提供直观易懂的查询结果.

27.如何查看RDD的内容？

（1）写出到文件系统，即调用所使用的RDD的类中类似saveasTextFile()的方法，例如对于JavaPairRDD的对象x，可以用x.saveasTextFile("输出文件路径")。

（2）还可将RDD转回List处理查看：有take()方法和collect()方法，但是collect方法会将整个RDD内容集中，如果数据集过大，在网络传输和内存占用上都可能造成压力，如果只是要查看RDD中的几个值还是take方法较为合适。

28.Hive中两字段相除，结果保留两位小数

select cast(字段1/字段2 as decimal(18,2)) from table_a;

29.计算文本中每行单词的数目

# -*- coding: UTF-8 -*-

import sys

wordnum = {} #创建字典，用于存放每行的单词数

lineid = 0

for line in sys.stdin:

ss = line.strip().split(' ')

lineid += 1

wordnum[lineid] = len(ss)

print wordnum

30.写出mapreduce的wordcount

####map.py

import sys

for line in sys.stdin:

ss = line.strip().split(' ')

for s in ss:

if s.strip() != "": #避免单词间出现多个空格，影响排序结果

print "%s\t%s" % (s,1)

####red.py

import sys

current_word = None

count_pool = []

sum = 0

for line in stdin:

word, val = line.strip().split('\t')

if current_word == None:

current_word = word

if current_word != word:

for count in count_pool:

sum += count

print "%s\t%s" % (current_word,sum)

current_word = word

count_pool = []

sum = 0

count_pool.append(int(val))

for count in count_pool:

sum += count

print "%s\t%s" % (current_word, str(sum))

31.用mapreduce如何解决两组数据的归并排序问题

数据a:

0 java

2 java

4 java

...

98 java

100 java

数据b:

1 hadoop

3 hadoop

5 hadoop

...

97 hadoop

99 hadoop

###-map_sort-###

import sys

base_count = 10000

for line in sys.stdin:

ss = line.strip().split('\t')

key = ss[0]

val = ss[1]

new_key = base_count + int(key)

red_idx = 1

if new_key < (10100 + 10000) / 2:

red_idx = 0

print "%s\t%s\t%s" % (red_idx, new_key, val)

###-red_sort-###

import sys

for line in sys.stdin:

idx_id, key, val = line.strip().split('\t')

print '\t'.join([key, val])

32.shell脚本通常有哪些类型

通常写一个shell脚本都要在第一行注明使用什么解释器来解释，即写成：#!/bin/bash

这样的形式，意思是告诉系统要使用/bin/bash这个解释器来解释下面的语句。shell的脚本一般用.sh作为后缀，只要你写的脚本的第一行有#!/bin/bash或者是其他的解释器，如#!/bin/csh，执行该脚本时系统会使用该注明的解释器来解释。

.csh脚本使用csh这个shell解释器来解释。

.sh脚本使用bash或sh解释器来解释。

.py则是使用python来解释。

33.Spark RDD、DataFrame和DataSet的区别

RDD

优点:

1.编译时类型安全，编译时就能检查出类型错误

2.面向对象的编程风格，直接通过类名点的方式来操作数据

缺点:

1.序列化和反序列化的性能开销，无论是集群间的通信,还是IO操作都需要对对象的结构和数据进行序列化和反序列化.

2.GC的性能开销，频繁的创建和销毁对象,势必会增加GC

DataFrame

DataFrame引入了schema和off-heap

•schema: RDD每一行的数据,结构都是一样的.这个结构就存储在schema中. Spark通过schame就能够读懂数据,因此在通信和IO时就只需要序列化和反序列化数据,而结构的部分就可以省略了。

•off-heap:意味着JVM堆以外的内存,这些内存直接受操作系统管理（而不是JVM）。Spark能够以二进制的形式序列化数据(不包括结构)到off-heap中,当要操作数据时,就直接操作off-heap内存.由于Spark理解schema,所以知道该如何操作。

off-heap就像地盘, schema就像地图, Spark有地图又有自己地盘了,就可以自己说了算了,不再受JVM的限制,也就不再收GC的困扰了。

通过schema和off-heap, DataFrame解决了RDD的缺点,但是却丢了RDD的优点。DataFrame不是类型安全的, API也不是面向对象风格的。

DataSet

DataSet结合了RDD和DataFrame的优点,并带来的一个新的概念Encoder

当序列化数据时, Encoder产生字节码与off-heap进行交互,能够达到按需访问数据的效果,而不用反序列化整个对象. Spark还没有提供自定义Encoder的API,但是未来会加入.

34.hashmap的原理，以及如何解决hash冲突？

HashMap 采用一种算法决定每个元素的存储位置。当执行map.put(String,Obect)方法时，系统将调用String的hashCode()方法得到其hashCode值——每个Java对象都有hashCode()方法，都可通过该方法获得它的hashCode值。得到这个对象的hashCode值之后，系统会根据该hashCode值来决定该元素的存储位置。源码中用到了一个重要的内部接口：Map.Entry，每个Map.Entry其实就是一个key-value对。从上面程序中可以看出：当系统决定存HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry的存储位置。

Hashmap里面的bucket出现了单链表的形式，散列表要解决的一个问题就是散列值的冲突问题，通常是两种方法：链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式，链表是单向链表。

HashMap里面没有出现hash冲突时，没有形成单链表时，hashmap查找元素很快,get()方法能够直接定位到元素，但是出现单链表后，单个bucket里存储的不是一个Entry，而是一个Entry链，系统只能必须按顺序遍历每个Entry，直到找到想搜索的Entry为止——如果恰好要搜索的Entry位于该Entry链的最末端（该Entry是最早放入该bucket中），那系统必须循环到最后才能找到该元素。

35.简单描述如何安装配置一个apache开源版hadoop，只描述即可，无需列出完整步骤，能列出步骤更好。

1)安装JDK并配置环境变量（/etc/profile）

2)关闭防火墙

3)配置hosts文件，方便hadoop通过主机名访问（/etc/hosts）

4)设置ssh免密码登录

5)解压缩hadoop安装包，并配置环境变量

6)修改配置文件（$HADOOP_HOME/conf）

hadoop-env.sh core-site.xml hdfs-site.xml mapred-site.xml

7)格式化hdfs文件系统（hadoop namenode -format）

8)启动hadoop （$HADOOP_HOME/bin/start-all.sh）

9)使用jps查看进程

36.请列出你所知道的hadoop调度器，并简要说明其工作方法。

1)默认调度器FIFO

hadoop中默认的调度器，采用先进先出的原则

2)计算能力调度器Capacity Scheduler

选择占用资源小，优先级高的先执行

3)公平调度器Fair Scheduler

同一队列中的作业公平共享队列中所有资源

以上.

听说，爱点赞的人运气都不会太差哦

如果有任何意见和建议，也欢迎在下方留言~

关注这个公众号，定期会有大数据学习的干货推送给你哦~