Python程序员面试分类真题4

Python程序员面试分类真题4

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

正确答案：

题目要求用两个栈来模拟队列，假设使用栈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.iterns)==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,iterns,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

ifnamp二二〃rnain〃：

stack=MyStack()

stack,push(1)

stack.push(2)

print”队列首元素为：“+str(stack.pop())

print"队列首元素为："+str(stack,pop())

程序的运行结果为：

队列首元素为：1

队列首元素为：2

算法性能分析：

这种方法入队列操作的时间复杂度为0(1)，出队列操作的时间复杂度则依

赖于入队列与出队列执行的频率。总体来讲，出队列操作的时间复杂度为

0(1),当然会有个别操作需要耗费更多的时间(因为需要从两个栈之间传输数

据)。

［考点］如何用两个栈模拟队列操作

2.请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在队列中

所处的位置和变化，队伍可能随时有人加入和退出；当有人退出影响到用户的

位置排名时需要及时反馈到用户。

正确答案：

本题不仅要实现队列常见的入队列与出队列的功能，而且还需要实现队列中任

意一个元素都可以随时出队列，且出队列后需要更新队列用户位置的变化。实

现代码如下：

fromcollectionsimportdeque

classUser:

def—init—(self,id,name):

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

self.name=name

self.seq=0

defgetName(self):

returnself,name

defsetName(self,name):

self,name=name

defgetSeq(self):

returnself,seq

defsetSeq(self,seq):

self,seq二seq

dpfgot.Id(sal「)：

returnself,id

defequals(self,argO):

o=argO

returnself.id=o.getldO

deftoString(self):

return〃id:〃+str(self.id)+〃name:"+sclf.namc+〃scq:〃+str(self,seq)

classMyQueue:

def_init_(self):

self,q=deque。

defenQueue(self,u):#进入队列尾部

u.setSeq(lcn(self.q)+l)

self.q.append(u)

#队头出队列

defdeQueue(self):

self.q.popleft()

self.updateSeqO

#队列中的人随机离开

defdeQueuemove(self,u):

self.q.remove(u)

seif.updateSeq()

#出队列后更新队列中每个人的序列

defupdateSeq(self):

i=l

foruinself,q:

u.setSeq(i)

i+=l

#打印队列的信息

defprintList(self):

foruinself,q:

printu.toStringO

ifname_二二“main〃：

ul=User(1,"userl")

u2=User(2,〃user2〃)

u3=User(3,〃user3〃)

u4=User(4,〃user4〃)

qiiPiiP=MyQiiPUP()

queue.enQueue(ul)

queue.enQueue(u2)

queue.enQueue(u3)

queue.enQueue(u4)

queue.deQueue()#队首元素ul出队列

queue.dcQucuemove(u3)#队列中间的元素u3出队列

queue.printList()

程序的运行结果为：

id:2name:user2seq:1

id:4name:user4seq:2

［考点］如何设计一个排序系统

3.LRU是LeastRecentlyUsed的缩写，它的意思是“最近最少使用”，LRU

缓存就是使用这种原理实现，简单的说就是缓存一定量的数据，当超过设定的

阈值时就把一些过期的数据删除掉。常用于页面置换算法，是虚拟页式存储管

理中常用的算法。如何实现LRU缓存方案？

正确答案：

我们可以使用两个数据结构实现一个LRU缓存。

(1)使用双向链表实现的队列，队列的最大容量为缓存的大小。在使用过

程中，把最近使用的页面移动到队列头，最近没有使用的页面将被放在队列尾

的位置。

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

值。

当引用一个页面时，如果所需的页面在内存中，只需要把这个页对应的结

点移动到队列的前面。如果所需的页面不在内存中，此时需要把这个页面加载

到内存中。简单地说，就是将一个新结点添加到队列的前面，并在哈希表中更

新相应的结点地址。如果队列是满的，那么就从队列尾部移除一个结点，并将

新结点添加到队列的前面。实现代码如下：

fromcollectionsimportdeque

classLRU:

def_init_(self,cacheSize):

self.cacheSize=cacheSize

