歡迎光臨
每天分享高質量文章
當前位置：知識星球 > 後端 > 正文

Python面試攻略（coding篇）

2018-08-24 分類：後端 閱讀(357) 評論(0)
來源：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)
標籤：

相關推薦

熱門標籤

iOS (11238)微軟 (4955)Linux (4274)安全 (4180)Python (4161)效能 (3165)運維 (2774)最佳化 (2419).NET (2262)Google (2136)機器學習 (1795)併發 (1613)分散式 (1559)叢集 (1240)SQL (1174)Mysql (1060)區塊鏈 (1017)Docker (977)微服務 (922)面試 (919)Apache (743)NLP (725)Redis (719)Android (668)Git (640)架構師 (632)Nginx (630)Facebook (599)JVM (595)爬蟲 (476)

熱門文章

分享創造快樂