Table of Contents

• Python語言特性
  • 1 Python的函數參數傳遞
  • 2 Python中的元類(metaclass)
  • 3 @staticmethod和@classmethod
  • 4 類變量和實例變量
  • 5 Python自省
  • 6 字典推導式
  • 7 Python中單下劃線和雙下劃線
  • 8 字符串格式化:%和.format
  • 9 迭代器和生成器
  • 10 *args and **kwargs
  • 11 面向切面編程AOP和裝飾器
  • 12 鴨子類型
  • 13 Python中重載
  • 14 新式類和舊式類
  • 15 __new__ 和 __init__ 的區別
  • 16 單例模式
    • 1 使用 __new__ 方法
    • 2 共享屬性
    • 3 裝飾器版本
  • 17 Python中的作用域
  • 18 GIL線程全局鎖
  • 19 協程
  • 20 閉包
  • 21 lambda函數
  • 22 Python函數式編程
  • 23 Python里的拷貝
  • 24 Python垃圾回收機制
    • 1 引用計數
    • 2 標記-清除機制
    • 3 分代技術
  • 25 Python的List
  • 26 Python的is
  • 27 read,readline和readlines
  • 28 Python2和3的區別
• 操作系統
  • 1 select,poll和epoll
  • 2 調度算法
  • 3 死鎖
  • 4 程序編譯與鏈接
    • 1 預處理
    • 2 編譯
    • 3 匯編
    • 4 鏈接
  • 5 靜態鏈接和動態鏈接
  • 6 虛擬內存技術
  • 7 分頁和分段
    • 分頁與分段的主要區別
  • 8 頁面置換算法
  • 9 邊沿觸發和水平觸發
• 數據庫
  • 1 事務
  • 2 數據庫索引
  • 3 Redis原理
  • 4 樂觀鎖和悲觀鎖
  • 5 MVCC
  • 6 MyISAM和InnoDB
• 網絡
  • 1 三次握手
  • 2 四次揮手
  • 3 ARP協議
  • 4 urllib和urllib2的區別
  • 5 Post和Get
  • 6 Cookie和Session
  • 7 apache和nginx的區別
  • 8 網站用戶密碼保存
  • 9 HTTP和HTTPS
  • 10 XSRF和XSS
  • 11 冪等 Idempotence
  • 12 RESTful架構(SOAP,RPC)
  • 13 SOAP
  • 14 RPC
  • 15 CGI和WSGI
  • 16 中間人攻擊
  • 17 c10k問題
  • 18 socket
  • 19 瀏覽器緩存
  • 20 HTTP1.0和HTTP1.1
  • 21 Ajax
• *NIX
  • unix進程間通信方式(IPC)
• 數據結構
  • 1 紅黑樹
• 編程題
  • 1 臺階問題/斐波納挈
  • 2 變態臺階問題
  • 3 矩形覆蓋
  • 4 楊氏矩陣查找
  • 5 去除列表中的重復元素
  • 6 鏈表成對調換
  • 7 創建字典的方法
    • 1 直接創建
    • 2 工廠方法
    • 3 fromkeys()方法
  • 8 合并兩個有序列表
  • 9 交叉鏈表求交點
  • 10 二分查找
  • 11 快排
  • 12 找零問題
  • 13 廣度遍歷和深度遍歷二叉樹
  • 14 二叉樹節點
  • 15 層次遍歷
  • 16 深度遍歷
  • 17 前中后序遍歷
  • 18 求最大樹深
  • 19 求兩棵樹是否相同
  • 20 前序中序求后序
  • 21 單鏈表逆置

Python語言特性

1 Python的函數參數傳遞

看兩個例子:

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

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

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

這里記住的是類型是屬于對象的，而不是變量。而對象有兩種,“可更改”（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()</pre> 
 
 這里先理解下函數參數里面的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</pre> 
 
類變量就是供類使用的變量,實例變量就是供實例使用的.

 這里 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]</pre> 
 
 參考: 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 
 或者: http://www.zhihu.com/question/19754941 
