python語言特性及面試知識點總結

1 Python的函數參數傳遞

看兩個例子:

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

所有的變量都可以了解是記憶體中一個對象的“引用”，或者，也可以看似c中void*的感覺。

通過id來看引用a的記憶體位址可以比較了解：

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引用儲存的記憶體值就不會發生變化：

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等則是可以修改的對象。(這就是這個問題的重點)

當一個引用傳遞給函數的時候,函數自動複制一份引用,這個函數裡的引用和外邊的引用沒有半毛關系了.是以第一個例子裡函數把引用指向了一個不可變對象,當函數傳回的時候,外面的引用沒半毛感覺.而第二個例子就不一樣了,函數内的引用指向的是可變對象,對它的操作就和定位了指針位址一樣,在記憶體裡進行修改.

如果還不明白的話,這裡有更好的解釋:  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)和執行個體方法,如下:

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)

更多關于這個問題: http://stackoverflow.com/questions/136097/what-is-the-difference-between-staticmethod-and-classmethod-in-python

4 類變量和執行個體變量

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了.

可以看看下面的例子:

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().

6 字典推導式

可能你見過清單推導時,卻沒有見過字典推導式,在2.7中才加入的:

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

7 Python中單下劃線和雙下劃線

>>> 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内部的名字,用來差別其他使用者自定義的命名,以防沖突.

_foo:一種約定,用來指定變量私有.程式員用來指定私有變量的一種方式.

__foo:這個有真正的意義:解析器用_classname__foo來代替這個名字,以差別和其他類相同的命名.

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

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

.format在許多方面看起來更便利.對于%最煩人的是它無法同時傳遞一個變量和元組.你可能會想下面的代碼不會有什麼問題:

"hi there %s" % name

但是,如果name恰好是(1,2,3),它将會抛出一個TypeError異常.為了保證它總是正确的,你必須這樣做:

"hi there %s" % (name,) # 提供一個單元素的數組而不是一個參數

但是有點醜..format就沒有這些問題.你給的第二個問題也是這樣,.format好看多了.

你為什麼不用它?

不知道它(在讀這個之前)

