Python Web后端面试常考数据结构与算法(珍藏版)

点击上方“萝卜大杂烩”，选择“星标”公众号

超级无敌干货，第一时间送达！！！













本文将对Python web后端面试时常考数据结构与算法进行总结，适合即将找工作或面试的你。Python web后端常考数据结构包括:


常见的数据结构链表、队列、栈、二叉树、堆


使用内置的结构实现高级数据结构，比如内置的list/deque实现栈


LeetCode或者剑指Offer上的常考题，本文将给出示例。






链表
链表有单链表、双链表、循环双端链表


如何使用Python来表示链表结构


实现链表常见操作，比如插入节点，反转链表，合并多个链表等


LeetCode练习常见链表题目，如翻转链表，如下所示：




合并两个有序链表





队列
队列（queue）是先进先出结构


如何使用Python实现队列？


实现队列的append和pop操作，如何做到先进先出


使用collections.deque实现队列






栈
栈（stack）是先进后出结构


如何使用Python实现栈？


实现栈的push和pop操作，如何做到先进后出


使用collections.deque实现队列






字典与集合
Python dict/set底层都是哈希表


哈希表的实现原理，底层其实就是一个数组


根据哈希函数快速定位一个元素，平均查找O(1)


不断加入元素会引起哈希表重新开辟空间，拷贝之前的元素到新数组




哈希表如何解决冲突


链接法：元素key冲突之后使用一个链表填充相同key的元素


开放寻址法：冲突之后根据一种方式(二次探查)寻找下一个可用的槽


cpython使用的二次探查




二叉树
先序、中序、后序


先序 根左右


中序 左根右


后序 左右根








堆
堆其实是完全二叉树，有最大堆和最小堆


最大堆：对于每个非叶子节点V，V的值都比它的两个孩子大


最小堆：对于每个非叶子节点V，V的值都比它的两个孩子小


最大堆支持每次pop操作获取最大的元素，最小堆获取最小元素


常见问题：用堆完成topK问题，从海量数字中寻找最大的K个








Python常考算法
排序+查找，重中之重


常考排序算法：冒泡排序、快速排序、归并排序、堆排序


线性查找，二分查找


能独立实现代码（手写），能够分析时间空间复杂度




常见排序算法的时空复杂度




排序算法的稳定性


相同大小的元素在排序之后依然保持相对位置不变，就是稳定的


r[i]=r[j]且r[i]在r[j]之前，排序之后r[i]依然在r[j]之前


稳定性对于排序一个复杂结构，并且需要保持原有排序才有意义



快速排序
快速排序经常问分治法(divide and conquer)，快排三步走:


Partition：选择基准分割数组为两个子数组，小于基准和大于基准的


对两个子数组分别快排


合并结果










合并两个有序数组


要求m+n复杂度内






归并排序






堆排序




二分查找




作者：dreamkong
链接：https://www.jianshu.com/p/3df18cf1024a
来源：简书





人生苦短，我用python
【神秘礼包获取方式】




点击下方公众号回复：1024







推荐阅读  点击标题可跳转




Tkinter绘制股票K线图






原文始发于微信公众号（萝卜大杂烩）：Python Web后端面试常考数据结构与算法(珍藏版)