ComputerScience

温故而知新

阿里移动事业部面试总结

发表于 更新于 阅读次数： Valine：
本文字数： 11k 阅读时长 ≈ 10 分钟

谈谈python2和python3的区别

字符编码

py3中默认字符编码是UTF-8，因此使用Python3不需要文件顶部写‘# coding=utf-8’；

py2中默认字符编码是ASCII，如果文件中出现了中文，需要在顶部加入coding声明# coding=utf-8

注意：# coding=utf-8的=号两边不要空格。

1
2
3
4
5
6
py2: 
  　　- ascii 
 　　 文件头可以修改：#-*- encoding:utf-8 -*-
py3:
 　　 - utf-8
  　　文件头可以修改：#-*- encoding:utf-8 -*-

字符串类型

Python3：

str 对象和 bytes 对象可以使用 .encode() (str -> bytes) 或 .decode() (bytes -> str)方法相互转化。

从str到bytes，是编码, 比特流 = str(串, encoding=’utf-8’)

从bytes到str，是解码，串 = bytes(比特流, encoding=’utf-8’)

为什么英文显示是b’hello’呢，因为英文里，utf-8和ASCII是兼容的，所以只是显示为b’hello’，其实也是数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
## str --> bytes
tt = '奥德赛'
type(tt)

ss = bytes(tt, encoding='utf-8') # to bytes
type(ss)

rr = ss.decode("utf-8")          # to string
type(rr)

uu = str(ss, encoding='utf-8')   # to string
type(uu)

"""
output:
<class 'bytes'>
<class 'str'>
<class 'str'>
"""

