Python面試攻略（coding篇）

知識 08-28

點擊上方「

Python開發

」，選擇「置頂公眾號」

關鍵時刻，第一時間送達！

來源：DataCastle數據城堡（ID：DataCastle2016）

https://blog.csdn.net/u013205877/article/details/77542837

https://github.com/taizilongxu/interview_python

python開發整理髮布，轉載請聯繫作者獲得授權

寫在前面

之前為各位小夥伴推出了python面試（嗨談篇）的內容，主要為各位小夥伴介紹了一些關於python面試中經常出現的概念性問題，那麼今天就要從代碼入手了，讓各位Pythoner在面試的時候遇到這些代碼問題也能完全不慌亂，從容解決。

當然，如果你在面試的過程中，正巧遇到了這其中沒提及的問題，你認為比較有意思的，也可以在後面的留言板中分享出來讓別的小夥伴參考一下看看~

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
 range(n):
       a, b = b, a + b
   return
 b

2.去除列表中的重複元素

用集合

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
 = []
[l2.append(i) for i in l1 if not i in l2]

3.合併兩個有序列表

尾遞歸

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

pop彈出

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

4.二分查找

#coding:utf-8


def
 binary_search
(list,item)
:

   low = 0

   high = len(list)-1

   while
 low<=high:
       mid = int((low+high)/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

5.快排

#codin

g: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
]))

參考：

https://blog.csdn.net/mrlevo520/article/details/77829204

6.使用python實現單例模式

方法一:可以使用__new__方法

在__new__方法中把類實例綁定到類變數_instance上，如果cls._instance為None表示該類還沒有實例化過，實例化該類並返回。如果cls_instance不為None表示該類已實例化，直接返回cls_instance

class

 SingleTon
(object)
:

   
def
 __new__
(cls,*args,**kwargs)
:

       if
 not
 hasattr(cls,"_instance"
):
           cls._instance = object.__new__(cls,*args,**kwargs)
       return
 cls._instance
class
 TestClass
(SingleTon)
:

   a = 1

test1 = TestClass()
test2 = TestClass()
print
 (test1.a,test2.a)
test1.a=
2

print
 (test1.a,test2.a)
print
 (id(test1),id(test2))

方法二:使用裝飾器,建立過實例的就放到instances裡面,下次建立的時候先檢查裡面有沒有

def

 SingleTon
(cls,*args,**kwargs)
:

   instances = {}
   print
 (instances)
   
def
 _singleton
()
:

       if
 cls not
 in
 instances:
           instances[cls] = cls(*args,**kwargs)
       print
 (instances)
       return
 instances[cls]
   return
 _singleton
@SingleTon

class
 LastClass
(object)
:

   a = 1

test1 = LastClass()
print
 (test1.a)
test2 = LastClass()
print
 (test2.a)

方法三:使用__metaclass__(元類)關於元類看看這個吧:http://blog.jobbole.com/21351/

class

 SignalTon
(type)
:

   
def
 __init__
(cls,name,bases,dict)
:

       super(SignalTon, cls).__init__(name,bases,dict)
       cls._instance = None

   
def
 __call__
(cls, *args, **kwargs)
:

       if
 cls._instance is
 None
:
           cls._instance = super(SignalTon,cls).__call__(*args,**kwargs)
       return
 cls._instance
class
 TestClass
(object)
:

   __metaclass__ = SignalTon
test1 = TestClass()
test2 = TestClass()
test1.a = 
2

print
 (test1.a,test2.a)
print
 (id(test1),id(test2))

方法四:共享屬性

所謂單例就是所有的引用（實例，對象）擁有相同的屬性和方法，同一個類的實例天生都會有相同的方法，那我們只需要保證同一個類所產生的實例都具有相同的屬性。所有實例共享屬性最簡單直接的方法就是共享__dict__屬性指向。

class

 SingleTon
(object)
:

   _state = {}
   
def
 __new__
(cls, *args, **kwargs)
:

       obj = object.__new__(cls,*args,**kwargs)
       obj.__dict__ = cls._state
       return
 obj
class
 TestClass
(SingleTon)
:

   a = 1

test1 = TestClass()
test2 = TestClass()
print
 (test1.a,test2.a)
test1.a = 2

print
 (test1.a,test2.a)
print
 (id(test1),id(test2))

方法五:使用同一個模版，寫在mysingleton.py中

class

 My_Singleton
(object)
:

   
def
 foo
(self)
:

       pass

my_singleton = My_Singleton()
#寫在要使用這個實例的py文件裡面,在不同的引用的地方都引用相同的實例,以此實現單例模式

from
 mysingleton import
 my_singleton
my_singleton.foo()

7.前中後序遍歷

深度遍歷改變順序就好了

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

8.super函數的原理

#閱讀下面的代碼，它的輸出結果是什麼？


class
 A
(object)
:

 
def
 __init__
(self)
:

  print
 
("enter A")

  super(A, self).__init__()  
# new

  
print
 ("leave A")

class
 B
(object)
:

 
def
 __init__
(self)
:

  
print
 ("enter B")

  super(B, self).__init__()  
# new

  
print
 ("leave B")

class
 C
(A)
:

 
def
 __init__
(self)
:

  
print
 ("enter C")

  super(C, self).__init__()

  
print
 ("leave C")

class
 D
(A)
:

 
def
 __init__
(self)
:

  
print
 ("enter D")

  super(D, self).__init__()

  
print
 ("leave D")

class
 E
(B, C)
:

 
def
 __init__
(self)
:

  
print
 ("enter E")

  super(E, self).__init__()  
# change

  
print
 ("leave E")

class
 F
(E, D)
:

 
def
 __init__
(self)
:

  
print
 ("enter F")

  super(F, self).__init__()  
# change

  
print
 ("leave F")

#輸出

enter F

enter E

enter B

enter C

enter D

enter A

leave A

leave D

leave C

leave B

leave E

leave F

參考：

http://www.cnblogs.com/lovemo1314/archive/2011/05/03/2035005.html

【點擊成為Java大神】

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！

請您繼續閱讀更多來自 Python開發 的精彩文章:

※告訴你三個抗衰老的方法
※你同意誰的說法？

TAG:Python開發 |