為了和Python2.5相容(譬如logging庫建議使用%(issue #4))

9 疊代器和生成器

這個是stackoverflow裡python排名第一的問題,值得一看:  http://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python

10 *args and **kwargs

用*args和**kwargs隻是為了友善并沒有強制使用它們.

當你不确定你的函數裡将要傳遞多少參數時你可以用*args.例如,它可以傳遞任意數量的參數:

>>> 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允許你使用沒有事先定義的參數名:

>>> 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.命名參數在清單的最前端.例如:

def table_things(titlestring, **kwargs)
           

*args和**kwargs可以同時在函數的定義中,但是*args必須在**kwargs前面.

當調用函數時你也可以用*和**文法.例如:

>>> 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一聽起來有點懵,同學面阿裡的時候就被問懵了...

裝飾器是一個很著名的設計模式，經常被用于有切面需求的場景，較為經典的有插入日志、性能測試、事務處理等。裝飾器是解決這類問題的絕佳設計，有了裝飾器，我們就可以抽離出大量函數中與函數功能本身無關的雷同代碼并繼續重用。概括的講，裝飾器的作用就是為已經存在的對象添加額外的功能。

這個問題比較大,推薦:  http://stackoverflow.com/questions/739654/how-can-i-make-a-chain-of-function-decorators-in-python

12 鴨子類型

“當看到一隻鳥走起來像鴨子、遊泳起來像鴨子、叫起來也像鴨子，那麼這隻鳥就可以被稱為鴨子。”

我們并不關心對象是什麼類型，到底是不是鴨子，隻關心行為。

比如在python中，有很多file-like的東西，比如StringIO,GzipFile,socket。它們有很多相同的方法，我們把它們當作檔案使用。

又比如list.extend()方法中,我們并不關心它的參數是不是list,隻要它是可疊代的,是以它的參數可以是list/tuple/dict/字元串/生成器等.

鴨子類型在動态語言中經常使用，非常靈活，使得python不想java那樣專門去弄一大堆的設計模式。

13 Python中重載

函數重載主要是為了解決兩個問題。

可變參數類型。

可變參數個數。

另外，一個基本的設計原則是，僅僅當兩個函數除了參數類型和參數個數不同以外，其功能是完全相同的，此時才使用函數重載，如果兩個函數的功能其實不同，那麼不應當使用重載，而應當使用一個名字不同的函數。

好吧，那麼對于情況 1 ，函數功能相同，但是參數類型不同，python 如何處理？答案是根本不需要處理，因為 python 可以接受任何類型的參數，如果函數的功能相同，那麼不同的參數類型在 python 中很可能是相同的代碼，沒有必要做成兩個不同函數。

那麼對于情況 2 ，函數功能相同，但參數個數不同，python 如何處理？大家知道，答案就是預設參數。對那些缺少的參數設定為預設參數即可解決問題。因為你假設函數功能相同，那麼那些缺少的參數終歸是需要用的。

好了，鑒于情況 1 跟 情況 2 都有了解決方案，python 自然就不需要函數重載了。

14 新式類和舊式類

這個面試官問了,我說了老半天,不知道他問的真正意圖是什麼.

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

新式類很早在2.2就出現了,是以舊式類完全是相容的問題,Python3裡的類全部都是新式類.這裡有一個MRO問題可以了解下(新式類是廣度優先,舊式類是深度優先),<Python核心程式設計>裡講的也很多.

15 __new__和__init__的差別

這個__new__确實很少見到,先做了解吧.

__new__是一個靜态方法,而__init__是一個執行個體方法.

__new__方法會傳回一個建立的執行個體,而__init__什麼都不傳回.

隻有在__new__傳回一個cls的執行個體時後面的__init__才能被調用.

當建立一個新執行個體時調用__new__,初始化一個執行個體時用__init__.

ps: __metaclass__是建立類時起作用.是以我們可以分别使用__metaclass__,__new__和__init__來分别在類建立,執行個體建立和執行個體初始化的時候做一些小手腳.

16 單例模式

這個絕對常考啊.絕對要記住1~2個方法,當時面試官是讓手寫的.

1 使用__new__方法

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__指向同一個字典,這樣它們具有相同的屬性和方法.

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 裝飾器方式

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

@singleton
class MyClass:
  ...
           

4 import方法

作為python的子產品是天然的單例模式

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

my_singleton = My_Singleton()

# 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為了保證線程安全而采取的獨立線程運作的限制,說白了就是一個核隻能在同一時間運作一個線程.

見Python 最難的問題

解決辦法就是多程序和下面的協程(協程也隻是單CPU,但是能減小切換代價提升性能).

19 協程

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

簡單點說協程是程序和線程的更新版,程序和線程都面臨着核心态和使用者态的切換問題而耗費許多切換時間,而協程就是使用者自己控制切換的時機,不再需要陷入系統的核心态.

Python裡最常見的yield就是協程的思想!可以檢視第九個問題.

20 閉包

閉包(closure)是函數式程式設計的重要的文法結構。閉包也是一種組織代碼的結構，它同樣提高了代碼的可重複使用性。

當一個内嵌函數引用其外部作作用域的變量,我們就會得到一個閉包. 總結一下,建立一個閉包必須滿足以下幾點:

必須有一個内嵌函數

内嵌函數必須引用外部函數中的變量

外部函數的傳回值必須是内嵌函數

感覺閉包還是有難度的,幾句話是說不明白的,還是查查相關資料.

重點是函數運作後并不會被撤銷,就像16題的instance字典一樣,當函數運作完後,instance并不被銷毀,而是繼續留在記憶體空間裡.這個功能類似類裡的類變量,隻不過遷移到了函數上.

閉包就像個空心球一樣,你知道外面和裡面,但你不知道中間是什麼樣.

21 lambda函數

其實就是一個匿名函數,為什麼叫lambda?因為和後面的函數式程式設計有關.

推薦: 知乎

22 Python函數式程式設計

這個需要适當的了解一下吧,畢竟函數式程式設計在Python中也做了引用.

推薦: 酷殼

python中函數式程式設計支援:

filter 函數的功能相當于過濾器。調用一個布爾函數bool_func來疊代周遊每個seq中的元素；傳回一個使bool_seq傳回值為true的元素的序列。

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

map函數是對一個序列的每個項依次執行函數，下面是對一個序列每個項都乘以2：

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

reduce函數是對一個序列的每個項疊代調用函數，下面是求3的階乘：

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

23 Python裡的拷貝

引用和copy(),deepcopy()的差別

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時，該對象生命就結束了。

優點:

簡單

實時性

缺點:

維護引用計數消耗資源

循環引用

2 标記-清除機制

基本思路是先按需配置設定，等到沒有空閑記憶體的時候從寄存器和程式棧上的引用出發，周遊以對象為節點、以引用為邊構成的圖，把所有可以通路到的對象打上标記，然後清掃一遍記憶體空間，把所有沒标記的對象釋放。

3 分代技術

分代回收的整體思想是：将系統中的所有記憶體塊根據其存活時間劃分為不同的集合，每個集合就成為一個“代”，垃圾收集頻率随着“代”的存活時間的增大而減小，存活時間通常利用經過幾次垃圾回收來度量。

Python預設定義了三代對象集合，索引數越大，對象存活時間越長。

舉例：

當某些記憶體塊M經過了3次垃圾收集的清洗之後還存活時，我們就将記憶體塊M劃到一個集合A中去，而新配置設定的記憶體都劃分到集合B中去。當垃圾收集開始工作時，大多數情況都隻對集合B進行垃圾回收，而對集合A進行垃圾回收要隔相當長一段時間後才進行，這就使得垃圾收集機制需要處理的記憶體少了，效率自然就提高了。在這個過程中，集合B中的某些記憶體塊由于存活時間長而會被轉移到集合A中，當然，集合A中實際上也存在一些垃圾，這些垃圾的回收會因為這種分代的機制而被延遲。

25 Python的List

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

26 Python的is

is是對比位址,==是對比值

27 read,readline和readlines

read 讀取整個檔案

readline 讀取下一行,使用生成器方法

readlines 讀取整個檔案到一個疊代器以供我們周遊

28 Python2和3的差別

推薦： python2.7.x與python3.x的主要差異

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

30 range and xrange

都在循環時使用，xrange記憶體性能更好。

for i in range(0, 20):

for i in xrange(0, 20):

range建立的是一個20個元素的清單

xrange建立的是生成器，效率比較低

作業系統

1 select,poll和epoll

其實所有的I/O都是輪詢的方法,隻不過實作的層面不同罷了.

這個問題可能有點深入了,但相信能回答出這個問題是對I/O多路複用有很好的了解了.其中tornado使用的就是epoll的.

selec,poll和epoll差別總結

基本上select有3個缺點:

連接配接數受限

查找配對速度慢

資料由核心拷貝到使用者态

poll改善了第一個缺點

epoll改了三個缺點.

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

2 排程算法

先來先服務(FCFS, First Come First Serve)

短作業優先(SJF, Shortest Job First)

最高優先權排程(Priority Scheduling)

時間片輪轉(RR, Round Robin)

多級回報隊列排程(multilevel feedback queue scheduling)

實時排程算法:

最早截至時間優先 EDF

最低松弛度優先 LLF

3 死鎖

原因:

競争資源

程式推進順序不當

必要條件:

互斥條件

請求和保持條件

不剝奪條件

環路等待條件

處理死鎖基本方法:

預防死鎖(摒棄除1以外的條件)

避免死鎖(銀行家算法)

檢測死鎖(資源配置設定圖)

解除死鎖

剝奪資源

撤銷程序

4 程式編譯與連結

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

Bulid過程可以分解為4個步驟:預處理(Prepressing), 編譯(Compilation)、彙編(Assembly)、連結(Linking)

以c語言為例:

1 預處理

預編譯過程主要處理那些源檔案中的以“#”開始的預編譯指令，主要處理規則有：

将所有的“#define”删除，并展開所用的宏定義

處理所有條件預編譯指令，比如“#if”、“#ifdef”、 “#elif”、“#endif”

處理“#include”預編譯指令，将被包含的檔案插入到該編譯指令的位置，注：此過程是遞歸進行的

删除所有注釋

添加行号和檔案名辨別，以便于編譯時編譯器産生調試用的行号資訊以及用于編譯時産生編譯錯誤或警告時可顯示行号

保留所有的#pragma編譯器指令。

2 編譯

編譯過程就是把預處理完的檔案進行一系列的詞法分析、文法分析、語義分析及優化後生成相應的彙編代碼檔案。這個過程是整個程式建構的核心部分。

3 彙編

彙編器是将彙編代碼轉化成機器可以執行的指令，每一條彙編語句幾乎都是一條機器指令。經過編譯、連結、彙編輸出的檔案成為目标檔案(Object File)

4 連結

連結的主要内容就是把各個子產品之間互相引用的部分處理好，使各個子產品可以正确的拼接。

連結的主要過程包塊 位址和空間的配置設定（Address and Storage Allocation）、符号決議(Symbol Resolution)和重定位(Relocation)等步驟。

5 靜态連結和動态連結

靜态連結方法：靜态連結的時候，載入代碼就會把程式會用到的動态代碼或動态代碼的位址确定下來

靜态庫的連結可以使用靜态連結，動态連結庫也可以使用這種方法連結導入庫

動态連結方法：使用這種方式的程式并不在一開始就完成動态連結，而是直到真正調用動态庫代碼時，載入程式才計算(被調用的那部分)動态代碼的邏輯位址，然後等到某個時候，程式又需要調用另外某塊動态代碼時，載入程式又去計算這部分代碼的邏輯位址，是以，這種方式使程式初始化時間較短，但運作期間的性能比不上靜态連結的程式

6 虛拟記憶體技術

虛拟存儲器是指具有請求調入功能和置換功能,能從邏輯上對記憶體容量加以擴充的一種存儲系統.

7 分頁和分段

分頁: 使用者程式的位址空間被劃分成若幹固定大小的區域，稱為“頁”，相應地，記憶體空間分成若幹個實體塊，頁和塊的大小相等。可将使用者程式的任一頁放在記憶體的任一塊中，實作了離散配置設定。

分段: 将使用者程式位址空間分成若幹個大小不等的段，每段可以定義一組相對完整的邏輯資訊。存儲配置設定時，以段為機關，段與段在記憶體中可以不相鄰接，也實作了離散配置設定。

分頁與分段的主要差別

頁是資訊的實體機關,分頁是為了實作非連續配置設定,以便解決記憶體碎片問題,或者說分頁是由于系統管理的需要.段是資訊的邏輯機關,它含有一組意義相對完整的資訊,分段的目的是為了更好地實作共享,滿足使用者的需要.

頁的大小固定,由系統确定,将邏輯位址劃分為頁号和頁内位址是由機器硬體實作的.而段的長度卻不固定,決定于使用者所編寫的程式,通常由編譯程式在對源程式進行編譯時根據資訊的性質來劃分.

分頁的作業位址空間是一維的.分段的位址空間是二維的.

8 頁面置換算法

最佳置換算法OPT:不可能實作

先進先出FIFO

最近最久未使用算法LRU:最近一段時間裡最久沒有使用過的頁面予以置換.

clock算法

9 邊沿觸發和水準觸發

邊緣觸發是指每當狀态變化時發生一個 io 事件，條件觸發是隻要滿足條件就發生一個 io 事件

資料庫

1 事務

資料庫事務(Database Transaction) ，是指作為單個邏輯工作單元執行的一系列操作，要麼完全地執行，要麼完全地不執行。

2 資料庫索引

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

MySQL索引背後的資料結構及算法原理

聚集索引,非聚集索引,B-Tree,B+Tree,最左字首原理

3 Redis原理

4 樂觀鎖和悲觀鎖

悲觀鎖：假定會發生并發沖突，屏蔽一切可能違反資料完整性的操作

樂觀鎖：假設不會發生并發沖突，隻在送出操作時檢查是否違反資料完整性。

5 MVCC

6 MyISAM和InnoDB

MyISAM 适合于一些需要大量查詢的應用，但其對于有大量寫操作并不是很好。甚至你隻是需要update一個字段，整個表都會被鎖起來，而别的程序，就算是讀程序都無法操作直到讀操作完成。另外，MyISAM 對于 SELECT COUNT(*) 這類的計算是超快無比的。

InnoDB 的趨勢會是一個非常複雜的存儲引擎，對于一些小的應用，它會比 MyISAM 還慢。他是它支援“行鎖” ，于是在寫操作比較多的時候，會更優秀。并且，他還支援更多的進階應用，比如：事務。

網絡

1 三次握手

用戶端通過向伺服器端發送一個SYN來建立一個主動打開，作為三路握手的一部分。用戶端把這段連接配接的序号設定為随機數 A。

伺服器端應當為一個合法的SYN回送一個SYN/ACK。ACK 的确認碼應為 A+1，SYN/ACK 包本身又有一個随機序号 B。

最後，用戶端再發送一個ACK。當服務端受到這個ACK的時候，就完成了三路握手，并進入了連接配接建立狀态。此時包序号被設定為收到的确認号 A+1，而響應則為 B+1。

2 四次揮手

注意: 中斷連接配接端可以是用戶端，也可以是伺服器端. 下面僅以用戶端斷開連接配接舉例, 反之亦然.

用戶端發送一個資料分段, 其中的 FIN 标記設定為1. 用戶端進入 FIN-WAIT 狀态. 該狀态下用戶端隻接收資料, 不再發送資料.

伺服器接收到帶有 FIN = 1 的資料分段, 發送帶有 ACK = 1 的剩餘資料分段, 确認收到用戶端發來的 FIN 資訊.

伺服器等到所有資料傳輸結束, 向用戶端發送一個帶有 FIN = 1 的資料分段, 并進入 CLOSE-WAIT 狀态, 等待用戶端發來帶有 ACK = 1 的确認封包.

用戶端收到伺服器發來帶有 FIN = 1 的封包, 傳回 ACK = 1 的封包确認, 為了防止伺服器端未收到需要重發, 進入 TIME-WAIT 狀态. 伺服器接收到封包後關閉連接配接. 用戶端等待 2MSL 後未收到回複, 則認為伺服器成功關閉, 用戶端關閉連接配接.

3 ARP協定

位址解析協定(Address Resolution Protocol)，其基本功能為透過目标裝置的IP位址，查詢目标的MAC位址，以保證通信的順利進行。它是IPv4網絡層必不可少的協定，不過在IPv6中已不再适用，并被鄰居發現協定（NDP）所替代。

4 urllib和urllib2的差別

這個面試官确實問過,當時答的urllib2可以Post而urllib不可以.

urllib提供urlencode方法用來GET查詢字元串的産生，而urllib2沒有。這是為何urllib常和urllib2一起使用的原因。

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

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 網站使用者密碼儲存

明文儲存

明文hash後儲存,如md5

MD5+Salt方式,這個salt可以随機

知乎使用了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 ，不會改變資源的狀态，不論調用一次還是N次都沒有副作用。請注意，這裡強調的是一次和N次具有相同的副作用，而不是每次GET的結果相同。GET http://www.newsjoe.com/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這個名字的由來）。

推薦: 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

20 HTTP1.0和HTTP1.1

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

請求頭Host字段,一個伺服器多個網站

長連結

檔案斷點續傳

身份認證,狀态管理,Cache緩存

21 Ajax

AJAX,Asynchronous JavaScript and XML（異步的 JavaScript 和 XML）, 是與在不重新加載整個頁面的情況下，與伺服器交換資料并更新部分網頁的技術。

*NIX

unix程序間通信方式(IPC)

管道（Pipe）：管道可用于具有親緣關系程序間的通信，允許一個程序和另一個與它有共同祖先的程序之間進行通信。

命名管道（named pipe）：命名管道克服了管道沒有名字的限制，是以，除具有管道所具有的功能外，它還允許無親緣關系程序間的通信。命名管道在檔案系統中有對應的檔案名。命名管道通過指令mkfifo或系統調用mkfifo來建立。

信号（Signal）：信号是比較複雜的通信方式，用于通知接受程序有某種事件發生，除了用于程序間通信外，程序還可以發送信号給程序本身；linux除了支援Unix早期信号語義函數sigal外，還支援語義符合Posix.1标準的信号函數sigaction（實際上，該函數是基于BSD的，BSD為了實作可靠信号機制，又能夠統一對外接口，用sigaction函數重新實作了signal函數）。

消息（Message）隊列：消息隊列是消息的連結表，包括Posix消息隊列system V消息隊列。有足夠權限的程序可以向隊列中添加消息，被賦予讀權限的程序則可以讀走隊列中的消息。消息隊列克服了信号承載資訊量少，管道隻能承載無格式位元組流以及緩沖區大小受限等缺

共享記憶體：使得多個程序可以通路同一塊記憶體空間，是最快的可用IPC形式。是針對其他通信機制運作效率較低而設計的。往往與其它通信機制，如信号量結合使用，來達到程序間的同步及互斥。

記憶體映射（mapped memory）：記憶體映射允許任何多個程序間通信，每一個使用該機制的程序通過把一個共享的檔案映射到自己的程序位址空間來實作它。

信号量（semaphore）：主要作為程序間以及同一程序不同線程之間的同步手段。

套接口（Socket）：更為一般的程序間通信機制，可用于不同機器之間的程序間通信。起初是由Unix系統的BSD分支開發出來的，但現在一般可以移植到其它類Unix系統上：Linux和System V的變種都支援套接字。

資料結構

1 紅黑樹

紅黑樹與AVL的比較：

AVL是嚴格平衡樹，是以在增加或者删除節點的時候，根據不同情況，旋轉的次數比紅黑樹要多；

紅黑是用非嚴格的平衡來換取增删節點時候旋轉次數的降低；

是以簡單說，如果你的應用中，搜尋的次數遠遠大于插入和删除，那麼選擇AVL，如果搜尋，插入删除次數幾乎差不多，應該選擇RB。

程式設計題

1 台階問題/斐波納挈

一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法。

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

第二種記憶方法

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)
           

第三種方法

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

2 變态台階問題

一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。

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)的方法。

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

