Python程序员面试分类真题4

Python程序员面试分类真题4(总分：100.00，做题时间：90分钟)面试题(总题数：5，分数：100.00)1.

如何用两个栈模拟队列操作

（分数：20.00）__________________________________________________________________________________________

正确答案：(题目要求用两个栈来模拟队列，假设使用栈A与栈B模拟队列Q，A为插入栈，B为弹出栈，以实现队列Q。

再假设A和B都为空，可以认为栈A提供入队列的功能，栈B提供出队列的功能。

要入队列，入栈A即可，而出队列则需要分两种情况考虑：

(1)如果栈B不为空，则直接弹出栈B的数据。

(2)如果栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的数据。

实现代码如下：

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"栈已经为空"

returnNone

#压栈

defpush(self,item):

self.items.append(item)

classMyStack:

def__init__(self):

self.A=Stack()#用来存储栈中元素

self.B=Stack()#用来存储当前栈中最小的元素

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

程序的运行结果为：

队列首元素为：1

队列首元素为：2

算法性能分析：

这种方法入队列操作的时间复杂度为O(1)，出队列操作的时间复杂度则依赖于入队列与出队列执行的频率。总体来讲，出队列操作的时间复杂度为O(1)，当然会有个别操作需要耗费更多的时间(因为需要从两个栈之间传输数据)。)解析：[考点]如何用两个栈模拟队列操作。2.

请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化，队伍可能随时有人加入和退出；当有人退出影响到用户的位置排名时需要及时反馈到用户。

（分数：20.00）__________________________________________________________________________________________

正确答案：(本题不仅要实现队列常见的入队列与出队列的功能，而且还需要实现队列中任意一个元素都可以随时出队列，且出队列后需要更新队列用户位置的变化。实现代码如下：

fromcollectionsimportdeque

classUser:

def__init__(self,id,name):

self.id=id#唯一标识一个用户

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

程序的运行结果为：

id:2name:user2seq:1

id:4name:user4seq:2)解析：[考点]如何设计一个排序系统。3.

LRU是LeastRecentlyUsed的缩写，它的意思是“最近最少使用”，LRU缓存就是使用这种原理实现，简单的说就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉。常用于页面置换算法，是虚拟页式存储管理中常用的算法。如何实现LRU缓存方案?

（分数：20.00）__________________________________________________________________________________________

正确答案：(我们可以使用两个数据结构实现一个LRU缓存。

(1)使用双向链表实现的队列，队列的最大容量为缓存的大小。在使用过程中，把最近使用的页面移动到队列头，最近没有使用的页面将被放在队列尾的位置。

(2)使用一个哈希表，把页号作为键，把缓存在队列中的结点的地址作为值。

当引用一个页面时，如果所需的页面在内存中，只需要把这个页对应的结点移动到队列的前面。如果所需的页面不在内存中，此时需要把这个页面加载到内存中。简单地说，就是将一个新结点添加到队列的前面，并在哈希表中更新相应的结点地址。如果队列是满的，那么就从队列尾部移除一个结点，并将新结点添加到队列的前面。实现代码如下：

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)

#把新缓存的结点同时添加到hash表中

self.hashSet.add(pageNum)

"""

当访问某一个page的时候会调用这个函数，对于访问的page有两种情况：

1.如果page在缓存队列中，直接把这个结点移动到队首

2.如果page不在缓存队列中，把这个page缓存到队首。

"""

defaccessPage(self,pageNum):

#page不在缓存队列中,把它缓存到队首

ifpageNumnotinself.hashSet:

self.enqueue(pageNum)

#page已经在缓存队列中了,移动到队首

elifpageNum!=self.queue[0]:

self.queue.remove(pageNum)

self.queue.appendleft(pageNum)

defprintQueue(self):

whilelen(self.queue)＞0:

printself.queue.popleft(),

if__name__="__main__":

#假设缓存大小为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()

程序的运行结果为：

761)解析：[考点]如何实现LRU缓存方案。4.

给定一趟旅途旅程中所有的车票信息，根据这个车票信息找出这趟旅程的路线。例如：给定下面的车票：(“西安”到“成都”)，(“北京”到“上海”)，(“大连”到“西安”)，(“上海”到“大连”)。那么可以得到旅程路线为：北京-＞上海，上海-＞大连，大连-＞西安，西安-＞成都。假定给定的车票不会有环，也就是说有一个城市只作为终点而不会作为起点。

（分数：20.00）__________________________________________________________________________________________

正确答案：(对于这种题目，一般而言可以使用拓扑排序进行解答。根据车票信息构建一个图，然后找出这张图的拓扑排序序列，这个序列就是旅程的路线。但这种方法的效率不高，它的时间复杂度为O(N)。这里重点介绍另外一种更加简单的方法：hash法(python中可以使用字典实现)。主要的思路为根据车票信息构建一个字典，然后从这个字典中找到整个旅程的起点，接着就可以从起点出发依次找到下一站，进而知道终点。具体的实现思路为：

(1)根据车票的出发地与目的地构建字典。

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

(2)构建Tickets的逆向字典如下(将旅程的起始点反向)：

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

(3)遍历Tickets，对于遍历到的key值，判断这个值是否在ReverseTickets中的key中存在，如果不存在，那么说明遍历到的Tickets中的key值就是旅途的起点。例如：“北京”在ReverseTickets的key中不存在，因此“北京”就是旅途的起点。

实现代码如下：

defprintResult(inputs):

#用来存储把input的键与值调换后的信息

reverseInput=dict()

fork,vininputs.items():

reverseInput[v]=k

start=None

#找到起点

fork,vininputs.items():

ifknotinreverseInput:

start=k

break

ifstart==None:

print"输入不合理"

return

#从起点出发按照顺序遍历路径

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)

程序的运行结果为：

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

算法性能分析：

这种方法的时间复杂度为O(N)，空间复杂度也为O(N)。)解析：[考点]如何从给定的车票中找出旅程。5.

给定一个数组，找出数组中是否有两个数对(a,b)和(c,d)，使得a+b=c+d，其中，a、b、c和d是不同的元素。如果有多个答案，打印任意一个即可。例如给定数组：[3,4,7,10,20,9,8]，可以找到两个数对(3,8)和(4,7)，使得3+8=4+7。

（分数：20.00）__________________________________________________________________________________________

正确答案：(最简单的方法就是使用四重遍历，对所有可能的数对，判断是否满足题目要求，如果满足则打印出来，但是这种方法的时间复杂度为O(N4)，很显然不满足要求。下面介绍另外一种方法——字典法，算法的主要思路为：以数对为单位进行遍历，在遍历过程中，把数对和数对的值存储在字典中(键为数对的和，值为数对)，当遍历到一个键值对时，如果它的和在字典中已经存在，那么就找到了满足条件的键值对。下面使用字典为例给出实现代码：

#用来存储数对

classpair:

def__init__(self,first,second