python技术面试题(二十)

正文共:1744 字 5 图 预计阅读时间:5 分钟

每日分享

The struggle you're in today is developing the strength you need for tomorrow.

今天拼搏的是明天你需要的力量。

小闫语录

没有无畏的奋斗,也没有无用的经历。现在所经历的都会成为将来你厚积薄发的蓄力,加油!

1.笔试题

1.1 哈希树

哈希树是专门优化查询效率的一种数据结构,这棵树查询效率极高,单论查询,要比二叉排序树快。

哈希树是通过质数分辨算法建立的,所以我们首先来看一下质数分辨算法。

质数是只能被1和它本身整除的数,所以2是最小的质数。在一篇论文中曾描述过质数分辨定理『n个不同的质数可以“分辨”的连续整数个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列』。

人们发现int类型最大能表示21亿个数,10个连续的质数能分辨的整数个数为 2*3*5*7*11*13*17*19*23*29=6464693230这个数超过了21亿,也就是说任何数经过10次以内计算肯定能找到。这就是为什么它查询快了。

看完是不是一脸蒙蔽,我还是用一个小栗子来说一下这棵树吧。

一个数除以2,余数有几种?0和1,所以哈希树的第2层有两个叉。查询就是根据余数判别走哪条路,一个数先除以2,根据余数找到分叉,用商除以3,根据余数找到分叉,再用商除以5。。。。不断的除下去,直到根据余数找到对应的数,或者跟本找不到为空。这就是哈希树。

1.2链表和顺序表的区别

顺序表中元素存储位置是相邻连续的,是可以快速访问到任何元素的一种数据结构。一个顺序表在使用前必须指定好存储空间大小,一旦分配内存就不可轻易更改。优点就是查询快速,缺点是插入非尾端数据或删除非尾端数据麻烦。顺序表由两部分组成,一部分是元素集合,一部分是有关表整体情况的信息(主要包括元素存储区的容量和元素的个数)。实现的方式为一体式和分离式,顾名思义,以顺序表两部分的情况区分。python中的list就是利用分离式顺序表实现的。

顺序表的构建需要预先知道数据大小来申请连续的存储空间,而进行扩充的时候,又不得不进行数据的搬迁,使用起来不是很灵活。为了充分利用计算机的内存空间,实现灵活的内存动态管理,我们就用到了链表。链表作为一种基础的数据结构,与顺序表不同,它是通过指针来描述元素关系的一种数据结构。它保存元素的时候,内存空间可以是不连续的,每个节点保存元素和下一个元素的指针即可。优点显而易见,但是缺点也很明显,就是查找元素必须重头开始查找。

1.3用代码实现一个死锁

假如一个线程在未释放锁的情况下发生了意外终止响应,其他线程获取不到锁而一直等待,这就是造成了死锁。下面我们利用简单的几行代码来模拟一个死锁的情况:

import threading
import time

# 创建互斥锁
lock = threading.Lock()

# 根据下标去取值, 保证同一时刻只能有一个线程去取值
def get_value(index):
    # 上锁
    lock.acquire()
    print(threading.current_thread())
    my_list = [3,6,8,1]
    # 判断下标释放越界
    if index >= len(my_list):
        print("下标越界:", index)
        return
    value = my_list[index]
    print(value)
    time.sleep(0.2)
    # 释放锁
    lock.release()

if __name__ == '__main__':
    # 模拟大量线程去执行取值操作
    for i in range(30):
        sub_thread = threading.Thread(target=get_value, args=(i,))
        sub_thread.start()

死锁产生后,程序会发生停止响应,空耗资源。为了避免此种情况,我们需要在合适的地方释放锁。

优质文章推荐:

公众号使用指南

redis操作命令总结

MySQL相关操作

SQL查询语句

前端中那些让你头疼的英文单词

Flask框架重点知识总结回顾

团队开发注意事项

浅谈密码加密

Django框架中的英文单词

Django中数据库的相关操作

DRF框架中的英文单词

DRF框架

Django相关知识点回顾

python技术面试题-腾讯

原文发布于微信公众号 - 小闫笔记(Pythonnote)

原文发表时间:2019-04-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券