Python程序員面試分類真題4

Python程序員面試分類真題4(總分：100.00，做題時間：90分鐘)面試題(總題數(shù)：5，分?jǐn)?shù)：100.00)1.

如何用兩個棧模擬隊列操作

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(題目要求用兩個棧來模擬隊列，假設(shè)使用棧A與棧B模擬隊列Q，A為插入棧，B為彈出棧，以實現(xiàn)隊列Q。

再假設(shè)A和B都為空，可以認為棧A提供入隊列的功能，棧B提供出隊列的功能。

要入隊列，入棧A即可，而出隊列則需要分兩種情況考慮：

(1)如果棧B不為空，則直接彈出棧B的數(shù)據(jù)。

(2)如果棧B為空，則依次彈出棧A的數(shù)據(jù)，放入棧B中，再彈出棧B的數(shù)據(jù)。

實現(xiàn)代碼如下：

classStack:

#模擬棧

def__init__(self):

self.items=[]

#判斷棧是否為空

defempty(self):

returnlen(self.items)==0

#返回棧的大小

defsize(self):

returnlen(self.items)

#返回棧項元素

defpeek(self):

ifnotself.empty():

returnself.items[len(self.items)-1]

else:

returnNone

#彈棧

defpop(self):

iflen(self.items)＞0:

returnself.items.pop()

else:

print"棧已經(jīng)為空"

returnNone

#壓棧

defpush(self,item):

self.items.append(item)

classMyStack:

def__init__(self):

self.A=Stack()#用來存儲棧中元素

self.B=Stack()#用來存儲當(dāng)前棧中最小的元素

defpush(self,data):

self.A.push(data)

defpop(self):

ifself,B.empty():

whilenotself.A.empty():

self.B.push(self.A.peek())

self.A.pop()

first=self.B.peek()

self.B.pop()

returnfirst

if__name__=="__main__":

stack=MyStack()

stack.push(1)

stack.push(2)

print"隊列首元素為:"+str(stack.pop())

print"隊列首元素為:"+str(stack.pop())

程序的運行結(jié)果為：

隊列首元素為：1

隊列首元素為：2

算法性能分析：

這種方法入隊列操作的時間復(fù)雜度為O(1)，出隊列操作的時間復(fù)雜度則依賴于入隊列與出隊列執(zhí)行的頻率?？傮w來講，出隊列操作的時間復(fù)雜度為O(1)，當(dāng)然會有個別操作需要耗費更多的時間(因為需要從兩個棧之間傳輸數(shù)據(jù))。)解析：[考點]如何用兩個棧模擬隊列操作。2.

請設(shè)計一個排隊系統(tǒng)，能夠讓每個進入隊伍的用戶都能看到自己在隊列中所處的位置和變化，隊伍可能隨時有人加入和退出；當(dāng)有人退出影響到用戶的位置排名時需要及時反饋到用戶。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(本題不僅要實現(xiàn)隊列常見的入隊列與出隊列的功能，而且還需要實現(xiàn)隊列中任意一個元素都可以隨時出隊列，且出隊列后需要更新隊列用戶位置的變化。實現(xiàn)代碼如下：

fromcollectionsimportdeque

classUser:

def__init__(self,id,name):

self.id=id#唯一標(biāo)識一個用戶

=name

self.seq=0

defgetName(self):

return

defsetName(self,name):

=name

defgetSeq(self):

returnself.seq

defsetSeq(self,seq):

self.seq=seq

defgetId(self):

returnself.id

defequals(self,arg0):

o=arg0

returnself.id=o.getId()

deftoString(self):

return"id:"+str(self.id)+"name:"++"seq:"+str(self.seq)

classMyQueue:

def__init__(self):

self.q=deque()

defenQueue(self,u):#進入隊列尾部

u.setSeq(len(self.q)+1)

self.q.append(u)

#隊頭出隊列

defdeQueue(self):

self.q.popleft()

self.updateSeq()

#隊列中的人隨機離開

defdeQueuemove(self,u):

self.q.remove(u)

self.updateSeq()

#出隊列后更新隊列中每個人的序列

defupdateSeq(self):

i=1

foruinself.q:

u.setSeq(i)

i+=1

#打印隊列的信息

defprintList(self):

foruinself.q:

printu.toString()

if__name__=="__main__":

u1=User(1,"user1")

u2=User(2,"user2")

u3=User(3,"user3")

u4=User(4,"user4")

queue=MyQueue()

queue.enQueue(u1)

queue.enQueue(u2)

queue.enQueue(u3)

queue.enQueue(u4)

queue.deQueue()#隊首元素u1出隊列

queue.deQueuemove(u3)#隊列中間的元素u3出隊列

queue.printList()

程序的運行結(jié)果為：

id:2name:user2seq:1

id:4name:user4seq:2)解析：[考點]如何設(shè)計一個排序系統(tǒng)。3.

