【Python】有趣的面試題

面試里值得思考的問題……

1、Fibonacci序列

#我最開始的答案：def fibs(n): assert isinstance(n, int) and n>=0 if n==1 or n==2: return 1 else: return fibs(n-1)+fibs(n-2)#面試官：遞歸可以，但是會有重複計算，可以改進嗎？#我：重複，好像是一顆不全滿的二叉樹？試試遞歸→循環？（記得二分搜索是可以拆的）def fibs(n): assert isinstance(n, int) and n>=0 if n==1 or n==2: return 1 first=1 second=1 n=n-2 while (n>0): temp=second second=first+second first=temp n-=1 return second#面試官：其實可以用yiled……充分發揮Python這門語言的優勢#我：哦………%生成器#嘗試寫一下def fibs(): first=1 second=1 yield first yield second while True: yield first+second temp=second second=first+second first=tempdef show_fibs(n): assert isinstance(n, int) and n>=0 it=fibs()#it是生成器對象 for i in range(n): print(next(it))show_fibs(5) #寫完我在想，是不是所有的遞歸都可以拆成循環，以及是不是所有的循環都可以拆成生成器#【複習生成器……】

2、單鏈表的相鄰元素兩兩交換

#當時沒有答出來，下來花了半個小時也沒有寫對……#昨天經 @unoyx 提醒，可以用只交換data的方法達成目的，但這種實現寫法在其他語言里可能有問題（我不懂）#隨後終於把兩種都寫了出來，@shenJin總結得很對：只要指針不亂指！（所有錯誤的根源……）class Node(object): def __init__(self,data,next=None): self._data=data self._next=nextclass SingleLinkedList(): def __init__(self): self._head=None def exchange1(self): #交換指針 if (self._head!=None and self._head._next!=None):#至少有2個元素，否則不需要做任何事 #head指針比較特殊，需要單獨考慮 first=self._head self._head=self._head._next #接下來就是循環，每一輪會改變兩個指針的指向 probe=first#初始化指針位置 while True: third = probe._next._next # 提前保存probe._next._next probe._next._next=probe#第一次改變指針指向 if third==None or third._next==None:#當前節點為1往後數到3或4為空，不需要交換 probe._next=third return else:#否則當前節點1的next指嚮往後數節點3的next，也就是節點4 probe._next=third._next probe=third def exchange2(self): #只交換data probe=self._head while(probe!=None and probe._next!=None): #當probe和probe._next所指向的元素不為None時，交換這兩個元素 temp_pointer=probe##提前保存probe的位置 temp=probe._data probe._data=probe._next._data probe._next._data=temp #之後指針前移兩格 probe=temp_pointer._next._next

3、函數裝飾器(被問過兩三次了……）

問：如果一個函數以同樣的參數被反覆調用……考慮將函數的返回值保存起來，以後直接取用會提高效率，請用裝飾器實現……

#感謝 @Manjusaka 的提問，印象深刻……a_lst=[]#想寫成字典但是找不到唯一的keydef buff(func): def wrapper(*args,**kwgs): global a_lst for item in a_lst: if args==item[0] and kwgs==item[1]: return item[2] else: result=func(*args,**kwgs) a_lst.append([args,kwgs,result]) return result return wrapper def func(*args,**kwgs): pass @ bufffunc(real_args,real_kwgs)

4、手寫多線程，以及：子線程如何向主線程返回數據？

#摘抄以前的筆記，以下#（1）直接實例化t一個threading.Thead對象t=threading.Thead(target=func,ars=())t.start()#（2）從threading.Thead派生一個新的類並實現它的run()方法，class MyThread(threading.Thead): def run(self): passt=MyThread()t.start()

問：子線程如何向主線程返回數據？

（1）定義全局變數，只要在一個進程內都可以共享

（2）線程隊列queue.Queue

重點看queue.Queue對象具有這樣一些方法：

1. q.get()
2. q.put(a_para)
3. q.size()
4. q.empty()
5. q.full()
6. q.get_nowait()等價於q.get(Fasle)
7. q.put_nowait()等價於q.put(False)
8. q.task_done()#完成一項任務後，改變q
9. q.join()#阻塞……知道q判斷等所有任務都完成也就是發出q.task_done以後。因此，如果用了q.join()，那麼每次q.get()以後都要加上q.task_done()，否則一直阻塞。

線程隊列與【生產者消費者模型】：

？（1）解決大並發（2）通過中間的阻塞隊列解決生產者與消費者的強耦合問題

# coding=utf-8"""module/program document"""from queue import Queuefrom threading import Threadclass producer(Thread): def __init__(self, q): super().__init__() self.q = q def run(self): print(producer begin to run……) self.count = 5 while self.count > 0: if self.count == 1: self.count -= 1 self.q.put(2) else: self.count -= 1 self.q.put(1) print(producer finish)class consumer(Thread): def __init__(self, q): super().__init__() self.q = q def run(self): print(consumer begin to run……) while True: print(while true) data = self.q.get() self.q.task_done() if data == 2:#遇2終止，遇1消費 print("stop because data=", data) print(q.task_done) break else: print("data is good,data=", data) #self.q.task_done()#不能省略，因為q.join()需要直到所有任務都task_done才取消阻塞，所以每次get後需要調用task_done， print(consumer finish)def main(): qq = Queue() p = producer(qq) c = consumer(qq) p.setDaemon(True) c.setDaemon(True) p.start() c.start() print(stage 1) qq.join()#Blocks until all items in the Queue have been gotten and processed,也就是等到Queue都處理完了，主線程才往下 print(stage 2) print("queue is complete")if __name__ == __main__: main()

推薦閱讀：