Introduction

Alternate Implementations

用过哪些python解释器
问C JAVA python有什么不同
python和C++、Java的区别是什么？python有编译吗？
python中交换两个数值
提高python运行效率的方法

basic concepts

列出几种魔法方法并简要介绍用途
C:\Users\ry-wu.junya\Desktop>python 1.py 22 33命令行启动程序并传参，print(sys.argv)会输出什么数据？文件名和参数构成的列表
单引号、双引号、三引号用法
print(0+”0”)会不会报错，为什么
Python的引用赋值、深拷贝和浅拷贝怎么理解
递归太深会怎样？答栈溢出。为什么会栈溢出？python函数中的临时变量存在哪？那很深的时候，用循环会怎样呢？为什么不会栈溢出？
python里is和==的区别？a=1，b=1，a is b是啥？python会缓存什么？
编译型和解释型语言的区别
常用的python库
Python自省isinstance
鸭子类型
Python为什么不需要函数重载
Python中的作用域和搜索顺序
Python的is

Built-in Functions

filter方法求出列表所有奇数并构造新列表，a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
举例说明zip()函数用法
zip函数功能
求三个方法打印结果: comma-separated, percentage, format method
简述any()和all()方法
r、r+、rb、rb+文件打开模式区别
说出你常用的几个库；说出几个比较难得内置函数
map reduce原理, 多个reduce的输出，但是要统计的是uv，怎么弄
open和with open的区别，平常用哪个比较多
read,readline和readlines

Built-in Types

保留两位小数
8转二进制

Built-in Exceptions

IOError、AttributeError、ImportError、IndentationError、IndexError、KeyError、SyntaxError、NameError分别代表什么异常
写一段自定义异常代码
举例说明异常模块中try except else finally的相关意义
python异常处理(try,except,else,catch,finally,raise)；

The Python Data Model

生成0-100的随机数

Data structures

python可变对象不可变对象
list和tuple的区别
list去重
list和字典的区别，有序和无序
python的list底层是怎么实现的？各种操作复杂度？
python字典和json字符串相互转化方法
列表嵌套元组，分别按字母和数字排序
元组列表区别;
列表嵌套列表排序，年龄数字相同怎么办？
根据键对字典排序(方法一，zip函数)
根据键对字典排序(方法二,不用zip)
列表推导式、字典推导式、生成器
根据字符串长度排序，看排序是否灵活运用
举例sort和sorted对列表排序，list=[0,-1,3,-10,5,9]
对list排序foo = [-5,8,0,4,9,-4,-20,-2,8,2,-4],使用lambda函数从小到大排序
列表嵌套字典的排序，分别根据年龄和姓名排序
[[1,2],[3,4],[5,6]]一行代码展开该列表，得出[1,2,3,4,5,6]
x=”abc”,y=”def”,z=[“d”,”e”,”f”],分别求出x.join(y)和x.join(z)返回的结果
[1,2,3]+[4,5,6]的结果是多少？
使用pop和del删除字典中的”name”字段，dic={“name”:”zs”,”age”:18}
python中copy和deepcopy区别
求两个列表的交集、差集、并集
lambda匿名函数好处
python中list和tuple有什么区别？怎么转化？
python的dict 底层是什么 哈希算法
Python dict 底层实现（哈希表）
字典、元组、列表的in方法哪个更快
如何更新字典，如果key有重复用哪个value
如何合并两个list
list如何快速去重
字典树
判断字典键是否存在有几种方法。好像是有三种。
字典怎么删除键值
字典推导式

Text versus bytes

a = ” hehheh “,去除收尾空格
正则表达式匹配中，(.)和(.?)匹配区别？
s=”info:xiaoZhang 33 shandong”,用正则切分字符串输出[‘info‘, ‘xiaoZhang‘, ‘33‘, ‘shandong‘]
正则匹配以163.com结尾的邮箱
正则re.complie作用
a=”hello”和b=”你好”编码成bytes类型
a=”张明 98分”，用re.sub，将98替换为100
python正则中search和match
问了字符串反转
Python 中 search 和 match 的区别？他们扫描开始的位置有什么区别？
正則.*和.*?的区别
正则表达式 .*是什么意思，*是什么意思
search和match区别

match()函数只检测字符串开头位置是否匹配，匹配成功才会返回结果，否则返回None search()函数会在整个字符串内查找模式匹配,只到找到第一个匹配然后返回一个包含匹配信息的对象

String类型和char类型数据的区别。

Functions as objects

First-class functions

python传参数是传值还是传址？
类变量与实例变量
递归求和
python 参数 *和**区别
你能写一个递归函数吗？随便一个场景说一下
super

Higher-order functions

高阶函数

Design patterns

多种方法实现单例模式

Function decorators and closures

python装饰器

装饰器（用函数实现，和类实现）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def f1(func):
    def f2(*args,**kwargs):
        ...
        return func(*args,**kwargs)
    return f2

class fn1:
    def __init__(self,func):
        self.func=func
    def __call__(self, *args, **kwargs):
        ...
        return self.func(*args,**kwargs)

装饰器处理异常并且记录（没太理解，用的try expect）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def h1(func):
    def h2(*args,**kwargs):
        try:
            return func(*args,**kwargs)
        except Exception as e:
            print(e)
@h1
def test():
    list=[]
    return list[100]
test()
python的闭包
泛型什么意思
面向对象编程和面向切面编程
说一下你对修饰器和@的认识
python装饰器，输入类型和输出类型
functools.wraps的原理
装饰器是什么？装饰器中的变量是放在哪的呢？
python装饰器、有参数的装饰器和没参数的装饰器有什么区别
装饰器有用过吗？能大概说一下怎么定义一个装饰器吗？定义完装饰器以后怎么使用它？

Object Oriented Idioms

Classes

class中的self
__init__和__new__的区别
Python中单下划线和双下划线
新式类和旧式类 - 多继承时子类调用通过深度优先查找继承而来的方法

Object references, mutability and recycling

python的多态怎么实现的，装饰器和可变参数、关键字参数

A Pythonic object

实例方法、类方法、静态方法
反射是什么

Inheritance

python的多继承

Control flow

Iterables, iterators and generators

range(100) 是什么意思？
生成器，感觉主要就是问面向对象相关的
请将[i for i in range(3)]改成生成器

迭代器、生成器、装饰器

python的迭代器和生成器，有什么区别和特性
迭代器自带方法(next);

Coroutines

协程
协程写过吗
go和python的协程
python协程怎么使用

Concurrency with futures

GIL是什么？为什么有GIL？
Python GIL，如何解决
python死锁怎么处理？怎么避免
python的计算密集和IO密集任务
Python多进程和多线程在哪些情况下使用
什么是阻塞？Blocking I/O
python如何利用多核（多进程就可以啦）
Python多线程和多进程的区别？
python多线程有什么情况适用
Python线程寫法
线程接收web高并发
python进程/线程/协程example
python的多线程可以么？python有GIL，为什么多线程还生效？

Concurrency with asyncio

那python里面有没有其他异步方式

subprocess — Subprocess management

python执行Linux命令

Generic Operating System Services

用python删除文件和用linux命令删除文件方法
log日志中，我们需要用时间戳记录error,warning等的发生时间，请用datetime模块打印当前时间戳 “2018-04-01 11:38:54”

Python Runtime

garbage collection

python引用计数机制
python垃圾回收机制
python的内存管理
python分代回收中的数据结构
python中的回收对象怎么快速确定内存位置
python回收内存溢出情况，怎么检查以及处理

atexit — Exit handlers

atexit

Metaprogramming

metaclass、args、kwargs
什么是python元类

Development Tools

unit test用例的执行顺序

Debugging and Profiling

如何计算多个函数花费的时间

Differences between Python 2 & 3

python的xrang和rang区别
Python 2 和 Python 3 的区别有哪些？
迭代器是 Python 2 还是 Python 3的？

Others

python，使用过的包，用过哪些python的库

Algorithms

用Python实现一个二分查找

Scrapy

爬取数据的时候遇到了什么反爬虫情况？你了解有哪些反爬虫机制？

Web

什么wsgi

Django

Django和flask区别
简述Django的orm
ORM的查询与数据库是怎么交互的，我说了操作，他问我底层是怎么实现的呢
Django有什么模块？
ORM语句（模糊查询，Like）
ORM有什么优点和缺点
Django中客户端发送过来的请求如何处理，返回一个什么对象

Flask

说一下Flask架构
gevent你是怎么使用的？
Flask与wsgi是如何交互的？
Flask源码读过么？
Flask的IO多路复用用在了什么地方？
Flask的context、threadlocal

Plot

请列出你会的任意一种统计图(条形图、折线图等)绘制的开源库，第三方也行
Python画图都用过哪些模块，画过哪些图？

File

python中读取Excel文件的方法

Text

平时有用到 Python 的文本开发环境吗？NLTK, spacy

RPC

如何测试rpc服务的并发量。Thrift有什么优缺点。

Databases

index的作用

Computer Organization

内存中堆和栈的区别？临时变量放哪？
问程序在计算机中运行时的全部底层构成，就是堆、栈、程序计数器、寄存器这些的

Network

命令的方式抓包

通过本场 Chat，你将获得如下知识点：

  • 掌握 Python 的基础语法
  • 语法常见的 Python 应用场景
  • 掌握 Python 闭包的使用以及装饰器的使用
  • 生成器和迭代器的使用
  • 常见的设计模式的使用
  • 深浅拷贝的区别
  • 线程、进程、协程的使用
  • 了解 Python 中的元编程和反射
  • 常考的数据结构和算法
  • 爬虫相关知识，网络编程基本知识等

所有题目

语言特性

1.谈谈对 Python 和其他语言的区别 2.简述解释型和编译型编程语言 3.Python 的解释器种类以及相关特点？ 4.说说你知道的Python3 和 Python2 之间的区别？ 5.Python3 和 Python2 中 int 和 long 区别？ 6.xrange 和 range 的区别？

编码规范

7.什么是 PEP8? 8.了解 Python 之禅么？ 9.了解 dosctring 么？ 10.了解类型注解么？ 11.例举你知道 Python 对象的命名规范，例如方法或者类等 12.Python 中的注释有几种？ 13.如何优雅的给一个函数加注释？ 14.如何给变量加注释？ 15.Python 代码缩进中是否支持 Tab 键和空格混用。 16.是否可以在一句 import 中导入多个库? 17.在给 Py 文件命名的时候需要注意什么? 18.例举几个规范 Python 代码风格的工具

数据类型

字符串

19.列举 Python 中的基本数据类型？ 20.如何区别可变数据类型和不可变数据类型 21.将"hello world"转换为首字母大写"Hello World" 22.如何检测字符串中只含有数字? 23.将字符串"ilovechina"进行反转 24.Python 中的字符串格式化方式你知道哪些？ 25.有一个字符串开头和末尾都有空格，比如“ adabdw ”,要求写一个函数把这个字符串的前后空格都去掉。 26.获取字符串”123456“最后的两个字符。 27.一个编码为 GBK 的字符串 S，要将其转成 UTF-8 编码的字符串，应如何操作？ 28.s=“info:xiaoZhang 33 shandong”,用正则切分字符串输出[‘info’, ‘xiaoZhang’, ‘33’, ‘shandong’] 27.怎样将字符串转换为小写？ 28.单引号、双引号、三引号的区别？ 29.a = “你好 中国 “,去除多余空格只留一个空格。

列表

30.已知 AList = [1,2,3,1,2],对 AList 列表元素去重，写出具体过程。 31.如何实现 “1,2,3” 变成 [“1”,“2”,“3”] 32.给定两个 list，A 和 B，找出相同元素和不同元素 33.[[1,2],[3,4],[5,6]]一行代码展开该列表，得出[1,2,3,4,5,6] 34.合并列表[1,5,7,9]和[2,2,6,8] 35.如何打乱一个列表的元素？

字典

36.字典操作中 del 和 pop 有什么区别 37.按照字典的内的年龄排序

1
2
3
4
5

d1 = [
    {'name':'alice', 'age':38},
    {'name':'bob', 'age':18},
    {'name':'Carl', 'age':28},
]

38.请合并下面两个字典 a = {“A”:1,“B”:2},b = {“C”:3,“D”:4} 39.如何使用生成式的方式生成一个字典，写一段功能代码。 40.如何把元组(“a”,“b”)和元组(1,2)，变为字典{“a”:1,“b”:2}