LRU是LeastRecentlyUsed的縮寫，它的意思是“最近最少使用”，LRU緩存就是使用這種原理實現(xiàn)，簡單的說就是緩存一定量的數(shù)據(jù)，當(dāng)超過設(shè)定的閾值時就把一些過期的數(shù)據(jù)刪除掉。常用于頁面置換算法，是虛擬頁式存儲管理中常用的算法。如何實現(xiàn)LRU緩存方案?

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(我們可以使用兩個數(shù)據(jù)結(jié)構(gòu)實現(xiàn)一個LRU緩存。

(1)使用雙向鏈表實現(xiàn)的隊列，隊列的最大容量為緩存的大小。在使用過程中，把最近使用的頁面移動到隊列頭，最近沒有使用的頁面將被放在隊列尾的位置。

(2)使用一個哈希表，把頁號作為鍵，把緩存在隊列中的結(jié)點的地址作為值。

當(dāng)引用一個頁面時，如果所需的頁面在內(nèi)存中，只需要把這個頁對應(yīng)的結(jié)點移動到隊列的前面。如果所需的頁面不在內(nèi)存中，此時需要把這個頁面加載到內(nèi)存中。簡單地說，就是將一個新結(jié)點添加到隊列的前面，并在哈希表中更新相應(yīng)的結(jié)點地址。如果隊列是滿的，那么就從隊列尾部移除一個結(jié)點，并將新結(jié)點添加到隊列的前面。實現(xiàn)代碼如下：

fromcollectionsimportdeque

classLRU:

def__init__(self,cacheSize):

self.cacheSize=cacheSize

self.queue=deque()

self.hashSet=set()

#判斷緩存隊列是否已滿

defisQueueFull(self):

returnlen(self.queue)==self.cacheSize

#把頁號為pageNum的頁緩存到隊列中,同時也添加到Hash表中

defenqueue(self,pageNum):

#如果隊列滿了,需要刪除隊尾的緩存的頁

ifself.isQueueFull():

self.hashSet.remove(self.queue[-1])

self.queue.pop()

self.queue.appendleft(pageNum)

#把新緩存的結(jié)點同時添加到hash表中

self.hashSet.add(pageNum)

"""

當(dāng)訪問某一個page的時候會調(diào)用這個函數(shù)，對于訪問的page有兩種情況：

1.如果page在緩存隊列中，直接把這個結(jié)點移動到隊首

2.如果page不在緩存隊列中，把這個page緩存到隊首。

"""

defaccessPage(self,pageNum):

#page不在緩存隊列中,把它緩存到隊首

ifpageNumnotinself.hashSet:

self.enqueue(pageNum)

#page已經(jīng)在緩存隊列中了,移動到隊首

elifpageNum!=self.queue[0]:

self.queue.remove(pageNum)

self.queue.appendleft(pageNum)

defprintQueue(self):

whilelen(self.queue)＞0:

printself.queue.popleft(),

if__name__="__main__":

#假設(shè)緩存大小為3

1ru=LRU(3)

#訪問page

1ru.accessPage(1)

1ru.accessPage(2)

1ru.accessPage(5)

1ru.accessPage(1)

1ru.accessPage(6)

1ru.accessPage(7)

#通過上面的訪問序列后，緩存的信息為

1ru.printQueue()

程序的運行結(jié)果為：

761)解析：[考點]如何實現(xiàn)LRU緩存方案。4.