self,queue=deque()

self.hashSet=set()

#判断缓存队列是否已满

defisQueueFull(self):

rplurn1pn(solf.qiiPiin)==SA1f.cachoSiZP

#把页号为pageNum的页缓存到队列中，同时也添加到Hash表中

defenqueue(self,pageNum):

#如果队列满了，需要删除队尾的缓存的页

ifself.isQueueFull():

self,hashSet.remove(self.queue[-l])

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

ifname_="main〃：

#假设缓存大小为3

lru=LRU(3)

#访问page

Iru.accessPage(1)

lru.accessPage(2)

Iru.accessPage(5)

lru.accessPage(1)

lru.accessPage(6)

lru.accessPage(7)

并通过上面的访问序列后，缓存的信息为

1ru.prinlQuoiip()

程序的运行结果为：

761

［考点］如何实现LRU缓存方案

4.给定一趟旅途旅程中所有的车票信息，根据这个车票信息找出这趟旅程的

路线。例如：给定下面的车票：（“西安”到“成都”）,（“北京”到“上

海”），（“大连”到“西安”）,（“上海”到“大连”）。那么可以得到旅程路

线为：北京上海，上海-＞大连，大连-,西安，西安成都。假定给定的

车票不会有环，也就是说有一个城市只作为终点而不会作为起点。

正确答案：

对于这种题目，一般而言可以使用拓扑排序进行解答。根据车票信息构建一个

图，然后找出这张图的拓扑排序序列，这个序列就是旅程的路线。但这种方法

的效率不高，它的时间复杂度为0（N）。这里重点介绍另外一种更加简单的方

法：hash法（python中可以使用字典实现）。主要的思路为根据车票信息构建一

个字典，然后从这个字典中找到整个旅程的起点，接着就可以从起点出发依次

找到下一站，进而知道终点,具体的实现思路为：

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

Tickets=｛（〃西安〃到〃成都〃），（〃北京〃到〃上海〃），（〃大连〃到〃西安〃），（〃上

海〃到〃大连〃）｝

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

ReverseTickets=｛（〃成都〃到〃西安〃），（〃上海〃到〃北京〃），（〃西安〃到〃大连

〃)，(〃大连〃到〃上海“)}

(3)遍历Tickets,对于遍历到的key值，判断这个值是否在

ReverseTickets中的key中存在,如果不存在,那么说明遍历到的Tickets中

的key值就是旅途的起点。例如：“北京”在ReverseTickets的key中不存

在，因此“北京”就是旅途的起点。

实现代码如下：

defprintResult(inputs):

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

reverselnput=dict()

fork,vininputs,items():

reverseinput[v]=k

start=None

#找到起点

fork,vininputs,items():

ifknotinreverseinput:

start二k

hroak

ifstart二二None:

print〃输入不合理”

return

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

to=inputs[start]

printstart+/z-＞，，+to,

stan=to

to=inputs[to]

whileto!=None:

print〃,〃+Start+〃-＞〃+to,

start二to

to=inputs[to]

if_name_=〃_main_〃：

inputs二diet()

inputs[〃西安〃]二〃成都〃

inputs[〃北京〃]二〃上海〃

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

inputs[〃上海〃]二〃大连〃

printResult(inputs)

程序的运行结果为：

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

算法性能分析：

这种方法的时间复杂度为0(N),空间复杂度也为0(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。

正确答案：

最简单的方法就是使用四重遍历，对所有可能的数对，判断是否满足题目要

求，如果满足则打印出来，但是这种方法的时间复杂度为O(N"),很显然不满足

要求。下面介绍另外一种方法一一字典法，算法的主要思路为：以数对为单位

进行遍历，在遍历过程中，把数对和数对的值存储在字典中(键为数对的和，值

为数对)，当遍历到一个键值对时，如果它的和在字典中已经存在，那么就找到

了满足条件的键值对。下面使用字典为例给出实现代码：

#用来存储数对

classpair:

def—init—(self,first,second):

seif.first=None

self.second=None

self.first=first

self,second=second

deffindPairs(arr):