综合

41.Python 常用的数据结构的类型及其特性？

1
2
3
4

A：{1:0,2:0,3:0}
B：{"a":0, "b":0, "c":0}
C: {(1,2):0, (2,3):0}
D: {[1,2]:0, [2,3]:0}

42.如何将元组(“A”,“B”)和元组(1,2),合并成字典{“A”:1,“B”:2} 43.Python 里面如何实现 tuple 和 list 的转换？ 44.我们知道对于列表可以使用切片操作进行部分元素的选择，那么如何对生成器类型的对象实现相同的功能呢？ 45.请将[i for i in range(3)]改成生成器 46.a=“hello"和 b=“你好"编码成 bytes 类型 47.下面的代码输出结果是什么？

1
2

a = (1,2,3,[4,5,6,7],8)
a[2] = 2

48.下面的代码输出的结果是什么?

1
2

a = (1,2,3,[4,5,6,7],8)
a[5] = 2

操作类题目

49.Python 交换两个变量的值 50.在读文件操作的时候会使用 read、readline 或者 readlines，简述它们各自的左右 51.json 序列化时，可以处理的数据类型有哪些？如何定制支持 datetime 类型？ 52.json 序列化时，默认遇到中文会转换成 unicode，如果想要保留中文怎么办？ 53.有两个磁盘文件 A 和 B，各存放一行字母，要求把这两个文件中的信息合并(按字母顺序排列)，输出到一个新文件 C 中。 54.如果当前的日期为 20190530，要求写一个函数输出 N 天后的日期，(比如 N 为 2，则输出 20190601)。 55.写一个函数，接收整数参数 n，返回一个函数，函数的功能是把函数的参数和 n 相乘并把结果返回。 56.下面代码会存在什么问题，如何改进？

1
2
3
4
5

def strappend(num):
    str='first'
    for i in range(num):
        str+=str(i)
    return str

57.一行代码输出 1-100 之间的所有偶数。 58.with 语句的作用，写一段代码？ 59.python 字典和 json 字符串相互转化方法 60.请写一个 Python 逻辑，计算一个文件中的大写字母数量

高级特效

70.函数装饰器有什么作用？请列举说明？ 71.Python 垃圾回收机制？ 72.魔法函数 __call__怎么使用? 73.如何判断一个对象是函数还是方法？ 74.@classmethod 和@staticmethod 用法和区别 75.Python 中的接口如何实现？ 76.Python 中的反射了解么? 77.metaclass 作用？以及应用场景？ 78.hasattr() getattr() setattr()的用法 79.请列举你知道的 Python 的魔法方法及用途。 80.如何知道一个 Python 对象的类型？ 81.Python 的传参是传值还是传址？ 82.Python 中的元类(metaclass)使用举例 83.简述 any()和 all()方法 84.filter 方法求出列表所有奇数并构造新列表，a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 85.什么是猴子补丁？ 86.在 Python 中是如何管理内存的？ 87.当退出 Python 时是否释放所有内存分配？

正则表达式

88.使用正则表达式匹配出

www.baidu.com中的地址 a=“张明 98 分”，用 re.sub，将 98 替换为 100 89.正则表达式匹配中(.)和(.?)匹配区别？ 90.写一段匹配邮箱的正则表达式

其他内容

91.解释一下 python 中 pass 语句的作用？ 92.简述你对 input()函数的理解 93.python 中的 is 和== 94.Python 中的作用域 95.三元运算写法和应用场景？ 96.了解 enumerate 么？ 97.列举 5 个 Python 中的标准模块 98.如何在函数中设置一个全局变量 99.pathlib 的用法举例 100.Python 中的异常处理，写一个简单的应用场景 101.Python 中递归的最大次数，那如何突破呢？ 102.什么是面向对象的 mro 103.isinstance 作用以及应用场景？ 104.什么是断言？应用场景？ 105.lambda 表达式格式以及应用场景？ 106.新式类和旧式类的区别 107.dir()是干什么用的？ 108.一个包里有三个模块，demo1.py, demo2.py, demo3.py，但使用 from tools import 导入模块时，如何保证只有 demo1、demo3 被导入了。 109.列举 5 个 Python 中的异常类型以及其含义 110.copy 和 deepcopy 的区别是什么？ 111.代码中经常遇到的args, **kwargs 含义及用法。 112.Python 中会有函数或成员变量包含单下划线前缀和结尾，和双下划线前缀结尾，区别是什么? 113.w、a+、wb 文件写入模式的区别 114.举例 sort 和 sorted 的区别 115.什么是负索引？ 116.pprint 模块是干什么的？ 117.解释一下 Python 中的赋值运算符 118.解释一下 Python 中的逻辑运算符 119.讲讲 Python 中的位运算符 120.在 Python 中如何使用多进制数字？ 121.怎样声明多个变量并赋值？

算法和数据结构

122.已知：

1
2

AList = [1,2,3]
BSet = {1,2,3}

(1) 从 AList 和 BSet 中 查找 4，最坏时间复杂度那个大？ (2) 从 AList 和 BSet 中 插入 4，最坏时间复杂度那个大？ 123.用 Python 实现一个二分查找的函数 124.python 单例模式的实现方法 125.使用 Python 实现一个斐波那契数列 126.找出列表中的重复数字 127.找出列表中的单个数字 128.写一个冒泡排序 129.写一个快速排序 130.写一个拓扑排序 131.python 实现一个二进制计算 132.有一组“+”和“-”符号，要求将“+”排到左边，“-”排到右边，写出具体的实现方法。 133.单链表反转 134.交叉链表求交点 135.用队列实现栈 136.找出数据流的中位数 137.二叉搜索树中第 K 小的元素

爬虫相关

138.在 requests 模块中，requests.content 和 requests.text 什么区别 139.简要写一下 lxml 模块的使用方法框架 140.说一说 scrapy 的工作流程 141.scrapy 的去重原理 142.scrapy 中间件有几种类，你用过哪些中间件 143.你写爬虫的时候都遇到过什么？反爬虫措施，你是怎么解决的？ 144.为什么会用到代理？ 145.代理失效了怎么处理？ 146.列出你知道 header 的内容以及信息 147.说一说打开浏览器访问 www.baidu.com 获取到结果，整个流程。 148.爬取速度过快出现了验证码怎么处理 149.scrapy 和 scrapy-redis 有什么区别？为什么选择 redis 数据库？ 150.分布式爬虫主要解决什么问题 151.写爬虫是用多进程好？还是多线程好？为什么？ 152.解析网页的解析器使用最多的是哪几个 153.需要登录的网页，如何解决同时限制 ip，cookie,session（其中有一些是动态生成的）在不使用动态爬取的情况下？ 154.验证码的解决（简单的：对图像做处理后可以得到的，困难的：验证码是点击，拖动等动态进行的？） 155.使用最多的数据库（mysql，mongodb，redis 等），对他的理解？

网络编程

156.TCP 和 UDP 的区别？ 157.简要介绍三次握手和四次挥手 158.什么是粘包？socket 中造成粘包的原因是什么？哪些情况会发生粘包现象？

并发

159.举例说明 conccurent.future 的中线程池的用法 160.说一说多线程，多进程和协程的区别。 161.简述 GIL 162.进程之间如何通信 163.IO 多路复用的作用？ 164.select、poll、epoll 模型的区别？ 165.什么是并发和并行？ 167.解释什么是异步非阻塞？ 168.threading.local 的作用？

Git 面试题

169.说说你知道的 git 命令 170.git 如何查看某次提交修改的内容x

Table of Contents

Python语言特性

1 Python的函数参数传递

看两个例子:

1
2
3
4
5

a = 1
def fun(a):
    a = 2
fun(a)
print a  # 1

1
2
3
4
5

a = []
def fun(a):
    a.append(1)
fun(a)
print a  # [1]

所有的变量都可以理解是内存中一个对象的“引用”，或者，也可以看似c中void*的感觉。

通过id来看引用a的内存地址可以比较理解：

1
2
3
4
5
6
7
8

a = 1
def fun(a):
    print "func_in",id(a)   # func_in 41322472
    a = 2
    print "re-point",id(a), id(2)   # re-point 41322448 41322448
print "func_out",id(a), id(1)  # func_out 41322472 41322472
fun(a)
print a  # 1

注：具体的值在不同电脑上运行时可能不同。

可以看到，在执行完a = 2之后，a引用中保存的值，即内存地址发生变化，由原来1对象的所在的地址变成了2这个实体对象的内存地址。

而第2个例子a引用保存的内存值就不会发生变化：

1
2
3
4
5
6
7

a = []
def fun(a):
    print "func_in",id(a)  # func_in 53629256
    a.append(1)
print "func_out",id(a)     # func_out 53629256
fun(a)
print a  # [1]

这里记住的是类型是属于对象的，而不是变量。而对象有两种,“可更改”（mutable）与“不可更改”（immutable）对象。在python中，strings, tuples, 和numbers是不可更改的对象，而 list, dict, set 等则是可以修改的对象。分别作为参数传递有不同效果。(这就是这个问题的重点)

当一个引用传递给函数的时候,函数自动复制一份引用,这个函数里的引用和外边的引用没有半毛关系了.所以第一个例子里函数把引用指向了一个不可变对象,当函数返回的时候,外面的引用没半毛感觉.而第二个例子就不一样了,函数内的引用指向的是可变对象,对它的操作就和定位了指针地址一样,在内存里进行修改.

如果还不明白的话,这里有更好的解释: http://stackoverflow.com/questions/986006/how-do-i-pass-a-variable-by-reference

2 Python中的元类(metaclass)

这个非常的不常用,但是像ORM这种复杂的结构还是会需要的,详情请看:http://stackoverflow.com/questions/100003/what-is-a-metaclass-in-python

3 @staticmethod和@classmethod

Python其实有3个方法,即静态方法(staticmethod),类方法(classmethod)和实例方法,如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def foo(x):
    print "executing foo(%s)"%(x)

class A(object):
    def foo(self,x):
        print "executing foo(%s,%s)"%(self,x)

    @classmethod
    def class_foo(cls,x):
        print "executing class_foo(%s,%s)"%(cls,x)

    @staticmethod
    def static_foo(x):
        print "executing static_foo(%s)"%x

a=A()

这里先理解下函数参数里面的self和cls.这个self和cls是对类或者实例的绑定,对于一般的函数来说我们可以这么调用foo(x),这个函数就是最常用的,它的工作跟任何东西(类,实例)无关.对于实例方法,我们知道在类里每次定义方法的时候都需要绑定这个实例,就是foo(self, x),为什么要这么做呢?因为实例方法的调用离不开实例,我们需要把实例自己传给函数,调用的时候是这样的a.foo(x)(其实是foo(a, x)).类方法一样,只不过它传递的是类而不是实例,A.class_foo(x).注意这里的self和cls可以替换别的参数,但是python的约定是这俩,还是不要改的好.

对于静态方法其实和普通的方法一样,不需要对谁进行绑定,唯一的区别是调用的时候需要使用a.static_foo(x)或者A.static_foo(x)来调用.

\ 实例方法 类方法 静态方法
a = A() a.foo(x) a.class_foo(x) a.static_foo(x)
A 不可用 A.class_foo(x) A.static_foo(x)

更多关于这个问题:

  1. http://stackoverflow.com/questions/136097/what-is-the-difference-between-staticmethod-and-classmethod-in-python
  2. https://realpython.com/blog/python/instance-class-and-static-methods-demystified/

4 类变量和实例变量

类变量：

​ 是可在类的所有实例之间共享的值（也就是说，它们不是单独分配给每个实例的）。例如下例中，num_of_instance 就是类变量，用于跟踪存在着多少个Test 的实例。

实例变量：

实例化之后，每个实例单独拥有的变量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Test(object):  
    num_of_instance = 0  
    def __init__(self, name):  
        self.name = name  
        Test.num_of_instance += 1  
  
if __name__ == '__main__':  
    print Test.num_of_instance   # 0
    t1 = Test('jack')  
    print Test.num_of_instance   # 1
    t2 = Test('lucy')  
    print t1.name , t1.num_of_instance  # jack 2
    print t2.name , t2.num_of_instance  # lucy 2

补充的例子

1
2
3
4
5
6
7
8
9

