python_编程面试题

使用递归方法对一个数组求最大值和最小值

"""
用递归算法求解一个数组的最大值和最小值
思路：
    1、首先假设这个列表只有1个元素或两个元素
    2、再考虑超过两个元素的情况，将该列表从中间位置一分为二
    3、然后递归调用该函数
"""
def myMaxMin(L,start,end):
    '''递归来得到数组的最大值和最小值'''
    if end - start <= 1:#基准点的情况
        return(max(L[start],L[end]),min(L[start],L[end]))
    else:
        max1, min1 = myMaxMin(L,start,(start+end)//2)#求前半部分的
        max2, min2 = myMaxMin(L,(start+end)//2+1,end)#求后半部分的
        return max(max1,max2),min(min1,min2)

def maxMin(L): 
    assert(type(L) == type([]) and len(L) > 0)
    maxV, minV = myMaxMin(L,0,len(L)-1)
    print(maxV,minV)
    return maxV, minV
    
L = [1,3,5,6,7,8,5,7,8,-9]
assert(maxMin(L) == (8,-9))

使用递归的方法求出10个球的颜色可能性打印出来（颜色只有黑、白两种）

'''
有10个球，每个球有两种颜色选择，黑与白，使用递归的方法把这10个球的颜色可能性打印出来
    1、将这10个球放入到一个列表中，全部用0表示,0表示白，1表示黑
    2、找基准点（程序结束的条件）start = end,打印结果
'''
count = 0
def perm(L,start,end):
    if start == end:#基准点，表示已经给每个球都赋值了一个颜色
        print(L)
        global count 
        count += 1
    else:
        perm(L,start+1,end)
        L[start] = (L[start]+1)%2#实现1与0的互换
        perm(L,start+1,end)
    
L=[0,0,0,0,0,0,0,0,0,0]
res = perm(L,0,len(L))
print(count)#1024,2**10

使用两个栈实现一个队列

'''
使用两个栈实现一个队列
队列：a,b,c -->c,b,a
'''
class QueueWithStacks:
    
    def __init__(self):
        self.s1 = []
        self.s2 = []
    
    def push(self,e):
        self.s1.append(e)
    
    def pop(self):
        if len(self.s2) == 0:
            while len(self.s1) > 0:
                t = self.s1.pop()
                self.s2.append(t)
        assert len(self.s2) > 0,'队列已经为空'#此时说明队列没有元素
        return self.s2.pop()
        
q = QueueWithStacks()
q.push('a')
q.push('b')
q.push('c')
print(q.pop())
print(q.pop())
print(q.pop())
print(q.pop())#AssertionError: 队列已经为空

实现单例模式

class Singleton:

    __instance = None

    @classmethod
    def get_instance(cls):
        if cls.__instance:
            return cls.__instance
        else:
            cls.__instance = Singleton()
            return cls.__instance


obj1 = Singleton.get_instance()
print(obj1)  # <__main__.Singleton object at 0x7eff2ce22b70>
obj2 = Singleton.get_instance()
print(obj2)  # <__main__.Singleton object at 0x7eff2ce22b70>

class Singleton(object):
    def __new__(cls, *args, **kwargs):
        if not hasattr(cls,'_instance'):
            cls._instance = super(Singleton,cls).__new__(cls)
        return cls._instance

s1 = Singleton()
s2 = Singleton()
print(s1 == s2) # True

闭包

def foo():
    return [lambda x: i+x for i in range(4)]

print([x(3) for x in foo()])

# 将上面的程序改写，以便更好的理解
def foo():
    function_list = []
    for i in range(4):
        function_list += [lambda x: i+x]
    return function_list  # 返回一个存有四个函数的列表

# x其实就是表示x=lambda x: i+x，所以x(3)就表示lambda 3: i+3，只不过此处用到了闭包的概念：i是foo函数的局部变量，x是foo的内嵌函数
# 内嵌函数引用外部函数的变量i，当foo函数执行完毕返回一个函数列表时，i的值已经是3了，所以当x函数中的i就是3，所以结果就是[3+3,3+3,3+3,3+3]
print([x(3) for x in foo()])

遍历一个目录,找出该目录下的所有文件

import os
file_list = []
def traversal_directory(dir):
    for child in os.listdir(dir):
        parent_child = os.path.join(dir, child)
        if os.path.isdir(parent_child):
            traversal_directory(parent_child)
        else:
            file_list.append(parent_child)
    return file_list

if __name__ == "__main__":
    for file in traversal_directory("slideshow"):
        print(file)

is与==的区别

"""
==符号判断的是字面值
is判断的是对象的地址
==符号为True则用is判断也必定为True
is判断为True时用==符号判断未必是True
"""
class A:
    @staticmethod
    def __eq__(var):
        return True
if __name__ == "__main__":
    print(A() == 1) # True
    print(A() is 1) # False
    print("A()的id",id(A()))
    print("1的id",id(1))

python与C语言在运行效率上哪个更快，并编写代码验证

求第45个斐波那契数

import time

def fun(n):
    if n <= 2:
        return 1
    return fun(n-1) + fun(n-2)

start = time.time()
res = fun(45)
end = time.time()
tm = end - start
print(tm) # 287.7714354991913，大约5分钟
print(res)

#include <stdio.h>
#include <time.h>
#include <unistd.h> //导入sleep函数
long fib(int n){
    if(n <= 2){
        return 1;
    }else{
        return fib(n-1) + fib(n-2);
    }
}
int main(){
    unsigned long start = time(0);
    long res = fib(45);
    unsigned long end = time(0);
    double time = end - start;
    printf("time:%f\n",time); //大约5秒钟
    printf("res:%ld\n", res);
    return 0;
}

根据给定的排序规则，对现有的数据进行排序

比如：给定order=['a', 'd', 'r', 'c'],对data=[{'id': 'd'},{'id': 'c'},{'id': 'r'},{'id': 'a'}]

# 方法一，直观但是时间复杂独比较大
order = ['a', 'd', 'r', 'c']
data = [{'id': 'd', 'name': 'xdl'}, {'id': 'c', 'name': 'gj'}, {'id': 'r', 'name': 'jack'}, {'id': 'a', 'name': 'lucy'}]
order_data = []
for o in order:
    for d in data:
        o == d['id'] and order_data.append(d)
print(order_data)

# 方法二，耗时比较短
order_data2 = []
# 思路：通过下标直接获取data中的数据然后放到新的列表中
# 1、把取出data中id的值作为key，这个字典在列表中的位置作为value，存放到新的列表data_index中
data_index = {d['id']: i for i, d in enumerate(data)}
# 2、遍历order,取出data_index对应的value； value作为下标逐个取出data中的字典放入到最终的列表中
for o in order:
    order_data2.append(data[data_index[o]])
print(order_data2)