歡迎光臨
每天分享高質量文章

Python面試攻略(coding篇)

來源:DataCastle資料城堡(ID:DataCastle2016)

寫在前面

之前為各位小夥伴推出了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            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.快排

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

參考: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

參考來源:

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

https://github.com/taizilongxu/interview_python



編號491,輸入編號直達本文

●輸入m獲取文章目錄

推薦↓↓↓

Web開發

更多推薦18個技術類微信公眾號

涵蓋:程式人生、演演算法與資料結構、駭客技術與網路安全、大資料技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、資料庫、運維等。

贊(0)

分享創造快樂