class Person:
    name="aaa"

p1=Person()
p2=Person()
p1.name="bbb"
print p1.name  # bbb
print p2.name  # aaa
print Person.name  # aaa

这里p1.name="bbb"是实例调用了类变量,这其实和上面第一个问题一样,就是函数传参的问题,p1.name一开始是指向的类变量name="aaa",但是在实例的作用域里把类变量的引用改变了,就变成了一个实例变量,self.name不再引用Person的类变量name了.

可以看看下面的例子:

1
2
3
4
5
6
7
8
9

class Person:
    name=[]

p1=Person()
p2=Person()
p1.name.append(1)
print p1.name  # [1]
print p2.name  # [1]
print Person.name  # [1]

参考:http://stackoverflow.com/questions/6470428/catch-multiple-exceptions-in-one-line-except-block

5 Python自省

这个也是python彪悍的特性.

自省就是面向对象的语言所写的程序在运行时,所能知道对象的类型.简单一句就是运行时能够获得对象的类型.比如type(),dir(),getattr(),hasattr(),isinstance().

1
2
3
4
5

a = [1,2,3]
b = {'a':1,'b':2,'c':3}
c = True
print type(a),type(b),type(c) # <type 'list'> <type 'dict'> <type 'bool'>
print isinstance(a,list)  # True

6 字典推导式

可能你见过列表推导时,却没有见过字典推导式,在2.7中才加入的:

1

d = {key: value for (key, value) in iterable}

7 Python中单下划线和双下划线

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

>>> class MyClass():
...     def __init__(self):
...             self.__superprivate = "Hello"
...             self._semiprivate = ", world!"
...
>>> mc = MyClass()
>>> print mc.__superprivate
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: myClass instance has no attribute '__superprivate'
>>> print mc._semiprivate
, world!
>>> print mc.__dict__
{'_MyClass__superprivate': 'Hello', '_semiprivate': ', world!'}

__foo__:一种约定,Python内部的名字,用来区别其他用户自定义的命名,以防冲突，就是例如__init__(),__del__(),__call__()这些特殊方法

_foo:一种约定,用来指定变量私有.程序员用来指定私有变量的一种方式.不能用from module import * 导入，其他方面和公有一样访问；

__foo:这个有真正的意义:解析器用_classname__foo来代替这个名字,以区别和其他类相同的命名,它无法直接像公有成员一样随便访问,通过对象名._类名__xxx这样的方式可以访问.

详情见:http://stackoverflow.com/questions/1301346/the-meaning-of-a-single-and-a-double-underscore-before-an-object-name-in-python

或者: http://www.zhihu.com/question/19754941

8 字符串格式化:%和.format

.format在许多方面看起来更便利.对于%最烦人的是它无法同时传递一个变量和元组.你可能会想下面的代码不会有什么问题:

1

"hi there %s" % name

但是,如果name恰好是(1,2,3),它将会抛出一个TypeError异常.为了保证它总是正确的,你必须这样做:

1

"hi there %s" % (name,)   # 提供一个单元素的数组而不是一个参数

但是有点丑..format就没有这些问题.你给的第二个问题也是这样,.format好看多了.