8 字符串格式化:%和.format 
 .format在許多方面看起來更便利.對于 % 最煩人的是它無法同時傳遞一個變量和元組.你可能會想下面的代碼不會有什么問題: 
"hi there %s" % name
 
 
但是,如果name恰好是(1,2,3),它將會拋出一個TypeError異常.為了保證它總是正確的,你必須這樣做:

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


apple
banana
cabbage</pre>
 相似的, **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</pre> 
 
就像你看到的一樣,它可以傳遞列表(或者元組)的每一項并把它們解包.注意必須與它們在函數里的參數相吻合.當然,你也可以在函數定義或者函數調用時用*.

 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 
 中文: 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那樣專門去弄一大堆的設計模式。
13 Python中重載 
 引自知乎: http://www.zhihu.com/question/20053359 
函數重載主要是為了解決兩個問題。
 
  
可變參數類型。

  
可變參數個數。

 
另外，一個基本的設計原則是，僅僅當兩個函數除了參數類型和參數個數不同以外，其功能是完全相同的，此時才使用函數重載，如果兩個函數的功能其實不同，那么不應當使用重載，而應當使用一個名字不同的函數。
好吧，那么對于情況 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問題可以了解下(新式類是廣度優先,舊式類是深度優先),里講的也很多.
 15 __new__ 和 __init__ 的區別 
 這個 __new__ 確實很少見到,先做了解吧. 
 
  
 __new__ 是一個靜態方法,而 __init__ 是一個實例方法. 

  
 __new__ 方法會返回一個創建的實例,而 __init__ 什么都不返回. 

  
 只有在 __new__ 返回一個cls的實例時后面的 __init__ 才能被調用. 

  
 當創建一個新實例時調用 __new__ ,初始化一個實例時用 __init__ . 

 
 stackoverflow 
 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</pre> 
 
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</pre> 
 
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:
  ...</pre> 
 
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()</pre> 
 
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']]</pre> 
 
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的區別 
操作系統 
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 調度算法 
 
  
先來先服務

  
短作業優先

  
最高優先權調度

  
時間片輪轉

  
多級反饋隊列調度

 
實時調度算法:
 
  
最早截至時間優先 EDF

  
最低松弛度優先 LLF

 
原因:
 
  
競爭資源

  
程序推進順序不當

 
必要條件:
 
  
互斥條件

  
請求和保持條件

  
不剝奪條件

  
環路等待條件

 
處理死鎖基本方法:
 
  
預防死鎖(摒棄除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編譯器指令。

 
編譯過程就是把預處理完的文件進行一系列的詞法分析、語法分析、語義分析及優化后生成相應的匯編代碼文件。這個過程是整個程序構建的核心部分。
匯編器是將匯編代碼轉化成機器可以執行的指令，每一條匯編語句幾乎都是一條機器指令。經過編譯、鏈接、匯編輸出的文件成為目標文件(Object File)
鏈接的主要內容就是把各個模塊直接愛你相互引用的部分處理好，使各個模塊可以正確的拼接。 鏈接的主要過程包塊 地址和空間的分配（Address and Storage Allocation）、符號決議(Symbol Resolution)和重定位(Relocation)等步驟。
5 靜態鏈接和動態鏈接 
靜態鏈接方法：靜態鏈接的時候，載入代碼就會把程序會用到的動態代碼或動態代碼的地址確定下來 靜態庫的鏈接可以使用靜態鏈接，動態鏈接庫也可以使用這種方法鏈接導入庫
動態鏈接方法：使用這種方式的程序并不在一開始就完成動態鏈接，而是直到真正調用動態庫代碼時，載入程序才計算(被調用的那部分)動態代碼的邏輯地址，然后等到某個時候，程序又需要調用另外某塊動態代碼時，載入程序又去計算這部分代碼的邏輯地址，所以，這種方式使程序初始化時間較短，但運行期間的性能比不上靜態鏈接的程序
6 虛擬內存技術 
虛擬存儲器是值具有請求調入功能和置換功能,能從邏輯上對內存容量加以擴充的一種存儲系統.
7 分頁和分段 
分頁: 用戶程序的地址空間被劃分成若干固定大小的區域，稱為“頁”，相應地，內存空間分成若干個物理塊，頁和塊的大小相等。可將用戶程序的任一頁放在內存的任一塊中，實現了離散分配。
分段: 將用戶程序地址空間分成若干個大小不等的段，每段可以定義一組相對完整的邏輯信息。存儲分配時，以段為單位，段與段在內存中可以不相鄰接，也實現了離散分配。
分頁與分段的主要區別 
 
  
頁是信息的物理單位,分頁是為了實現非連續分配,以便解決內存碎片問題,或者說分頁是由于系統管理的需要.段是信息的邏輯單位,它含有一組意義相對完整的信息,分段的目的是為了更好地實現共享,滿足用戶的需要.

  
頁的大小固定,由系統確定,將邏輯地址劃分為頁號和頁內地址是由機器硬件實現的.而段的長度卻不固定,決定于用戶所編寫的程序,通常由編譯程序在對源程序進行編譯時根據信息的性質來劃分.

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

 
8 頁面置換算法 
 
  
最佳置換算法OPT:不可能實現

  
先進先出FIFO

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

  
clock算法

 
9 邊沿觸發和水平觸發 
邊緣觸發是指每當狀態變化時發生一個 io 事件，條件觸發是只要滿足條件就發生一個 io 事件
數據庫事務(Database Transaction) ，是指作為單個邏輯工作單元執行的一系列操作，要么完全地執行，要么完全地不執行。
2 數據庫索引 
 推薦: http://tech.meituan.com/mysql-index.html 
 MySQL索引背后的數據結構及算法原理 
聚集索引,非聚集索引,B-Tree,B+Tree,最左前綴原理
3 Redis原理 
4 樂觀鎖和悲觀鎖 
悲觀鎖：假定會發生并發沖突，屏蔽一切可能違反數據完整性的操作
樂觀鎖：假設不會發生并發沖突，只在提交操作時檢查是否違反數據完整性。
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 四次揮手 
3 ARP協議 
地址解析協議(Address Resolution Protocol): 根據IP地址獲取物理地址的一個TCP/IP協
4 urllib和urllib2的區別 
這個面試官確實問過,當時答的urllib2可以Post而urllib不可以.
 
  
urllib提供urlencode方法用來GET查詢字符串的產生，而urllib2沒有。這是為何urllib常和urllib2一起使用的原因。

  
urllib2可以接受一個Request類的實例來設置URL請求的headers，urllib僅可以接受URL。這意味著，你不可以偽裝你的User Agent字符串等。

 
5 Post和Get 
6 Cookie和Session 
7 apache和nginx的區別 
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 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格式執行資料互換，使其抽象于語言實現、平臺和硬件。
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 
16 中間人攻擊 
在GFW里屢見不鮮的,呵呵.
中間人攻擊（Man-in-the-middle attack，通常縮寫為MITM）是指攻擊者與通訊的兩端分別創建獨立的聯系，并交換其所收到的數據，使通訊的兩端認為他們正在通過一個私密的連接與對方直接對話，但事實上整個會話都被攻擊者完全控制。
17 c10k問題 
所謂c10k問題，指的是服務器同時支持成千上萬個客戶端的問題，也就是concurrent 10 000 connection（這也是c10k這個名字的由來）。
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 
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: 1 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)</pre> 
 
第三種方法

def fib(n):
    a, b = 0, 1
    while a < n:
        print a,
        a, b  = b, a + b
    print
fib(1000)
 
 
2 變態臺階問題 

一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
fib = lambda n: i 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列二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。
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</pre> 

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, [])</pre> 
 
循環算法

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</pre> 

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 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)</pre> 
 
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))</pre> 
 
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)</pre> 
 
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)</pre> 
 
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</pre> 
 
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</pre> </article>