4 楊氏矩陣查找

在一個m行n列二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

使用Step-wise線性搜尋。

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 去除清單中的重複元素

用集合

list(set(l))
           

用字典

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

用字典并保持順序

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

清單推導式

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

面試官提到的,先排序然後删除.

6 連結清單成對調換

1->2->3->4轉換成2->1->4->3.

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 直接建立

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

2 工廠方法

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

3 fromkeys()方法

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

8 合并兩個有序清單

知乎遠端面試要求程式設計

尾遞歸

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, [])
           

循環算法

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
           

9 交叉連結清單求交點

去哪兒的面試,沒做出來.

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
           

10 二分查找

def binarySearch(l, t):
    low, high = 0, len(l) - 1
    while low < high:
        print low, high
        mid = (low + high) / 2
        if l[mid] > t:
            high = mid
        elif l[mid] < t:
            low = mid + 1
        else:
            return mid
    return low if l[low] == t else False

if __name__ == '__main__':
    l = [1, 4, 12, 45, 66, 99, 120, 444]
    print binarySearch(l, 12)
    print binarySearch(l, 1)
    print binarySearch(l, 13)
    print binarySearch(l, 444)
           

11 快排

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

if __name__=='__main__':
    seq=[5,6,78,9,0,-1,2,3,-65,12]
    print(qsort(seq))
           

12 找零問題

def  coinChange(values, money, coinsUsed):
    #values    T[1:n]數組
    #valuesCounts   錢币對應的種類數
    #money  找出來的總錢數
    #coinsUsed   對應于目前錢币總數i所使用的硬币數目
    for cents in range(1, money+1):
        minCoins = cents     #從第一個開始到money的所有情況初始
        for value in values:
            if value <= cents:
                temp = coinsUsed[cents - value] + 1
                if temp < minCoins:
                    minCoins = temp
        coinsUsed[cents] = minCoins
        print('面值為：{0} 的最小硬币數目為：{1} '.format(cents, coinsUsed[cents]) )

if __name__ == '__main__':
    values = [ 25, 21, 10, 5, 1]
    money = 63
    coinsUsed = {i:0 for i in range(money+1)}
    coinChange(values, money, coinsUsed)
           

13 廣度周遊和深度周遊二叉樹

給定一個數組，建構二叉樹，并且按層次列印這個二叉樹

## 14 二叉樹節點
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 層次周遊
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 深度周遊
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了

18 求最大樹深

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

19 求兩棵樹是否相同

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

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 單連結清單逆置

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
           

22 兩個字元串是否是變位詞

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'))