可以使用encode()函数对字符串进行编码，转换成二进制字节数据，也可用decode()函数将字节解码成字符串；用decode()函数解码，英文可不要用指定编码格式，中文需要指定解码方式；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''中文编码'''
>>> a = '中文'
>>> type(a)
str
>>> b = a.encode(encoding='utf-8')
>>> b
b'\xe4\xb8\xad\xe6\x96\x87'

'''中文解码'''
>>> c = b.decode(encoding='utf-8')
>>> c
'中文'

'''可以省略解码格式'''
>>> d = b.decode()
>>> d
'中文'

Python2：

Python2中字符串有两种类型：unicode和str，前者表示文本字符串，后者表示字节序列，两者没有明显的界限。
如上所述，Python3中也有两种类型，str表示字符串，byte表示字节序列，任何需要写入文本或者网络传输的数据都只接收字节序列。

字符串：

1
2
3
4
5
6
7
py2: 
    unicode         v = u"root"    #本质上用unicode存储（万国码）
    (str/bytes)     v = "root"     #本质用字节存储
       
py3:         
    str             v = "root"     #本质上用unicode存储（万国码）
    bytes           v = b"root"    #本质上用字节存储

例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
>>> t = '存贮'
>>> t
'\xe5\xad\x98\xe8\xb4\xae'
>>> 
>>> type(t)
<type 'str'>
>>>  
>>> 
>>> t.encode(encoding='utf-8')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
UnicodeDecodeError: 'ascii' codec can't decode byte 0xe5 in position 0: ordinal not in range(128)
>>> 
>>> s = t.decode(encoding='utf-8')
>>> s
u'\u5b58\u8d2e'
>>>
>>> print(s)
存贮
>>> type(s)
<type 'unicode'>

补充知识（参考2）

原码：数值X的原码记为[x]原，如果机器字长为n(即采用n个二进制位表示数据)。则最高位是符号位。0表示正号，1表示负号，其余的n-1位表示数值的绝对值。数值零的原码表示有两种形式：[+0]原=0000 0000 ,-[0]原=1000 0000.

例子：若机器字长n等于8，则

1
2
3
[+1]原=0000 00001      [-1]原=1000 00001 
[+127]原=0111 1111     [-127]原=1111 1111
[+45]原=0010 1101      [-45]原=1010 1101

可见，原码，在计算数值上出问题了，当然，你也可以实验下，原码在计算正数和正数的时候，它是一点问题都没有的，但是出现负数的时候就出现问题了。所以才会有我下面将的问题：反码。

反码：数值X的反码记作[x]反，如果机器字长为n，则最高位是符号位，0表示正号，1表示负号，正数的反码与原码相同，负数的反码则是其绝对值按位求反。数值0的反码表示有两种形式：[+0]反=0000 0000 ,-[0]反=1111 1111.

例子：若机器字长n等于8，则

1
2
3
[+1]反=0000 00001      [-1]反=1111 1110 
[+127]反=0111 1111     [-127]反=1000 0000
[+45]反=0010 1101      [-45]反=1101 0010

在看反码计算的问题：

1
2
3
4
1+（-1）=0     |   (0000 0001)反+（1111 1110）反=（1111 1111）反=（1000 0000）原=【-0】 可以看到，虽然是-0，但是问题还不是很大。
1+（-2）=-1    |   (0000 0001）反+（1111 1101）反=（1111 1110）反=（1000 0001）原=【-1】 可以看到，没有问题。
(-1)+（2）=1   |   (1111 1110）反+（0000 0010）反=（0000 0000）反=（0000 0000）原=【0】 可以看到，问题发生了，因为溢出，导致结果变为0了。
所以，看以看到，用反码表示，问题依然没有解决，所以，出现了下面的补码。

补码：数值X的补码记作[x]补，如果机器字长为n，则最高位是符号位，0表示正号，1表示负号，正数的补码与原码反码都相同，负数的补码则等于其反码的末尾加1。数值0的补码表示有唯一的编码：[+0]补=0000 0000 ,-[0]补=0000 0000.

例子：若机器字长n等于8，则

1
2
3
[+1]补=0000 00001      [-1]补=1111 1111 
[+127]补=0111 1111     [-127]补=1000 0001
[+45]补=0010 1101      [-45]补=1101 0011

在看补码计算的问题：

1
2
3
1+（-1）=0        |      （0000 0001）补+（1111 1111）补=（0000 0000）补=（0000 0000）原=【0】 可以看到。没有问题
1+（-2）=-1       |      （0000 0001）补+（1111 1110）补=（1111 1111）补=（1000 0001）原=【-1】 可以看到，没有问题
-1+（2）=1        |      （1111 1111）补+（0000 0010）补=（0000 0001）补 =（0000 0001）原=【1】 可以看到，没有问题

通过上面的计算，我们发现，用补码的方式，就不存在在原码和反码中存在的计算问题了。其实，这也是计算机表达带符号整数用补码的原因。如果，你觉得我举得例子太少，缺少代表行，你可以自己试试。不过，放心补码一定是不会存在原码和反码的问题的。

缩进格式

1
2
3
4
Python2的缩进机制中，1个Tab和8个Space等价的，同时允许缩进中Tab和Space在代码中共存，但这种机制在部分IDE使用中有问题。

Python3中Tab和Space不再能共存，同时存在时会报错：
TabError: inconsistent use of tabs and spaces in indentation.
1
2
3
4
5
6
在python2中，print作为语句使用，而在python3中作为函数使用，exec同理：

print(“hello”,“world”)

在python2中则输出为一个元组；
在pyton3中输出为两个字符串，默认中间用空格隔开。

True和False用法

1
2
3
Python2中True和False都是全局变量，数值分别表示为1和0，因为是变量，所以存在可以被赋值的情况。

Python3中True和False是关键字，固定指向两个固定对象，不再允许被重新赋值。

小数和除法的用法

1
2
3
4
Python2中/作用就是整除，只输出整数，//是小数除法；
而在Python3中用//作为整除，/是小数除法。

实例：3/2在Python2中输出为1，在Python3中是1.5

小数和除法的用法

1
2
3
4
5
6
7
# Python2中/作用就是整除，只输出整数，//是小数除法；
# 在默认情况下，这两种运算符有很大的重叠地方，比如，当两个数都是整数的时候，两者的运算结果是没有区别的。如果想在python中让这两种有一个明确的分工。即"/"可以用于float除法，"//"用于整除法，我们可以在程序开始的时候做以下

from __future__ import division

#而在Python3中用//作为整除，/是小数除法。
#实例：3/2在Python2中输出为1，在Python3中是1.5

比较运算符的区别

1
2
3
Python2中任意两对象都可以比较。

Python3中只有同种数据类型对象可以比较。

nonlocal

1
在Python2中可以在函数中使用global声明变量为全局变量，但是给一个变量声明为非局部变量是无法实现的。在Python3，新增了关键字nonlocal，使得定义非局部变量成为了可能。

迭代器

1
2
3
4
Python2中很多返回列表对象的内置函数和方法。


在Python3中都改成了返回类似于迭代器的对象，迭代器的惰性求值特性使得操作大数据更加有效率。

for循环变量值区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#python2中，for循环会修改外部相同名称变量的值：

i = 1
print('comprehension: ', [i for i in range(5)])
print('after: i =', i)  #i=4
类似于Python3中：
i=1
for i in  range(5):
    print(i)
    print(i)          ##两次结果都是4


#Python3，for循环不会修改外部相同名称变量的值：
i = 1
print('comprehension: ', [i for i in range(5)])
print('after: i =', i) #i=1

[i for i in range(5)]生成的是一个链表

round函数返回值区别

1
2
3
4
5
Python3，round函数返回int类型值
  isinstance(round(15.5),int)   #True

Python2，round函数返回float类型值
  isinstance(round(15.5),float) #True

通过input()解析用户输入

1
2
3
4
Python3中input得到的为str；
Python2的input的到的为int型，Python2的raw_input得到的为str类型；

统一一下：Python3中用input，Python2中用row_input，都输入为str。

迭代器range和xrange

py3中的range == py2中的 xrange， 返回类似迭代器的东西，节省内存空间

语句变函数

py3中为print(), exec() 是一个方法，必须加上括号；

py2中为print, exec，是一个语句

数据传输

py3中socket传过来的数据是byte类型 / hashlib包update也需要传bytes类型的数据；

py2中则可以直接传入str, e.g

两数相除

py2中，1/2（两个整数相除）结果是0；

py3中是0.5了

python 2.2+ 以上都可以使用 from _future_ import division 实现改特性, 同时注意 // 取代了之前的 / 运算

print函数

Python3中print为一个函数，必须用括号括起来；

Python2中print为class。

对于一个dict，按其value值进行排序

1
2
3
4
5
6
7
8
## 按value排序，sorted()函数不会改变原来的对象，而是会返回一个新的已经排序好的对象；而sort则是在原位重新排列列表，会覆盖原有的列表。
sorted(d.items(), key=lambda item:item[1], reverse=True/False)

## 按value排序，并保存到一个新的列表中
[(k, v) for k, v in sorted(d.items(), key=lambda item:item[1], reverse=True/False)]

## 按value排序，并保存到一个新的dict中
[{k: v} for k, v in sorted(d.items(), key=lambda item:item[1], reverse=True/False)]

PS：不要与map混淆，map(function, iterable, …)是将function应用于iterable的每一个元素，结果以列表的形式返回。

窗口函数

窗口函数有以下功能：

1）同时具有分组和排序的功能

2）不减少原表的行数

3）语法如下：

1
2
<窗口函数> over (partition by <用于分组的列名>
                order by <用于排序的列名>)

题目

若一张表里面记录了一些用户的ID和其出行的城市信息，写一条SQL输出他出行最高频次的那条记录，表如下。

id city
10000 广州
10000 广州
10000 深圳
10001 广州
10001 深圳
10001 深圳

思路

1、先对该表出行记录汇总，计算出每个id对应出行city的次数；

1
SELECT id, city, count(*) AS ctime FROM travel GROUP BY id, city

2、对步骤1中的出行次数进行排序；

1
2
3
SELECT t1.id, t1.city, ctime, ROW_NUMBER() over ( PARTITION BY t1.id ORDER BY ctime DESC ) AS rank FROM

  (SELECT id, city, count(*) AS ctime FROM travel GROUP BY id, city ) AS t1

3、取出top 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
SELECT t2.id, t2.city FROM (

  SELECT t1.id, t1.city, ctime, ROW_NUMBER() over ( PARTITION BY t1.id ORDER BY ctime DESC ) AS rank FROM

  (SELECT id, city, count(*) AS ctime FROM travel GROUP BY id, city ) AS t1 

) AS t2

WHERE t2.rank = 1

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

WITH t2 AS (   
	WITH t1 AS (
    
	SELECT id, city, count(*) AS ctime FROM travel GROUP BY id, city 
	) 
	
    SELECT t1.id,	t1.city, ctime, ROW_NUMBER() over ( PARTITION BY t1.id ORDER BY ctime DESC ) AS rank FROM t1
	) 

	SELECT t2.id,	t2.city FROM t2 WHERE	t2.rank = 1


结果

id city
10000 广州
10001 深圳

总结

关于排序

Rank()：可查询出并列第一，是跳跃查询；两个第一名下来就是第三名；

Row_number()：是没有重复值的排序（即使两条记录相等也是不重复的），可以利用它来实现分页；

dense_rank()：连续排序，两个第二名仍然跟着第三名。

关于group by和over partition by的区别

group by分组汇总后改变表的行数，一行只有一个类别；

而over partition by分组汇总不会减少原表中的行数。

数据仓库的层

参考：数据仓库的基础知识

谈谈贝叶斯概率

贝叶斯公式

贝叶斯定理由英国数学家贝叶斯 (Thomas Bayes 1702-1761) 发展，用来描述两个条件概率之间的关系，比如 $P(A|B)$ 和$P(B|A)$。主要用于文本分类。

（1）条件概率公式

设A，B是两个事件，且$P(B)>0$，则在事件B发生的条件下，事件A发生的条件概率为：

（2）由条件概率公式得出乘法公式：$P(AB)=P(A|B)P(B)=P(B|A)P(A)$

也可变形为：

也可以这样来看贝叶斯公式：

  • 第一部分是先验概率$P(A)$，后一部分是“调整因子”。

  • P(A) 称为”先验概率”，即在B事件发生之前，我们对A事件概率的一个判断。

  • $P(A|B)$称为”后验概率”， 即在B事件发生之后，我们对A事件概率的重新评估。

  • $\frac{P(B|A)} {P(B)}$称为”可能性函数”，这是一个调整因子，使得预估概率更接近真实概率。

（3）全概率公式：

全概率公式的意义在于，当直接计算P(A)较为困难，而$P(B_i)$ 和$P(A|B_i)(i=1,2,\cdots)$的计算较为简单时，可以利用全概率公式计算$P(A)$。将事件A分解成几个小事件，通过求小事件的概率，然后相加从而求得事件A的概率。而将事件A进行分割的时候，不是直接对A进行分割，而是先找到样本空间Ω的一个个划分$B_1,B_2,\cdots,B_n$，这样事件A就被事件$AB_1,AB_2,\cdots,AB_n$分解成了n 部分。

即$A=AB_1+AB_2+…+AB_n$, 每一个$B_i$发生都可能导致A发生相应的概率是$P(A|B_i)$ ，由加法公式得：

垃圾邮件问题

垃圾邮件曾经是一个令人头痛的问题，长期困扰着邮件运营商和用户。据统计，用户收到的电子邮件中80%以上是垃圾邮件。

传统的垃圾邮件过滤方法，主要有”关键词法”和”校验码法”等。

关键词法的过滤依据是特定的词语，（如垃圾邮件的关键词：“发票”，“贷款”，“利率”，“中奖”，“办证”，“抽奖”，“号码”，“钱”，“款”，“幸运”……等等。）但这种方法效果很不理想，而且容易规避。一是正常邮件中也可能有这些关键词，非常容易误判。二是将关键词进行变形，如“代！开-发/票”，就很容易规避关键词过滤，如果将关键词的各种变形都找出来过滤，那是无穷无尽的，而且更容易误判正常邮件。

校验码法则是计算邮件文本的校验码，再与已知的垃圾邮件进行对比。它们的识别效果都不理想，而且很容易规避。

直到2002年，Paul Graham提出使用“贝叶斯方法”过滤垃圾邮件，经过几年的工程化应用，才算解决了这个问题。而这种方法的效果，好的不可思议。此外，这种过滤方法还具有自我学习能力，会根据新收到的邮件，不断调整。收到的垃圾邮件越多，它的准确率就越高。

  • 贝叶斯过滤器的使用过程

现在我们收到一封新邮件，我们假定它是 正常邮件 和 垃圾邮件的概率各是50%，即：

然后，对这封新邮件的内容进行解析，发现其中含有“发票”这个词，那么这封邮件属于垃圾邮件的概率提高到多少？其实就是计算一个条件概率，在有“发票”词语的条件下，邮件是垃圾邮件的概率：P(垃圾|发票)。直接计算肯定是无法计算了，这时要用到贝叶斯定理：

根据全概率公式：

所以：

其中，P(发票|垃圾) 表示所有垃圾邮件中出现“发票”的概率，我们假设100封垃圾邮件中有5封包含“发票”这个词，那么这个概率是5%。P(发票|正常) 表示所有正常邮件中出现“发票”的概率，我们假设1000封正常邮件中有1封包含“发票”这个词，那么这个概率是0.1%。于是：

因此，这封新邮件是垃圾邮件的概率是98%。从贝叶斯思维的角度，这个“发票”推断能力很强，直接将垃圾邮件50%的概率提升到98%了。那么，我们是否就此能给出结论：这是封垃圾邮件？

根据以上的“发票”关键词，我们不能给出结论说这是一封垃圾邮件。这里还有2个核心问题没有解决：

  • （1）P(发票|垃圾) 和 P(发票|正常)是我们假定的，怎样实际计算它们？

  • （2）正常邮件也是可能含有“发票”这个词，误判了怎么办？

建立历史资料库

贝叶斯过滤器是一种统计学过滤器，建立在已有的统计结果之上。所以，我们必须预先提供两组已经识别好的邮件，一组是正常邮件，另一组是垃圾邮件。

我们用这两组邮件，对过滤器进行”训练”。这两组邮件的规模越大，训练效果就越好。Paul Graham使用的邮件规模，是正常邮件和垃圾邮件各4000封。

“训练”过程很简单。首先，解析所有邮件，提取每一个词。然后，计算每个词语在正常邮件和垃圾邮件中的出现频率。

比如，我们假定”贷款”这个词，在4000封垃圾邮件中，有200封包含这个词，那么它的出现频率就是5%；而在4000封正常邮件中，只有2封包含这个词，那么出现频率就是0.05%。（【注释】如果某个词只出现在垃圾邮件中，Paul Graham就假定，它在正常邮件的出现频率是1%，反之亦然。这样做是为了避免概率为0。随着邮件数量的增加，计算结果会自动调整。）

有了这个初步的统计结果，概率值计算问题就解决了。过滤器就可以投入使用了。

联合概率的计算

对于误判问题，可以采用“多特征判断”的思路，就像猫和老虎，如何单看颜色，花纹都不好判断，那就颜色、花纹、大小、体重等一起来判断。

同理，对于“发票”不好来判断，那就联合其他词语一起来判断，如果这封邮件中除了“发票”，还有“常年”，“代开”，“各种”，“行业”，“绝对正规”，“税点低”等词语，那么就通过这些词语联合认定这封邮件是垃圾邮件。

在基本方法计算的基础上，选取前n个（例如n=3，实际应用中是15个词/字以上）概率最高的词，假设为：“发票”，“常年”，“代开”。然后计算其联合条件概率。即在这3个词同时出现的条件下，这是一封垃圾邮件的概率。

即：P(垃圾|发票;常年;代开)，这时仍要用到贝叶斯定理：

这里假设：所有词语彼此之间是不相关的（严格说这个假设不成立；实际上各词语之间不可能完全没有相关性，但可以忽略）。

所以：

由于上式中右边的分母不太好求。我们可以求这封邮件是正常邮件的概率：

上面两个式子相除，得到：

即在这3个词同时出现的情况下，属于垃圾邮件的概率与属于正常邮件的概率的比值。上边式子中的每一项，都可以用前面介绍的统计学方法得到。 假设：

那么上式比值为2500，即多个词（或字）联合认定，这封邮件是垃圾邮件的概率是正常邮件概率的2500倍，可以确定是垃圾邮件了。

讲讲AC自动机算法，与KMP的区别

讲讲stacking，如果stacking若干模型后没有提升，可能的原因有哪些

Reference:

1、Python3中的bytes和str类型

2、数据在计算机中的存储形式和运算

3、贝叶斯

------ 本文结束------
Donate comment here.

欢迎关注我的其它发布渠道