給定一趟旅途旅程中所有的車票信息，根據(jù)這個車票信息找出這趟旅程的路線。例如：給定下面的車票：(“西安”到“成都”)，(“北京”到“上?！?，(“大連”到“西安”)，(“上?！钡健按筮B”)。那么可以得到旅程路線為：北京-＞上海，上海-＞大連，大連-＞西安，西安-＞成都。假定給定的車票不會有環(huán)，也就是說有一個城市只作為終點而不會作為起點。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(對于這種題目，一般而言可以使用拓撲排序進行解答。根據(jù)車票信息構(gòu)建一個圖，然后找出這張圖的拓撲排序序列，這個序列就是旅程的路線。但這種方法的效率不高，它的時間復(fù)雜度為O(N)。這里重點介紹另外一種更加簡單的方法：hash法(python中可以使用字典實現(xiàn))。主要的思路為根據(jù)車票信息構(gòu)建一個字典，然后從這個字典中找到整個旅程的起點，接著就可以從起點出發(fā)依次找到下一站，進而知道終點。具體的實現(xiàn)思路為：

(1)根據(jù)車票的出發(fā)地與目的地構(gòu)建字典。

Tickets={("西安"到"成都"),("北京"到"上海"),("大連"到"西安"),("上海"到"大連")}

(2)構(gòu)建Tickets的逆向字典如下(將旅程的起始點反向)：

ReverseTickets={("成都"到"西安"),("上海"到"北京"),("西安"到"大連"),("大連"到"上海")}

(3)遍歷Tickets，對于遍歷到的key值，判斷這個值是否在ReverseTickets中的key中存在，如果不存在，那么說明遍歷到的Tickets中的key值就是旅途的起點。例如：“北京”在ReverseTickets的key中不存在，因此“北京”就是旅途的起點。

實現(xiàn)代碼如下：

defprintResult(inputs):

#用來存儲把input的鍵與值調(diào)換后的信息

reverseInput=dict()

fork,vininputs.items():

reverseInput[v]=k

start=None

#找到起點

fork,vininputs.items():

ifknotinreverseInput:

start=k

break

ifstart==None:

print"輸入不合理"

return

#從起點出發(fā)按照順序遍歷路徑

to=inputs[start]

printstart+"-＞"+to,

stan=to

to=inputs[to]

whileto!=None:

print","+Start+"-＞"+to,

start=to

to=inputs[to]

if__name__=="__main__":

inputs=dict()

inputs["西安"]="成都"

inputs["北京"]="上海"

inputs["大連"]="西安"

inputs["上海"]="大連"

printResult(inputs)

程序的運行結(jié)果為：

北京-＞上海,上海-＞大連,大連-＞西安,西安-＞成都

算法性能分析：

這種方法的時間復(fù)雜度為O(N)，空間復(fù)雜度也為O(N)。)解析：[考點]如何從給定的車票中找出旅程。5.

給定一個數(shù)組，找出數(shù)組中是否有兩個數(shù)對(a,b)和(c,d)，使得a+b=c+d，其中，a、b、c和d是不同的元素。如果有多個答案，打印任意一個即可。例如給定數(shù)組：[3,4,7,10,20,9,8]，可以找到兩個數(shù)對(3,8)和(4,7)，使得3+8=4+7。

（分?jǐn)?shù)：20.00）__________________________________________________________________________________________

正確答案：(最簡單的方法就是使用四重遍歷，對所有可能的數(shù)對，判斷是否滿足題目要求，如果滿足則打印出來，但是這種方法的時間復(fù)雜度為O(N4)，很顯然不滿足要求。下面介紹另外一種方法——字典法，算法的主要思路為：以數(shù)對為單位進行遍歷，在遍歷過程中，把數(shù)對和數(shù)對的值存儲在字典中(鍵為數(shù)對的和，值為數(shù)對)，當(dāng)遍歷到一個鍵值對時，如果它的和在字典中已經(jīng)存在，那么就找到了滿足條件的鍵值對。下面使用字典為例給出實現(xiàn)代碼：

#用來存儲數(shù)對

classpair:

def__init__(self,first,second