你为什么不用它?

  • 不知道它(在读这个之前)
  • 为了和Python2.5兼容(譬如logging库建议使用%(issue #4))

http://stackoverflow.com/questions/5082452/python-string-formatting-vs-format

9 迭代器和生成器

这个是stackoverflow里python排名第一的问题,值得一看: http://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python

这是中文版: http://taizilongxu.gitbooks.io/stackoverflow-about-python/content/1/README.html

这里有个关于生成器的创建问题面试官有考： 问： 将列表生成式中[]改成() 之后数据结构是否改变？ 答案：是，从列表变为生成器

1
2
3
4
5
6

>>> L = [x*x for x in range(10)]
>>> L
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
>>> g = (x*x for x in range(10))
>>> g
<generator object <genexpr> at 0x0000028F8B774200>

通过列表生成式，可以直接创建一个列表。但是，受到内存限制，列表容量肯定是有限的。而且，创建一个包含百万元素的列表，不仅是占用很大的内存空间，如：我们只需要访问前面的几个元素，后面大部分元素所占的空间都是浪费的。因此，没有必要创建完整的列表（节省大量内存空间）。在Python中，我们可以采用生成器：边循环，边计算的机制—>generator

1
2

>>> mylist = [x*x for x in range(3)]        # Iterables
>>> mygenerator = (x*x for x in range(3))     # Generators

It is just the same except you used () instead of []. BUT, you cannot perform for i in my generator a second time since generators can only be used once

Yield is a keyword that is used like return, except the function will return a generator.

The generator is considered empty once the function runs but does not hit yield anymore. It can be because the loop had come to an end, or because you do not satisfy an “if/else” anymore.

1
2
3
4
5
6
7
8
9

>>> class Bank(): # 让我们建个银行,生产许多ATM
...  crisis = False
...  def create_atm(self):
...    while not self.crisis:
...      yield "$100"

>>> hsbc = Bank() 
>>> corner_street_atm = hsbc.create_atm()
>>> print([corner_street_atm.next() for cash in range(5)])

**生成器：**带有yield的函数不再是一个普通函数，而是一个生成器。当函数被调用时，返回一个生成器对象。不像一般函数在生成值后退出，生成器函数在生成值后会自动挂起并暂停他们的执行状态。

10 *args and **kwargs

用*args和**kwargs只是为了方便并没有强制使用它们.

当你不确定你的函数里将要传递多少参数时你可以用*args.例如,它可以传递任意数量的参数:

1
2
3
4
5
6
7
8

>>> def print_everything(*args):
        for count, thing in enumerate(args):
...         print '{0}. {1}'.format(count, thing)
...
>>> print_everything('apple', 'banana', 'cabbage')
0. apple
1. banana
2. cabbage

相似的,**kwargs允许你使用没有事先定义的参数名:

1
2
3
4
5
6
7

>>> def table_things(**kwargs):
...     for name, value in kwargs.items():
...         print '{0} = {1}'.format(name, value)
...
>>> table_things(apple = 'fruit', cabbage = 'vegetable')
cabbage = vegetable
apple = fruit

你也可以混着用.命名参数首先获得参数值然后所有的其他参数都传递给*args和**kwargs.命名参数在列表的最前端.例如:

1

def table_things(titlestring, **kwargs)

*args和**kwargs可以同时在函数的定义中,但是*args必须在**kwargs前面.

当调用函数时你也可以用*和**语法.例如:

1
2
3
4
5
6
7

>>> def print_three_things(a, b, c):
...     print 'a = {0}, b = {1}, c = {2}'.format(a,b,c)
...
>>> mylist = ['aardvark', 'baboon', 'cat']
>>> print_three_things(*mylist)

a = aardvark, b = baboon, c = cat

就像你看到的一样,它可以传递列表(或者元组)的每一项并把它们解包.注意必须与它们在函数里的参数相吻合.当然,你也可以在函数定义或者函数调用时用*.

http://stackoverflow.com/questions/3394835/args-and-kwargs

11 面向切面编程AOP和装饰器

这个AOP一听起来有点懵,同学面阿里的时候就被问懵了…

装饰器是一个很著名的设计模式，经常被用于有切面需求的场景，较为经典的有插入日志、性能测试、事务处理等。装饰器是解决这类问题的绝佳设计，有了装饰器，我们就可以抽离出大量函数中与函数功能本身无关的雷同代码并继续重用。概括的讲，装饰器的作用就是为已经存在的对象添加额外的功能。

装饰器是一个工厂函数，接受一个函数作为参数，然后返回一个新函数，其闭包中包含被装饰的函数。有了装饰器，可以提取大量函数中与本身功能无关的类似代码 ( 这块在Flask中用于定义路由的@app.route，就是一个很好的例子)，达到代码重用的目的。可应用于插入日志、性能测试、事务处理等方面。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def deco(func):
    def warpper(*args, **kwargs):
        print('start')
        func(*args, **kwargs)
        print('end')
    return warpper
@deco
def myfunc(parameter):
    print("run with %s" % parameter)
myfunc("something")

这个问题比较大,推荐: http://stackoverflow.com/questions/739654/how-can-i-make-a-chain-of-function-decorators-in-python

中文: http://taizilongxu.gitbooks.io/stackoverflow-about-python/content/3/README.html

12 鸭子类型

“当看到一只鸟走起来像鸭子、游泳起来像鸭子、叫起来也像鸭子，那么这只鸟就可以被称为鸭子。”

在鸭子类型中，关注的不是对象的类型本身，而是他是如何使用的。例如，在不使用鸭子类型的语言中，我们可以编写一个函数，它接受一个类型为鸭的对象，并调用它的走和叫方法。在使用鸭子类型的语言中，这样的一个函数可以接受一个任意类型的对象，并调用它的走和叫方法。

我们并不关心对象是什么类型，到底是不是鸭子，只关心行为。

比如在python中，有很多file-like的东西，比如StringIO,GzipFile,socket。它们有很多相同的方法，我们把它们当作文件使用。

又比如list.extend()方法中,我们并不关心它的参数是不是list,只要它是可迭代的,所以它的参数可以是list/tuple/dict/字符串/生成器等.

鸭子类型在动态语言中经常使用，非常灵活，使得python不像java那样专门去弄一大堆的设计模式。

@property 和 @setter

@property负责把一个方法变成属性调用。在对实例操作时，不暴露接口，而是通过getter和setter方法实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Student(object):
    @property
    def score(self):
        return self._score
	@score.setter
    def score(self, value):
        if not isinstance(value, int):
            raise ValueError('score must be an intager')
        if value<0 or value>100:
            raise ValueError('score must between 0~100!')
        self._score = value
		s = Student()
s.score = 60
print(s.score)
s.score = 999
print(s.score)

13 Python中重载

引自知乎:http://www.zhihu.com/question/20053359

Python不支持重载。函数重载主要是为了解决两个问题。可变参数类型和可变参数个数。

因为 python 可以接受任何类型的参数，参数个数不同，可以使用就是缺省参数。

函数重载主要是为了解决两个问题。

  1. 可变参数类型。
  2. 可变参数个数。

另外，一个基本的设计原则是，仅仅当两个函数除了参数类型和参数个数不同以外，其功能是完全相同的，此时才使用函数重载，如果两个函数的功能其实不同，那么不应当使用重载，而应当使用一个名字不同的函数。

好吧，那么对于情况 1 ，函数功能相同，但是参数类型不同，python 如何处理？答案是根本不需要处理，因为 python 可以接受任何类型的参数，如果函数的功能相同，那么不同的参数类型在 python 中很可能是相同的代码，没有必要做成两个不同函数。

那么对于情况 2 ，函数功能相同，但参数个数不同，python 如何处理？大家知道，答案就是缺省参数。对那些缺少的参数设定为缺省参数即可解决问题。因为你假设函数功能相同，那么那些缺少的参数终归是需要用的。

好了，鉴于情况 1 跟 情况 2 都有了解决方案，python 自然就不需要函数重载了。

14 新式类和旧式类

这个面试官问了,我说了老半天,不知道他问的真正意图是什么.

stackoverflow

这篇文章很好的介绍了新式类的特性: http://www.cnblogs.com/btchenguang/archive/2012/09/17/2689146.html

新式类很早在2.2就出现了,所以旧式类完全是兼容的问题,Python3里的类全部都是新式类.这里有一个MRO问题可以了解下(新式类继承是根据C3算法,旧式类是深度优先),<Python核心编程>里讲的也很多.

一个旧式类的深度优先的例子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class A():
    def foo1(self):
        print "A"
class B(A):
    def foo2(self):
        pass
class C(A):
    def foo1(self):
        print "C"
class D(B, C):
    pass

d = D()
d.foo1()

# A

按照经典类的查找顺序从左到右深度优先的规则，在访问d.foo1()的时候,D这个类是没有的..那么往上查找,先找到B,里面没有,深度优先,访问A,找到了foo1(),所以这时候调用的是A的foo1()，从而导致C重写的foo1()被绕过

New-style classes inherit from object, or from another new-style class.

1
2
3
4

class NewStyleClass(object):
	pass
class AnotherNewStyleClass(NewStyleClass):
	pass

Old-style classes don’t.

1
2

class OldStyleClass():
	pass

15 __new__和__init__的区别

这个__new__确实很少见到,先做了解吧.

  1. __new__是一个静态方法,而__init__是一个实例方法.
  2. __new__方法会返回一个创建的实例,而__init__什么都不返回.
  3. 只有在__new__返回一个cls的实例时后面的__init__才能被调用.
  4. 当创建一个新实例时调用__new__,初始化一个实例时用__init__.

stackoverflow

ps: __metaclass__是创建类时起作用.所以我们可以分别使用__metaclass__,__new__和__init__来分别在类创建,实例创建和实例初始化的时候做一些小手脚.

16 单例模式

​ 单例模式是一种常用的软件设计模式。在它的核心结构中只包含一个被称为单例类的特殊类。通过单例模式可以保证系统中一个类只有一个实例而且该实例易于外界访问，从而方便对实例个数的控制并节约系统资源。如果希望在系统中某个类的对象只能存在一个，单例模式是最好的解决方案。

__new__()在__init__()之前被调用，用于生成实例对象。利用这个方法和类的属性的特点可以实现设计模式的单例模式。单例模式是指创建唯一对象，单例模式设计的类只能实例 这个绝对常考啊.绝对要记住1~2个方法,当时面试官是让手写的.

1 使用__new__方法

1
2
3
4
5
6
7
8
9

class Singleton(object):
    def __new__(cls, *args, **kw):
        if not hasattr(cls, '_instance'):
            orig = super(Singleton, cls)
            cls._instance = orig.__new__(cls, *args, **kw)
        return cls._instance

class MyClass(Singleton):
    a = 1

2 共享属性

创建实例时把所有实例的__dict__指向同一个字典,这样它们具有相同的属性和方法.

1
2
3
4
5
6
7
8
9

class Borg(object):
    _state = {}
    def __new__(cls, *args, **kw):
        ob = super(Borg, cls).__new__(cls, *args, **kw)
        ob.__dict__ = cls._state
        return ob

class MyClass2(Borg):
    a = 1

3 装饰器版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def singleton(cls):
    instances = {}
    def getinstance(*args, **kw):
        if cls not in instances:
            instances[cls] = cls(*args, **kw)
        return instances[cls]
    return getinstance

@singleton
class MyClass:
  ...

4 import方法

作为python的模块是天然的单例模式

1
2
3
4
5
6

# mysingleton.py
class My_Singleton(object):
    def foo(self):
        pass

my_singleton = My_Singleton()

1
2
3
4

# to use
from mysingleton import my_singleton

my_singleton.foo()

单例模式伯乐在线详细解释

17 Python中的作用域

Python 中，一个变量的作用域总是由在代码中被赋值的地方所决定的。

当 Python 遇到一个变量的话他会按照这样的顺序进行搜索：

本地作用域（Local）→当前作用域被嵌入的本地作用域（Enclosing locals）→全局/模块作用域（Global）→内置作用域（Built-in）

18 GIL线程全局锁

线程全局锁(Global Interpreter Lock),即Python为了保证线程安全而采取的独立线程运行的限制,说白了就是一个核只能在同一时间运行一个线程.

对于io密集型任务，python的多线程起到作用，但对于cpu密集型任务，python的多线程几乎占不到任何优势，还有可能因为争夺资源而变慢。

见Python 最难的问题

解决办法就是多进程和下面的协程(协程也只是单CPU,但是能减小切换代价提升性能).

多进程在多核利用的效率方面本身就是好于多线程的。何来『不能利用多核』的问题？

多进程之间内存不能共享，因此CPU的每个核运行的代码不会互相相关。对多线程来说会出现多CPU同时访问一个内存区域时需要对内存进行锁定的问题，反而是会影响多核效率的。

由于GIL的限制cPython无法简单充分利用多核处理器的并行处理能力，而使用multiprocessing之类的多进程方式，在进程间通信上会耗费额外多的开销，也达不到多线程应有的效率。

另一方面看来，目前python在大数据量高并发度方面的瓶颈并不是很明显，python通常用于处理轻量级的任务。在我工作中使用python处理上T级别的自然语料库的时候，也是依托于mapreduce平台，所以大数据处理中不能多线程实际上也并不是一个很明显的问题。

而且彻底修改现在的GIL机制牵扯到从底层重新设置cPython的核心，包括资源同步、gc策略等等，如果真的这样修改，会大大降低python处理简单单线程任务的性能，因为即使是单线程也需要做资源同步的话，开销是相当大的。所以cPython在可预见的未来都不会改掉现在的GIL。

Python 其实是希望实现另一个功能，异步操作。尽管异步操作和并行计算都可以通过多线程来完成，但是其实前者更加适合用协程或者用户级线程来完成。但是 Python 是 stackful 实现，也就是 byte code 借用 C runtime stack 来维护自己的运行状态。这种机制的弱点就是不容易用跨平台的方式来实现协程，所以利用 OS 多线程加 GIL 也就成了模拟协程语意的妥协手段。

In CPython, the global interpreter lock, or GIL, is a mutex that prevents multiple native threads from executing Python bytecodes at once. This lock is necessary mainly because CPython’s memory management is not thread-safe. (However, since the GIL exists, other features have grown to depend on the guarantees that it enforces.)

多进程和多线程

**进程：**是资源分配的最小单位，创建和销毁开销较大；

**线程：**是CPU调度的最小单位，开销小，切换速度快；

操作系统将CPU时间片分配给多个线程，每个线程在指定放到时间片内完成。操作系统不断从一个线程切换到另一个线程执行，宏观上看就好像是多个线程一起执行。

Python中由于全局锁 (GIL) 的存在导致，同一时间只有一个获得GIL的线程在跑，其他线程则处于等待状态，这导致了多线程只是在做分时切换，并不能利用多核。

多线程与多进程的区别：（1）多进程中同一个变量各自有一份拷贝在每个进程中，互不影响；（2）多线程中，所有变量都由所有线程共享，任何一个变量都可被任何一个线程修改。线程之间共享数据的最大危险在于多个线程同时更改一个变量，把内容改乱。

19 协程

知乎被问到了,呵呵哒,跪了

简单点说协程是进程和线程的升级版,进程和线程都面临着内核态和用户态的切换问题而耗费许多切换时间,而协程就是用户自己控制切换的时机,不再需要陷入系统的内核态.

Python里最常见的yield就是协程的思想!可以查看第九个问题.

20 闭包

闭包(closure)是函数式编程的重要的语法结构。闭包也是一种组织代码的结构，它同样提高了代码的可重复使用性。闭包可以实现先将一个参数传递给一个函数，而并不立即执行，以达到延迟求值的目的。

当一个内嵌函数引用其外部作作用域的变量,我们就会得到一个闭包. 总结一下,创建一个闭包必须满足以下几点:

  1. 必须有一个内嵌函数
  2. 内嵌函数必须引用外部函数中的变量
  3. 外部函数的返回值必须是内嵌函数

感觉闭包还是有难度的,几句话是说不明白的,还是查查相关资料.

重点是函数运行后并不会被撤销,就像16题的instance字典一样,当函数运行完后,instance并不被销毁,而是继续留在内存空间里.这个功能类似类里的类变量,只不过迁移到了函数上.

闭包就像个空心球一样,你知道外面和里面,但你不知道中间是什么样.

21 lambda函数

其实就是一个匿名函数,为什么叫lambda?因为和后面的函数式编程有关.

Lambda表达式就是：能嵌入到其他表达式当中的匿名函数（闭包）。

  1. 它的第一个重要意义是可以在表达式当中直接定义一个函数，而不需要将定义函数和表达式分开，这样有助于将逻辑用更紧凑的方式表达出来。
  2. 它的第二个重要意义是引入了闭包。基本上来说常见的支持lambda表达式的语言里，不存在不支持闭包的lambda表达式；从函数式编程的角度来说，支持闭包也是很重要的。闭包是指将当前作用域中的变量通过值或者引用的方式封装到lambda表达式当中，成为表达式的一部分，它使你的lambda表达式从一个普通的函数变成了一个带隐藏参数的函数。

推荐: 知乎

22 Python函数式编程

这个需要适当的了解一下吧,毕竟函数式编程在Python中也做了引用.

推荐: 酷壳

python中函数式编程支持:

filter 函数的功能相当于过滤器。调用一个布尔函数bool_func来迭代遍历每个seq中的元素；返回一个使bool_seq返回值为true的元素的序列。

1
2
3
4

>>>a = [1,2,3,4,5,6,7]
>>>b = filter(lambda x: x > 5, a)
>>>print b
>>>[6,7]

map函数是对一个序列的每个项依次执行函数，下面是对一个序列每个项都乘以2：

1
2
3

>>> a = map(lambda x:x*2,[1,2,3])
>>> list(a)
[2, 4, 6]

reduce函数是对一个序列的每个项迭代调用函数，下面是求3的阶乘：

1
2

>>> reduce(lambda x,y:x*y,range(1,4))
6

23 Python里的拷贝

引用和copy(),deepcopy()的区别

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import copy
a = [1, 2, 3, 4, ['a', 'b']]  #原始对象

b = a  #赋值，传对象的引用
c = copy.copy(a)  #对象拷贝，浅拷贝
d = copy.deepcopy(a)  #对象拷贝，深拷贝

a.append(5)  #修改对象a
a[4].append('c')  #修改对象a中的['a', 'b']数组对象

print 'a = ', a
print 'b = ', b
print 'c = ', c
print 'd = ', d

输出结果：
a =  [1, 2, 3, 4, ['a', 'b', 'c'], 5]
b =  [1, 2, 3, 4, ['a', 'b', 'c'], 5]
c =  [1, 2, 3, 4, ['a', 'b', 'c']]
d =  [1, 2, 3, 4, ['a', 'b']]

24 Python垃圾回收机制

Python GC主要使用引用计数（reference counting）来跟踪和回收垃圾。在引用计数的基础上，通过“标记-清除”（mark and sweep）解决容器对象可能产生的循环引用问题，通过“分代回收”（generation collection）以空间换时间的方法提高垃圾回收效率。

1 引用计数

PyObject是每个对象必有的内容，其中ob_refcnt就是做为引用计数。当一个对象有新的引用时，它的ob_refcnt就会增加，当引用它的对象被删除，它的ob_refcnt就会减少.引用计数为0时，该对象生命就结束了。

优点:

  1. 简单
  2. 实时性

缺点:

  1. 维护引用计数消耗资源
  2. 循环引用

2 标记-清除机制

基本思路是先按需分配，等到没有空闲内存的时候从寄存器和程序栈上的引用出发，遍历以对象为节点、以引用为边构成的图，把所有可以访问到的对象打上标记，然后清扫一遍内存空间，把所有没标记的对象释放。

3 分代技术

分代回收的整体思想是：将系统中的所有内存块根据其存活时间划分为不同的集合，每个集合就成为一个“代”，垃圾收集频率随着“代”的存活时间的增大而减小，存活时间通常利用经过几次垃圾回收来度量。

Python默认定义了三代对象集合，索引数越大，对象存活时间越长。

举例： 当某些内存块M经过了3次垃圾收集的清洗之后还存活时，我们就将内存块M划到一个集合A中去，而新分配的内存都划分到集合B中去。当垃圾收集开始工作时，大多数情况都只对集合B进行垃圾回收，而对集合A进行垃圾回收要隔相当长一段时间后才进行，这就使得垃圾收集机制需要处理的内存少了，效率自然就提高了。在这个过程中，集合B中的某些内存块由于存活时间长而会被转移到集合A中，当然，集合A中实际上也存在一些垃圾，这些垃圾的回收会因为这种分代的机制而被延迟。

说明os,sys模块不同，并列举常用的模块方法？

os模板提供了一种方便的使用操作系统函数的方法

sys模板可供访问由解释器使用或维护的变量和与解释器交互的函数

os模块负责程序与操作系统的交互，提供了访问操作系统底层的接口。sys模块负责程序与Python解释器的交互，提供了一系列的函数和变量用户操作Python运行时的环境。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

os.remove()
os.rename()
os.walk()
os.chdir()
os.mkdir/makedirs
os.rmdir/removedirs
os.listdir()
os.getcwd()
os.chmod()
os.path.basename()
os.path.dirname()
os.path.join()
os.path.split()
os.path.splitext()
os.path.getatime\ctime\mtime
os.path.getsize()
os.path.exists()
os.path.isabs()
os.path.isdir()
os.path.isfile()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

sys.argv
sys.modules.keys()
sys.exc_info()
sys.exit(n)
sys.hexversion
sys.maxint
sys.maxunicode
sys.modules
sys.path
sys.platform
sys.stdout
sys.stdin
sys.stderr
sys.exc_clear()
sys.byteorder
sys.api_version
sys.version_info

25 Python的List

推荐: http://www.jianshu.com/p/J4U6rR

内存布局 像vector

append

insert

pop allocated reduce

listremove allocated reduce

26 Python的is

is是对比地址,==是对比值

27 read,readline和readlines

  • read 读取整个文件
  • readline 读取下一行,使用生成器方法
  • readlines 读取整个文件到一个迭代器以供我们遍历

28 Python2和3的区别

推荐：Python 2.7.x 与 Python 3.x 的主要差异

  • future
  • print
  • 整除
  • unicode
    • Python 2 有 ASCII str() 类型，unicode() 是单独的，不是 byte 类型。
    • 在 Python 3，有了 Unicode (utf-8) 字符串，以及一个字节类：byte 和 bytearrays。
  • 没有xrange

29 super init

super() lets you avoid referring to the base class explicitly, which can be nice. But the main advantage comes with multiple inheritance, where all sorts of fun stuff can happen. See the standard docs on super if you haven’t already.

Note that the syntax changed in Python 3.0: you can just say super().__init__() instead of super(ChildB, self).__init__() which IMO is quite a bit nicer.

http://stackoverflow.com/questions/576169/understanding-python-super-with-init-methods

Python2.7中的super方法浅见

30 range and xrange

都在循环时使用，xrange内存性能更好。 for i in range(0, 20): for i in xrange(0, 20): What is the difference between range and xrange functions in Python 2.X? range creates a list, so if you do range(1, 10000000) it creates a list in memory with 9999999 elements. xrange is a sequence object that evaluates lazily.

http://stackoverflow.com/questions/94935/what-is-the-difference-between-range-and-xrange-functions-in-python-2-x

  • How are arguments passed – by reference of by value?

  • Do you know what list and dict comprehensions are? Can you give an example?

  • What is PEP 8?

  • Do you use virtual environments?

  • Can you sum all of the elements in the list, how about to multuply them and get the result?

  • Do you know what is the difference between lists and tuples? Can you give me an example for their usage?

  • Do you know the difference between range and xrange?

  • Tell me a few differences between Python 2.x and 3.x

  • What are decorators and what is their usage?

  • The with statement and its usage.

  • 说说你对zen of python的理解，你有什么办法看到它

  • github上都fork过哪些python库，列举一下你经常使用的，每个库用一句话描述下其功能

  • 你调试python代码的方法有哪些

  • 什么是

  • 什么是元类(meta_class)

  • 对比一下dict中 items 与 iteritems

  • 是否遇到过python的模块间循环引用的问题，如何避免它

  • 有用过with statement吗？它的好处是什么？

  • 说说decorator的用法和它的应用场景，如果可以的话，写一个decorator

  • inspect模块有什么用

  • 写一个类，并让它尽可能多的支持操作符

  • 说一说你见过比较cool的python实现

  • python下多线程的限制以及多进程中传递参数的方式

  • Python是如何进行内存管理的？

  • 什么是lambda函数？它有什么好处?

  • 如何用Python输出一个Fibonacci数列？

  • 介绍一下Python中webbrowser的用法？

  • 解释一下python的and-or语法

  • Python是如何进行类型转换的？

  • Python如何实现单例模式？其他23种设计模式python如何实现？

  • 如何用Python来进行查询和替换一个文本字符串？

  • 如何用Python来发送邮件？

  • 有没有一个工具可以帮助查找python的bug和进行静态的代码分析？

有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；

要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。

  • 如何用Python删除一个文件？
  • Python如何copy一个文件？
  • python程序中文输出问题怎么解决？
  • python代码得到列表list的交集与差集
  • 写一个简单的python socket编程
  • python如何捕获异常
  • 在Python中, list, tuple, dict, set有什么区别, 主要应用在什么样的场景?
  • 静态函数, 类函数, 成员函数的区别?
  • a=1, b=2, 不用中间变量交换a和b的值
  • 写一个函数, 输入一个字符串, 返回倒序排列的结果: 如: string_reverse(‘abcdef’), 返回: ‘fedcba’
  • 请用自己的算法, 按升序合并如下两个list, 并去除重复的元素:

list1 = [2, 3, 8, 4, 9, 5, 6]

list2 = [5, 6, 10, 17, 11, 2]

  • 说一下以下代码片段存在的问题

from amodule import * # amodule is an exist module

class dummyclass(object): def init(self): self**.**is_d = True pass

class childdummyclass(dummyclass): def init(self, isman): self**.**isman = isman

@classmethod def can_speak(self): return True

@property def man(self): return self**.**isman

if name == “main”: object = new childdummyclass(True) **print(object.**can_speak()) **print(object.**man()) **print(object.**is_d)

  • 介绍一下python的异常处理机制和自己开发过程中的体会
  • 解释一下 WSGI 和 FastCGI 的关系？
  • 解释一下 Django 和 Tornado 的关系、差别
  • 解释下Django使用redis缓存服务器
  • 如何进行Django单元测试
  • 解释下Http协议
  • 解释下Http请求头和常见响应状态码
  • 分别简述OO，OOA
  • 简述正则表达式中？p的含义
  • Python类中的self的具体含义是
  • 请写出python的常用内置函数（至少3个），并描述它们具体含义
  • 可以用python进行POST数据提交，可以加载什么模块来进行操作？在操作之前需要对数据进行什么操作？
  • 说出python中间件Sqlalchemy的具体声明方式？以及模块与MySQLdb之间的区别？
  • 描述出3中python常用框架，并简要描述这些框架的优缺点
  • reactor是什么？ 有什么作用？请简要描述。
  • 请描述2种不同语言间数据流转通用格式。
  • 简述我们使用多线程编程时，锁与信号量之间的关系。
  • 通常在python编写tcp服务时，我们使用拆、粘包的模块是什么？如何加载这个模块？

两个整数数组各有100亿条数据，并已经排序，保存在磁盘上，内存10M。

问：

（1）如何取得交集？时间和空间效率分别是多少？Python 集合set()操作方法

（2）如果其中一个数组只有100条数据，如何优化算法取得交集？时间和空间效率分别是多少？

（3）用自己熟悉的语言实现第2个问题，要求可以正确运行；假设已经提供函数read_elt(arrary_name, index)可以用来读取某个数组的第index个元素，元素个数分别用m=100和n=10^10表示。

  • 有100个磁盘组成的存储系统，当有3个磁盘同时损坏时，才会发生数据丢失。如果1个磁盘的损坏率是p，请问整个存储系统丢失数据的概率是多少？
  • 请描述B-Tree插入值的过程
  • 一个管道可以从a端发送字符到b端，只能发送0-9这10个数字，设计消息的协议，让a可以通知b任意大小的数字，并讨论这种消息协议可能发送的错误的处理能力。
  • 假设fd是一个socket，read(fd, buf, 1024)

问：可能返回哪些值？其代表什么含义？

  • 自旋锁适合哪些场合应用，不适合哪些场合？
  • 假设网络会丢失消息，进程可能意外终止，磁盘可靠（写入数据后不会丢失）；

问：

如何构建一个可靠的分布式key-value存储系统？

答题要求如下：

1.客户端向系统发送1条写入请求(例如key=x, value=1)，系统返回’成功’，客户端一定可以正确读取到key=y的值

2.在你设计的系统中，要满足上面第1条，并有一定对故障的容错能力。

3.如果要尽可能提高写入或读写成功率，如果改进系统设计？分别会有哪些问题？

  • 假设你的键盘只有以下键:

A

Ctrl + A

Ctrl + C

Ctrl + V

这里Ctrl+A,Ctrl+C,Ctrl+V分别代表"全选”,“复制”，“粘贴”。

如果你只能按键盘N次，请写一个程序可以产生最多数量的A。也就是说输入是N(你按键盘的次数)， 输出是M(产生的A的个数)。

加分项：

打印出中间你按下的那些键。

  • 假设给你一个月的日志，格式如下：

[I 130403 17:26:40] 1 200 GET /question/123 (8.8.9.9) 200.39ms

[I 130403 17:26:90] 1 200 GET /topic/456 (8.8.9.9) 300.85ms

[I 130403 17:26:90] 1 200 POST /answer/789 (8.8.9.9) 300.85ms

…

方括号中依次是：级别，日期，时间，后面依次是用户id，返回码，访问方式，访问路径，用户ip，响应时间

日志文件名格式为：年-月-日-小时.log，如：2013-01-01-18.log，共30*24个文件。

写个程序，算出一个用户列表和一个路径列表符合以下要求：

(1).这些用户每天都会访问（GET）/topic/***这个路径两次以上（*代表数字）

(2).这些用户每天访问（GET）的/topic/***路径中，至少会包含两个不同的路径（后面的数字不一样）

(3).统计出所有以上用户所访问的路径中每天都出现两次以上的路径列表

  • 有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；

要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小

  • Python语言的有哪些缺陷？
  • What are some key differences to bear in mind when coding in Python vs. Java?
  • 有哪些CPython的替代实现？什么时候，为什么会使用他们？
  • Python是解释型的还是编译型的？
  • 为什么要用函数装饰器？请举例
  • 现在有一个 dict 对象 adict，里面包含了一百万个元素，查找其中的某个元素的平均需要多少次比较？一千万个元素呢？
  • 现在有一个 list 对象 alist，里面的所有元素都是字符串，编写一个函数对它实现一个大小写无关的排序。
  • python 里关于“堆”这种数据结构的模块是哪个？“堆”有什么优点和缺点？举一个游戏开发中可能会用到堆的问题（不限是于 python 的堆，可以是其它语言的相关实现）。
  • set 是在哪个版本成为 build-in types 的？举一个你在以往项目中用到这种数据结构的问题（不限是于 python 的 set ，可以是其它语言的相关实现），并说明为什么当时选择了 set 这种数据结构。
  • 有一个排好序地 list 对象 alist，查找其中是否有某元素 a（尽可能地使用标准库函数）
  • 实现一个 stack。
  • 编写一个简单的 ini 文件解释器。
  • 现有 N 个纯文本格式的英文文件，实现一种检索方案，即做一个小搜索引擎。

操作系统

1 select,poll和epoll

其实所有的I/O都是轮询的方法,只不过实现的层面不同罢了.

这个问题可能有点深入了,但相信能回答出这个问题是对I/O多路复用有很好的了解了.其中tornado使用的就是epoll的.

selec,poll和epoll区别总结

基本上select有3个缺点:

  1. 连接数受限
  2. 查找配对速度慢
  3. 数据由内核拷贝到用户态

poll改善了第一个缺点

epoll改了三个缺点.

关于epoll的: http://www.cnblogs.com/my_life/articles/3968782.html

2 调度算法

  1. 先来先服务(FCFS, First Come First Serve)
  2. 短作业优先(SJF, Shortest Job First)
  3. 最高优先权调度(Priority Scheduling)
  4. 时间片轮转(RR, Round Robin)
  5. 多级反馈队列调度(multilevel feedback queue scheduling)

常见的调度算法总结:http://www.jianshu.com/p/6edf8174c1eb

实时调度算法:

  1. 最早截至时间优先 EDF
  2. 最低松弛度优先 LLF

3 死锁

原因:

  1. 竞争资源
  2. 程序推进顺序不当

必要条件:

  1. 互斥条件
  2. 请求和保持条件
  3. 不剥夺条件
  4. 环路等待条件

处理死锁基本方法:

  1. 预防死锁(摒弃除1以外的条件)
  2. 避免死锁(银行家算法)
  3. 检测死锁(资源分配图)
  4. 解除死锁
    1. 剥夺资源
    2. 撤销进程
  5. 互斥锁

死锁概念处理策略详细介绍:https://wizardforcel.gitbooks.io/wangdaokaoyan-os/content/10.html

4 程序编译与链接

推荐: http://www.ruanyifeng.com/blog/2014/11/compiler.html

Bulid过程可以分解为4个步骤:预处理(Prepressing), 编译(Compilation)、汇编(Assembly)、链接(Linking)

以c语言为例:

1 预处理

预编译过程主要处理那些源文件中的以“#”开始的预编译指令，主要处理规则有：

  1. 将所有的“#define”删除，并展开所用的宏定义
  2. 处理所有条件预编译指令，比如“#if”、“#ifdef”、 “#elif”、“#endif”
  3. 处理“#include”预编译指令，将被包含的文件插入到该编译指令的位置，注：此过程是递归进行的
  4. 删除所有注释
  5. 添加行号和文件名标识，以便于编译时编译器产生调试用的行号信息以及用于编译时产生编译错误或警告时可显示行号
  6. 保留所有的#pragma编译器指令。

2 编译

编译过程就是把预处理完的文件进行一系列的词法分析、语法分析、语义分析及优化后生成相应的汇编代码文件。这个过程是整个程序构建的核心部分。

3 汇编

汇编器是将汇编代码转化成机器可以执行的指令，每一条汇编语句几乎都是一条机器指令。经过编译、链接、汇编输出的文件成为目标文件(Object File)

4 链接

链接的主要内容就是把各个模块之间相互引用的部分处理好，使各个模块可以正确的拼接。 链接的主要过程包块 地址和空间的分配（Address and Storage Allocation）、符号决议(Symbol Resolution)和重定位(Relocation)等步骤。

5 静态链接和动态链接

静态链接方法：静态链接的时候，载入代码就会把程序会用到的动态代码或动态代码的地址确定下来 静态库的链接可以使用静态链接，动态链接库也可以使用这种方法链接导入库

动态链接方法：使用这种方式的程序并不在一开始就完成动态链接，而是直到真正调用动态库代码时，载入程序才计算(被调用的那部分)动态代码的逻辑地址，然后等到某个时候，程序又需要调用另外某块动态代码时，载入程序又去计算这部分代码的逻辑地址，所以，这种方式使程序初始化时间较短，但运行期间的性能比不上静态链接的程序

6 虚拟内存技术

虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储系统.

7 分页和分段

分页: 用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。

分段: 将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。

分页与分段的主要区别

  1. 页是信息的物理单位,分页是为了实现非连续分配,以便解决内存碎片问题,或者说分页是由于系统管理的需要.段是信息的逻辑单位,它含有一组意义相对完整的信息,分段的目的是为了更好地实现共享,满足用户的需要.
  2. 页的大小固定,由系统确定,将逻辑地址划分为页号和页内地址是由机器硬件实现的.而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时根据信息的性质来划分.
  3. 分页的作业地址空间是一维的.分段的地址空间是二维的.

8 页面置换算法

  1. 最佳置换算法OPT:不可能实现
  2. 先进先出FIFO
  3. 最近最久未使用算法LRU:最近一段时间里最久没有使用过的页面予以置换.
  4. clock算法

9 边沿触发和水平触发

边缘触发是指每当状态变化时发生一个 io 事件，条件触发是只要满足条件就发生一个 io 事件

数据库

1 事务

数据库事务(Database Transaction) ，是指作为单个逻辑工作单元执行的一系列操作，要么完全地执行，要么完全地不执行。 彻底理解数据库事务: http://www.hollischuang.com/archives/898

2 数据库索引

推荐: http://tech.meituan.com/mysql-index.html

MySQL索引背后的数据结构及算法原理

聚集索引,非聚集索引,B-Tree,B+Tree,最左前缀原理

3 Redis原理

Redis是什么？

  1. 是一个完全开源免费的key-value内存数据库
  2. 通常被认为是一个数据结构服务器，主要是因为其有着丰富的数据结构 strings、map、 list、sets、 sorted sets

Redis数据库

​ 通常局限点来说，Redis也以消息队列的形式存在，作为内嵌的List存在，满足实时的高并发需求。在使用缓存的时候，redis比memcached具有更多的优势，并且支持更多的数据类型，把redis当作一个中间存储系统，用来处理高并发的数据库操作

  • 速度快：使用标准C写，所有数据都在内存中完成，读写速度分别达到10万/20万
  • 持久化：对数据的更新采用Copy-on-write技术，可以异步地保存到磁盘上，主要有两种策略，一是根据时间，更新次数的快照（save 300 10 ）二是基于语句追加方式(Append-only file，aof)
  • 自动操作：对不同数据类型的操作都是自动的，很安全
  • 快速的主–从复制，官方提供了一个数据，Slave在21秒即完成了对Amazon网站10G key set的复制。
  • Sharding技术： 很容易将数据分布到多个Redis实例中，数据库的扩展是个永恒的话题，在关系型数据库中，主要是以添加硬件、以分区为主要技术形式的纵向扩展解决了很多的应用场景，但随着web2.0、移动互联网、云计算等应用的兴起，这种扩展模式已经不太适合了，所以近年来，像采用主从配置、数据库复制形式的，Sharding这种技术把负载分布到多个特理节点上去的横向扩展方式用处越来越多。

Redis缺点

  • 是数据库容量受到物理内存的限制,不能用作海量数据的高性能读写,因此Redis适合的场景主要局限在较小数据量的高性能操作和运算上。
  • Redis较难支持在线扩容，在集群容量达到上限时在线扩容会变得很复杂。为避免这一问题，运维人员在系统上线时必须确保有足够的空间，这对资源造成了很大的浪费。

4 乐观锁和悲观锁

悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作

乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。

乐观锁与悲观锁的具体区别: http://www.cnblogs.com/Bob-FD/p/3352216.html

5 MVCC

​ 全称是Multi-Version Concurrent Control，即多版本并发控制，在MVCC协议下，每个读操作会看到一个一致性的snapshot，并且可以实现非阻塞的读。MVCC允许数据具有多个版本，这个版本可以是时间戳或者是全局递增的事务ID，在同一个时间点，不同的事务看到的数据是不同的。

MySQL的innodb引擎是如何实现MVCC的

innodb会为每一行添加两个字段，分别表示该行创建的版本和删除的版本，填入的是事务的版本号，这个版本号随着事务的创建不断递增。在repeated read的隔离级别（事务的隔离级别请看这篇文章）下，具体各种数据库操作的实现：

  • select：满足以下两个条件innodb会返回该行数据：
    • 该行的创建版本号小于等于当前版本号，用于保证在select操作之前所有的操作已经执行落地。
    • 该行的删除版本号大于当前版本或者为空。删除版本号大于当前版本意味着有一个并发事务将该行删除了。
  • insert：将新插入的行的创建版本号设置为当前系统的版本号。
  • delete：将要删除的行的删除版本号设置为当前系统的版本号。
  • update：不执行原地update，而是转换成insert + delete。将旧行的删除版本号设置为当前版本号，并将新行insert同时设置创建版本号为当前版本号。

其中，写操作（insert、delete和update）执行时，需要将系统版本号递增。

​ 由于旧数据并不真正的删除，所以必须对这些数据进行清理，innodb会开启一个后台线程执行清理工作，具体的规则是将删除版本号小于当前系统版本的行删除，这个过程叫做purge。

通过MVCC很好的实现了事务的隔离性，可以达到repeated read级别，要实现serializable还必须加锁。

参考：MVCC浅析

6 MyISAM和InnoDB

MyISAM 适合于一些需要大量查询的应用，但其对于有大量写操作并不是很好。甚至你只是需要update一个字段，整个表都会被锁起来，而别的进程，就算是读进程都无法操作直到读操作完成。另外，MyISAM 对于 SELECT COUNT(*) 这类的计算是超快无比的。

InnoDB 的趋势会是一个非常复杂的存储引擎，对于一些小的应用，它会比 MyISAM 还慢。他是它支持“行锁” ，于是在写操作比较多的时候，会更优秀。并且，他还支持更多的高级应用，比如：事务。

mysql 数据库引擎: http://www.cnblogs.com/0201zcr/p/5296843.html MySQL存储引擎－－MyISAM与InnoDB区别: https://segmentfault.com/a/1190000008227211

MySQL基本语法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

CREATE  TABLE  example(id  INT,
            name  VARCHAR(20),
            sex  BOOLEAN);

ALTER  TABLE  表名 DROP  属性名;    # 删除字段
DROP  TABLE   表名;       # 删除表

ALTER  TABLE  旧表名 RENAME  新表名;    # 修改表名
ALTER  TABLE  表名 MODIFY  属性名  数据类型;    # 修改字段数据类型 

SELECT  * FROM 表名 WHERE  id=1;   # 条件查询
SELECT  * FROM 表名 WHERE  字段名 BETWEEN 条件一 AND  条件二 # 范围查询
SELECT  COUNT(*) FROM  表名;   # 查询表共有多少条记录

触发器：是由INSERT、UPDATE和DELETE等事件来触发某种特定操作，满足触发条件时，数据库系统会执行触发器中定义的语句，这样可以保证某些操作之间的一致性。

1
2
3
4
5

CREATE  TRIGGER  触发器名称  BEFORE|AFTER   触发事件
    ON  表名称 FOR  EACH ROW
    BEGIN
        执行语句
    END

网络

1 三次握手

  1. 客户端通过向服务器端发送一个SYN来创建一个主动打开，作为三次握手的一部分。客户端把这段连接的序号设定为随机数 A。
  2. 服务器端应当为一个合法的SYN回送一个SYN/ACK。ACK 的确认码应为 A+1，SYN/ACK 包本身又有一个随机序号 B。
  3. 最后，客户端再发送一个ACK。当服务端受到这个ACK的时候，就完成了三路握手，并进入了连接创建状态。此时包序号被设定为收到的确认号 A+1，而响应则为 B+1。

2 四次挥手

注意: 中断连接端可以是客户端，也可以是服务器端. 下面仅以客户端断开连接举例, 反之亦然.

  1. 客户端发送一个数据分段, 其中的 FIN 标记设置为1. 客户端进入 FIN-WAIT 状态. 该状态下客户端只接收数据, 不再发送数据.
  2. 服务器接收到带有 FIN = 1 的数据分段, 发送带有 ACK = 1 的剩余数据分段, 确认收到客户端发来的 FIN 信息.
  3. 服务器等到所有数据传输结束, 向客户端发送一个带有 FIN = 1 的数据分段, 并进入 CLOSE-WAIT 状态, 等待客户端发来带有 ACK = 1 的确认报文.
  4. 客户端收到服务器发来带有 FIN = 1 的报文, 返回 ACK = 1 的报文确认, 为了防止服务器端未收到需要重发, 进入 TIME-WAIT 状态. 服务器接收到报文后关闭连接. 客户端等待 2MSL 后未收到回复, 则认为服务器成功关闭, 客户端关闭连接.

图解: http://blog.csdn.net/whuslei/article/details/6667471

3 ARP协议

地址解析协议(Address Resolution Protocol)，其基本功能为透过目标设备的IP地址，查询目标的MAC地址，以保证通信的顺利进行。它是IPv4网络层必不可少的协议，不过在IPv6中已不再适用，并被邻居发现协议（NDP）所替代。

4 urllib和urllib2的区别

这个面试官确实问过,当时答的urllib2可以Post而urllib不可以.

  1. urllib提供urlencode方法用来GET查询字符串的产生，而urllib2没有。这是为何urllib常和urllib2一起使用的原因。
  2. urllib2可以接受一个Request类的实例来设置URL请求的headers，urllib仅可以接受URL。这意味着，你不可以伪装你的User Agent字符串等。

5 Post和Get

GET和POST有什么区别？及为什么网上的多数答案都是错的 知乎回答

get: RFC 2616 - Hypertext Transfer Protocol – HTTP/1.1 post: RFC 2616 - Hypertext Transfer Protocol – HTTP/1.1

GET：浏览器告知服务器，只获取页面上的信息，请求的参数加到url后面；

POST：浏览器告知服务器，想在URL上发布新的信息，并且服务器必须确保数据已经存储且仅存储一次。这是html表单发送数据到服务器的方法。提交的数据放到data或body中，不能放到url中。

GET是用于获取数据的，POST，一般用于将数据发给服务器之用

GET和POST与数据如何传递没有关系

HTTP协议对GET和POST都没有对长度的限制

安全不安全和GET、POST没有关系

只是GET使用URL或Cookie传参。而POST将数据放在BODY中。

具体的请参考RFC文档。

6 Cookie和Session

Cookie Session
储存位置 客户端 服务器端
目的 跟踪会话，也可以保存用户偏好设置或者保存用户名密码等 跟踪会话
安全性 不安全 安全

session技术是要使用到cookie的，之所以出现session技术，主要是为了安全。

7 apache和nginx的区别

nginx 相对 apache 的优点：

  • 轻量级，同样起web 服务，比apache 占用更少的内存及资源
  • 抗并发，nginx 处理请求是异步非阻塞的，支持更多的并发连接，而apache 则是阻塞型的，在高并发下nginx 能保持低资源低消耗高性能
  • 配置简洁
  • 高度模块化的设计，编写模块相对简单
  • 社区活跃

apache 相对nginx 的优点：

  • rewrite ，比nginx 的rewrite 强大
  • 模块超多，基本想到的都可以找到
  • 少bug ，nginx 的bug 相对较多
  • 超稳定

8 网站用户密码保存

  1. 明文保存
  2. 明文hash后保存,如md5
  3. MD5+Salt方式,这个salt可以随机
  4. 知乎使用了Bcrypy(好像)加密

9 HTTP和HTTPS

状态码 定义
1xx 报告 接收到请求，继续进程
2xx 成功 步骤成功接收，被理解，并被接受
3xx 重定向 为了完成请求,必须采取进一步措施
4xx 客户端出错 请求包括错的顺序或不能完成
5xx 服务器出错 服务器无法完成显然有效的请求

403: Forbidden 404: Not Found

HTTPS握手,对称加密,非对称加密,TLS/SSL,RSA

10 XSRF和XSS

  • CSRF(Cross-site request forgery)跨站请求伪造
  • XSS(Cross Site Scripting)跨站脚本攻击

CSRF重点在请求,XSS重点在脚本

11 幂等 Idempotence

HTTP方法的幂等性是指一次和多次请求某一个资源应该具有同样的副作用。(注意是副作用)

GET http://www.bank.com/account/123456，不会改变资源的状态，不论调用一次还是N次都没有副作用。请注意，这里强调的是一次和N次具有相同的副作用，而不是每次GET的结果相同。GET http://www.news.com/latest-news这个HTTP请求可能会每次得到不同的结果，但它本身并没有产生任何副作用，因而是满足幂等性的。

DELETE方法用于删除资源，有副作用，但它应该满足幂等性。比如：DELETE http://www.forum.com/article/4231，调用一次和N次对系统产生的副作用是相同的，即删掉id为4231的帖子；因此，调用者可以多次调用或刷新页面而不必担心引起错误。

POST所对应的URI并非创建的资源本身，而是资源的接收者。比如：POST http://www.forum.com/articles的语义是在http://www.forum.com/articles下创建一篇帖子，HTTP响应中应包含帖子的创建状态以及帖子的URI。两次相同的POST请求会在服务器端创建两份资源，它们具有不同的URI；所以，POST方法不具备幂等性。

PUT所对应的URI是要创建或更新的资源本身。比如：PUT http://www.forum/articles/4231的语义是创建或更新ID为4231的帖子。对同一URI进行多次PUT的副作用和一次PUT是相同的；因此，PUT方法具有幂等性。

12 RESTful架构(SOAP,RPC)

推荐: http://www.ruanyifeng.com/blog/2011/09/restful.html

13 SOAP

SOAP（原为Simple Object Access Protocol的首字母缩写，即简单对象访问协议）是交换数据的一种协议规范，使用在计算机网络Web服务（web service）中，交换带结构信息。SOAP为了简化网页服务器（Web Server）从XML数据库中提取数据时，节省去格式化页面时间，以及不同应用程序之间按照HTTP通信协议，遵从XML格式执行资料互换，使其抽象于语言实现、平台和硬件。

14 RPC

RPC（Remote Procedure Call Protocol）——远程过程调用协议，它是一种通过网络从远程计算机程序上请求服务，而不需要了解底层网络技术的协议。RPC协议假定某些传输协议的存在，如TCP或UDP，为通信程序之间携带信息数据。在OSI网络通信模型中，RPC跨越了传输层和应用层。RPC使得开发包括网络分布式多程序在内的应用程序更加容易。

总结:服务提供的两大流派.传统意义以方法调用为导向通称RPC。为了企业SOA,若干厂商联合推出webservice,制定了wsdl接口定义,传输soap.当互联网时代,臃肿SOA被简化为http+xml/json.但是简化出现各种混乱。以资源为导向,任何操作无非是对资源的增删改查，于是统一的REST出现了.

进化的顺序: RPC -> SOAP -> RESTful

15 CGI和WSGI

CGI是通用网关接口，是连接web服务器和应用程序的接口，用户通过CGI来获取动态数据或文件等。 CGI程序是一个独立的程序，它可以用几乎所有语言来写，包括perl，c，lua，python等等。

WSGI, Web Server Gateway Interface，是Python应用程序或框架和Web服务器之间的一种接口，WSGI的其中一个目的就是让用户可以用统一的语言(Python)编写前后端。

官方说明：PEP-3333

16 中间人攻击

在GFW里屡见不鲜的,呵呵.

中间人攻击（Man-in-the-middle attack，通常缩写为MITM）是指攻击者与通讯的两端分别创建独立的联系，并交换其所收到的数据，使通讯的两端认为他们正在通过一个私密的连接与对方直接对话，但事实上整个会话都被攻击者完全控制。

17 c10k问题

所谓c10k问题，指的是服务器同时支持成千上万个客户端的问题，也就是concurrent 10 000 connection（这也是c10k这个名字的由来）。 推荐: https://my.oschina.net/xianggao/blog/664275

http://www.kegel.com/c10k.html

18 socket

推荐: http://www.360doc.com/content/11/0609/15/5482098_122692444.shtml

Socket=Ip address+ TCP/UDP + port

19 浏览器缓存

推荐: http://www.cnblogs.com/skynet/archive/2012/11/28/2792503.html

304 Not Modified

Expires是Web服务器响应消息头字段，限HTTP 1.0，HTTP 1.1没有作用

Cache-control策略（重点关注） max-age=300

Last-Modified/

Etag 当前资源在服务器的唯一标识

Last-Modified与ETag是可以一起使用的，服务器会优先验证ETag，一致的情况下，才会继续比对Last-Modified，最后才决定是否返回304。

用户行为与缓存

第一次请求

1. EÉ*FExpires. 3. Etag 4. Last-Modified Cache-Control

第二次请求

斑 览 器 请 求 是 否 过 期 ？ Etag? -Mod’ 向 嫩 eb 服 务 器 求 请 求 啃 应 、 缓 存 协 商 向 web 服 务 器 求 FIf-None-Match 向 web 服 务 駕 请 求 带 Mod 而 ed ， e 服 务 决 策

20 HTTP1.0和HTTP1.1

推荐: http://blog.csdn.net/elifefly/article/details/3964766

  1. 请求头Host字段,一个服务器多个网站
  2. 长链接
  3. 文件断点续传
  4. 身份认证,状态管理,Cache缓存

HTTP请求8种方法介绍 HTTP/1.1协议中共定义了8种HTTP请求方法，HTTP请求方法也被叫做“请求动作”，不同的方法规定了不同的操作指定的资源方式。服务端也会根据不同的请求方法做不同的响应。

GET

GET请求会显示请求指定的资源。一般来说GET方法应该只用于数据的读取，而不应当用于会产生副作用的非幂等的操作中。

GET会方法请求指定的页面信息，并返回响应主体，GET被认为是不安全的方法，因为GET方法会被网络蜘蛛等任意的访问。

HEAD

HEAD方法与GET方法一样，都是向服务器发出指定资源的请求。但是，服务器在响应HEAD请求时不会回传资源的内容部分，即：响应主体。这样，我们可以不传输全部内容的情况下，就可以获取服务器的响应头信息。HEAD方法常被用于客户端查看服务器的性能。

POST

POST请求会 向指定资源提交数据，请求服务器进行处理，如：表单数据提交、文件上传等，请求数据会被包含在请求体中。POST方法是非幂等的方法，因为这个请求可能会创建新的资源或/和修改现有资源。

PUT

PUT请求会身向指定资源位置上传其最新内容，PUT方法是幂等的方法。通过该方法客户端可以将指定资源的最新数据传送给服务器取代指定的资源的内容。

DELETE

DELETE请求用于请求服务器删除所请求URI（统一资源标识符，Uniform Resource Identifier）所标识的资源。DELETE请求后指定资源会被删除，DELETE方法也是幂等的。

CONNECT

CONNECT方法是HTTP/1.1协议预留的，能够将连接改为管道方式的代理服务器。通常用于SSL加密服务器的链接与非加密的HTTP代理服务器的通信。

OPTIONS

OPTIONS请求与HEAD类似，一般也是用于客户端查看服务器的性能。 这个方法会请求服务器返回该资源所支持的所有HTTP请求方法，该方法会用’*’来代替资源名称，向服务器发送OPTIONS请求，可以测试服务器功能是否正常。JavaScript的XMLHttpRequest对象进行CORS跨域资源共享时，就是使用OPTIONS方法发送嗅探请求，以判断是否有对指定资源的访问权限。 允许

TRACE

TRACE请求服务器回显其收到的请求信息，该方法主要用于HTTP请求的测试或诊断。

HTTP/1.1之后增加的方法

在HTTP/1.1标准制定之后，又陆续扩展了一些方法。其中使用中较多的是 PATCH 方法：

PATCH

PATCH方法出现的较晚，它在2010年的RFC 5789标准中被定义。PATCH请求与PUT请求类似，同样用于资源的更新。二者有以下两点不同：

但PATCH一般用于资源的部分更新，而PUT一般用于资源的整体更新。 当资源不存在时，PATCH会创建一个新的资源，而PUT只会对已在资源进行更新。

21 Ajax

AJAX,Asynchronous JavaScript and XML（异步的 JavaScript 和 XML）, 是与在不重新加载整个页面的情况下，与服务器交换数据并更新部分网页的技术。

*NIX

unix进程间通信方式(IPC)

  1. 管道（Pipe）：管道可用于具有亲缘关系进程间的通信，允许一个进程和另一个与它有共同祖先的进程之间进行通信。
  2. 命名管道（named pipe）：命名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。命名管道在文件系统中有对应的文件名。命名管道通过命令mkfifo或系统调用mkfifo来创建。
  3. 信号（Signal）：信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身；linux除了支持Unix早期信号语义函数sigal外，还支持语义符合Posix.1标准的信号函数sigaction（实际上，该函数是基于BSD的，BSD为了实现可靠信号机制，又能够统一对外接口，用sigaction函数重新实现了signal函数）。
  4. 消息（Message）队列：消息队列是消息的链接表，包括Posix消息队列system V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺
  5. 共享内存：使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其它通信机制，如信号量结合使用，来达到进程间的同步及互斥。
  6. 内存映射（mapped memory）：内存映射允许任何多个进程间通信，每一个使用该机制的进程通过把一个共享的文件映射到自己的进程地址空间来实现它。
  7. 信号量（semaphore）：主要作为进程间以及同一进程不同线程之间的同步手段。
  8. 套接口（Socket）：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的，但现在一般可以移植到其它类Unix系统上：Linux和System V的变种都支持套接字。

数据结构

1 红黑树

红黑树与AVL的比较：

AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；

红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；

所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。

红黑树详解: https://xieguanglei.github.io/blog/post/red-black-tree.html

教你透彻了解红黑树: https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

编程题

1 台阶问题/斐波那契

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1

fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)

第二种记忆方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def memo(func):
    cache = {}
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap


@memo
def fib(i):
    if i < 2:
        return 1
    return fib(i-1) + fib(i-2)

第三种方法

1
2
3
4
5

def fib(n):
    a, b = 0, 1
    for _ in xrange(n):
        a, b = b, a + b
    return b

2 变态台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1

fib = lambda n: n if n < 2 else 2 * fib(n - 1)

3 矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

第2*n个矩形的覆盖方法等于第2*(n-1)加上第2*(n-2)的方法。

1

f = lambda n: 1 if n < 2 else f(n - 1) + f(n - 2)

4 杨氏矩阵查找

在一个m行n列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

使用Step-wise线性搜索。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def get_value(l, r, c):
    return l[r][c]

def find(l, x):
    m = len(l) - 1
    n = len(l[0]) - 1
    r = 0
    c = n
    while c >= 0 and r <= m:
        value = get_value(l, r, c)
        if value == x:
            return True
        elif value > x:
            c = c - 1
        elif value < x:
            r = r + 1
    return False

5 去除列表中的重复元素

用集合

1

list(set(l))

用字典

1
2
3

l1 = ['b','c','d','b','c','a','a']
l2 = {}.fromkeys(l1).keys()
print l2

用字典并保持顺序

1
2
3
4

l1 = ['b','c','d','b','c','a','a']
l2 = list(set(l1))
l2.sort(key=l1.index)
print l2

列表推导式

1
2
3

l1 = ['b','c','d','b','c','a','a']
l2 = []
[l2.append(i) for i in l1 if not i in l2]

sorted排序并且用列表推导式.

l = [‘b’,‘c’,’d’,‘b’,‘c’,‘a’,‘a’] [single.append(i) for i in sorted(l) if i not in single] print single

6 链表成对调换

1->2->3->4转换成2->1->4->3.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # @param a ListNode
    # @return a ListNode
    def swapPairs(self, head):
        if head != None and head.next != None:
            next = head.next
            head.next = self.swapPairs(next.next)
            next.next = head
            return next
        return head

7 创建字典的方法

1 直接创建

1

dict = {'name':'earth', 'port':'80'}

2 工厂方法

1
2
3

items=[('name','earth'),('port','80')]
dict2=dict(items)
dict1=dict((['name','earth'],['port','80']))

3 fromkeys()方法

1
2
3
4

dict1={}.fromkeys(('x','y'),-1)
dict={'x':-1,'y':-1}
dict2={}.fromkeys(('x','y'))
dict2={'x':None, 'y':None}

8 合并两个有序列表

知乎远程面试要求编程

尾递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def _recursion_merge_sort2(l1, l2, tmp):
    if len(l1) == 0 or len(l2) == 0:
        tmp.extend(l1)
        tmp.extend(l2)
        return tmp
    else:
        if l1[0] < l2[0]:
            tmp.append(l1[0])
            del l1[0]
        else:
            tmp.append(l2[0])
            del l2[0]
        return _recursion_merge_sort2(l1, l2, tmp)

def recursion_merge_sort2(l1, l2):
    return _recursion_merge_sort2(l1, l2, [])

循环算法

思路：

定义一个新的空列表

比较两个列表的首个元素

小的就插入到新列表里

把已经插入新列表的元素从旧列表删除

直到两个旧列表有一个为空

再把旧列表加到新列表后面

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def loop_merge_sort(l1, l2):
    tmp = []
    while len(l1) > 0 and len(l2) > 0:
        if l1[0] < l2[0]:
            tmp.append(l1[0])
            del l1[0]
        else:
            tmp.append(l2[0])
            del l2[0]
    tmp.extend(l1)
    tmp.extend(l2)
    return tmp

pop弹出

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

a = [1,2,3,7]
b = [3,4,5]

def merge_sortedlist(a,b):
    c = []
    while a and b:
        if a[0] >= b[0]:
            c.append(b.pop(0))
        else:
            c.append(a.pop(0))
    while a:
        c.append(a.pop(0))
    while b:
        c.append(b.pop(0))
    return c
print merge_sortedlist(a,b)

9 交叉链表求交点

其实思想可以按照从尾开始比较两个链表，如果相交，则从尾开始必然一致，只要从尾开始比较，直至不一致的地方即为交叉点，如图所示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# 使用a,b两个list来模拟链表，可以看出交叉点是 7这个节点
a = [1,2,3,7,9,1,5]
b = [4,5,7,9,1,5]

for i in range(1,min(len(a),len(b))):
    if i==1 and (a[-1] != b[-1]):
        print "No"
        break
    else:
        if a[-i] != b[-i]:
            print "交叉节点：",a[-i+1]
            break
        else:
            pass

另外一种比较正规的方法，构造链表类

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def node(l1, l2):
    length1, lenth2 = 0, 0
    # 求两个链表长度
    while l1.next:
        l1 = l1.next
        length1 += 1
    while l2.next:
        l2 = l2.next
        length2 += 1
    # 长的链表先走
    if length1 > lenth2:
        for _ in range(length1 - length2):
            l1 = l1.next
    else:
        for _ in range(length2 - length1):
            l2 = l2.next
    while l1 and l2:
        if l1.next == l2.next:
            return l1.next
        else:
            l1 = l1.next
            l2 = l2.next

修改了一下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#coding:utf-8
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def node(l1, l2):
    length1, length2 = 0, 0
    # 求两个链表长度
    while l1.next:
        l1 = l1.next#尾节点
        length1 += 1
    while l2.next:
        l2 = l2.next#尾节点
        length2 += 1

    #如果相交
    if l1.next == l2.next:
        # 长的链表先走
        if length1 > length2:
            for _ in range(length1 - length2):
                l1 = l1.next
            return l1#返回交点
        else:
            for _ in range(length2 - length1):
                l2 = l2.next
            return l2#返回交点
    # 如果不相交
    else:
        return

思路: http://humaoli.blog.163.com/blog/static/13346651820141125102125995/

10 二分查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#coding:utf-8
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (high - low) / 2 + low    # 避免(high + low) / 2溢出
        guess = list[mid]
        if guess > item:
            high = mid - 1
        elif guess < item:
            low = mid + 1
        else:
            return mid
    return None
mylist = [1,3,5,7,9]
print binary_search(mylist, 3)

参考: http://blog.csdn.net/u013205877/article/details/76411718

冒泡

1
2
3
4
5
6

def bubbleSort(nums):
    for i in range(len(nums)-1):    # 这个循环负责设置冒泡排序进行的次数
        for j in range(len(nums)-i-1):  # ｊ为列表下标
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

11 快排

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#coding:utf-8
def quicksort(list):
    if len(list)<2:
        return list
    else:
        midpivot = list[0]
        lessbeforemidpivot = [i for i in list[1:] if i<=midpivot]
        biggerafterpivot = [i for i in list[1:] if i > midpivot]
        finallylist = quicksort(lessbeforemidpivot)+[midpivot]+quicksort(biggerafterpivot)
        return finallylist

print quicksort([2,4,6,7,1,2,5])

更多排序问题可见：数据结构与算法-排序篇-Python描述

1
2
3
4
5
6
7
8

def qsort(seq):
    if seq==[]:
        return []
    else:
        pivot=seq[0]
        lesser=qsort([x for x in seq[1:] if x<pivot])
        greater=qsort([x for x in seq[1:] if x>=pivot])
        return lesser+[pivot]+greater

12 找零问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#coding:utf-8
#values是硬币的面值values = [ 25, 21, 10, 5, 1]
#valuesCounts   钱币对应的种类数
#money  找出来的总钱数
#coinsUsed   对应于目前钱币总数i所使用的硬币数目

def coinChange(values,valuesCounts,money,coinsUsed):
    #遍历出从1到money所有的钱数可能
    for cents in range(1,money+1):
        minCoins = cents
        #把所有的硬币面值遍历出来和钱数做对比
        for kind in range(0,valuesCounts):
            if (values[kind] <= cents):
                temp = coinsUsed[cents - values[kind]] +1
                if (temp < minCoins):
                    minCoins = temp
        coinsUsed[cents] = minCoins
        print ('面值:{0}的最少硬币使用数为:{1}'.format(cents, coinsUsed[cents]))

思路: http://blog.csdn.net/wdxin1322/article/details/9501163

方法: http://www.cnblogs.com/ChenxofHit/archive/2011/03/18/1988431.html

13 广度遍历和深度遍历二叉树

给定一个数组，构建二叉树，并且按层次打印这个二叉树

14 二叉树节点

1
2
3
4
5
6
7

class Node(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

tree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4)))

15 层次遍历

1
2
3
4
5

def lookup(root):
    row = [root]
    while row:
        print(row)
        row = [kid for item in row for kid in (item.left, item.right) if kid]

1
2
3
4
5
6
7
8
9

def lookup(root):
    stack = [root]
    while stack:
        current = stack.pop(0)
        print(current.data)
        if current.left:
            stack.append(current.left)
        if current.right:
            stack.append(current.right)

16 深度遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def deep(root):
    if not root:
        return
    print root.data
    deep(root.left)
    deep(root.right)

if __name__ == '__main__':
    lookup(tree)
    deep(tree)

17 前中后序遍历

深度遍历改变顺序就OK了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#coding:utf-8
#二叉树的遍历
#简单的二叉树节点类
class Node(object):
    def __init__(self,value,left,right):
        self.value = value
        self.left = left
        self.right = right

#中序遍历:遍历左子树,访问当前节点,遍历右子树

def mid_travelsal(root):
    if root.left is not None:
        mid_travelsal(root.left)
    #访问当前节点
    print(root.value)
    if root.right is not None:
        mid_travelsal(root.right)

#前序遍历:访问当前节点,遍历左子树,遍历右子树

def pre_travelsal(root):
    print (root.value)
    if root.left is not None:
        pre_travelsal(root.left)
    if root.right is not None:
        pre_travelsal(root.right)

#后续遍历:遍历左子树,遍历右子树,访问当前节点

def post_trvelsal(root):
    if root.left is not None:
        post_trvelsal(root.left)
    if root.right is not None:
        post_trvelsal(root.right)
    print (root.value)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def pre_order(root):
    if not root:
        return
    print(root.data)
    pre_order(root.left)
    pre_order(root.right)
		
def mid_order(root):
    if not root:
        return
    mid_order(root.left)
		    print(root.data)
    mid_order(root.right)
		
def las_order(root):
    if not root:
        return
    las_order(root.left)
    las_order(root.right)
          print(root.data)

18 求最大树深

1
2
3
4

def maxDepth(root):
        if not root:
            return 0
        return max(maxDepth(root.left), maxDepth(root.right)) + 1

19 求两棵树是否相同

1
2
3
4
5
6
7

def isSameTree(p, q):
    if p == None and q == None:
        return True
    elif p and q :
        return p.val == q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)
    else :
        return False

20 前序中序求后序

推荐: http://blog.csdn.net/hinyunsin/article/details/6315502

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def rebuild(pre, center):
    if not pre:
        return
    cur = Node(pre[0])
    index = center.index(pre[0])
    cur.left = rebuild(pre[1:index + 1], center[:index])
    cur.right = rebuild(pre[index + 1:], center[index + 1:])
    return cur

def deep(root):
    if not root:
        return
    deep(root.left)
    deep(root.right)
    print root.data

21 单链表逆置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Node(object):
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))

def rev(link):
    pre = link
    cur = link.next
    pre.next = None
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return pre

root = rev(link)
while root:
    print root.data
    root = root.next

思路: http://blog.csdn.net/feliciafay/article/details/6841115

方法: http://www.xuebuyuan.com/2066385.html?mobile=1

22 两个字符串是否是变位词

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

class Anagram:
    """
    @:param s1: The first string
    @:param s2: The second string
    @:return true or false
    """
    def Solution1(s1,s2):
        alist = list(s2)

        pos1 = 0
        stillOK = True

        while pos1 < len(s1) and stillOK:
            pos2 = 0
            found = False
            while pos2 < len(alist) and not found:
                if s1[pos1] == alist[pos2]:
                    found = True
                else:
                    pos2 = pos2 + 1

            if found:
                alist[pos2] = None
            else:
                stillOK = False

            pos1 = pos1 + 1

        return stillOK

    print(Solution1('abcd','dcba'))

    def Solution2(s1,s2):
        alist1 = list(s1)
        alist2 = list(s2)

        alist1.sort()
        alist2.sort()


        pos = 0
        matches = True

        while pos < len(s1) and matches:
            if alist1[pos] == alist2[pos]:
                pos = pos + 1
            else:
                matches = False

        return matches

    print(Solution2('abcde','edcbg'))

    def Solution3(s1,s2):
        c1 = [0]*26
        c2 = [0]*26

        for i in range(len(s1)):
            pos = ord(s1[i])-ord('a')
            c1[pos] = c1[pos] + 1

        for i in range(len(s2)):
            pos = ord(s2[i])-ord('a')
            c2[pos] = c2[pos] + 1

        j = 0
        stillOK = True
        while j<26 and stillOK:
            if c1[j] == c2[j]:
                j = j + 1
            else:
                stillOK = False

        return stillOK

    print(Solution3('apple','pleap'))

23 动态规划问题

可参考：动态规划(DP)的整理-Python描述