算法岗常问的一些Python基础知识
前言
大家好，我是鬼仔，一名互联网算法工程师。在大厂业务部门做算法，除了算法模型能力需要达标之外，还需要具备一定的开发能力，因为业务团队的需求会比较多，需要快速迭代，模型训练好后往往还要亲自部署上线，良好的开发水平可以让模型快速上线调试。
在这个校招算法岗灰飞烟灭的时代，面试官不仅希望同学们能够了解各种算法原理、熟悉sota模型，还希望同学们能够具备一定的编程开发能力。想起鬼仔前两年校招面试的时候，就被问过好多次C++、python的基础知识，一开始鬼仔只复习了机器学习、深度学习的相关知识，开发什么的早就忘光了（在学校也没啥机会接触到呀），所以回答得支支吾吾，很是尴尬。后面自己整理了一波材料，恶补了开发基础知识，其实算法岗涉及到的开发知识并不会很深，面试官更多的是想考察下学生的开发功底怎么样，计算机基础如何。
前几天鬼仔整理了一些算法岗常问的一些C++基础知识 ，今天再分享下Python方面的基础面试题。除此之外，鬼仔之前也整理了一些算法岗面试知识点系列总结，感兴趣的同学记得关注鬼仔，后面会持续更新！
一、Python的变量类型
Python的变量类型可以分为两类：可变和不可变数据类型
- 不可变数据类型：当该数据类型的对应变量的值发生了改变，那么它对应的内存地址也会发生改变，就称不可变数据类型，包括：int（整型）、string（字符串）、tuple（元组）；
- 可变数据类型：当该数据类型的对应变量的值发生了改变，那么它对应的内存地址不发生改变，就称可变数据类型。包括：set（集合）、list（列表）、dict（字典）。
二、Python函数是值传递还是引用传递？
Python参数传递采用的是“传对象引用”的方式，这种方式相当于值传递和引用传递的一种综合。
- 不可变参数类型是值传递：如果函数收到的是一个不可变数据类型（比如数字、字符或者元组）的引用，就不能直接修改原始对象，相当于通过“传值'来传递对象。
- 可变参数类型是引用传递：如果函数收到的是一个可变数据类型（比如字典或者列表）的引用，就能修改对象的原始值，相当于通过“传引用”来传递对象。
三、python中可作为字典key的类型
- 一个对象能不能作为字典的key，就取决于其有没有hash方法。
- 字典的键可以是任意不可变数据类型，需要注意的是tuple元组作为键时，tuple不能以任何方式包含可变对象。
四、Python是否可重载
所谓重载，就是多个相同函数名的函数，根据传入的参数个数，参数类型而执行不同的功能。所以函数重载实质上是为了解决编程中参数可变不统一的问题。
在python中，具有重载的思想却没有重载的概念，因为python并不需要重载。python是一门动态语言，不需要声明变量类型，函数中可以接受任何类型的参数也就无法根据参数类型来支持重载，python没有必要去考虑参数的类型问题，这些都可以在函数内部判断处理，并无必要去在写一个函数。python有多种传参方式，默认参数/可变参数/可变关键字参数可以处理函数参数中参数可变的问题。
五、Python中的字典Dictionary详解
1、 Dictionary内部是如何实现的？
Dictionary字典相当于一个HashMap，是通过散列表或说哈希表实现的。字典也是一个数组，但数组的索引是键经过哈希函数处理后得到的散列值。哈希函数的目的是使键均匀地分布在数组中，并且可以在内存中以O(1)的时间复杂度进行寻址，从而实现快速查找和修改。
2、hash表怎么解决冲突？
哈希表中哈希函数的设计困难在于将数据均匀分布在哈希表中，从而尽量减少哈希碰撞和冲突。由于不同的键可能具有相同的哈希值，即可能出现冲突，高级的哈希函数能够使冲突数目最小化。
哈希函数就是一个映射，因此哈希函数的设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可。本质上看哈希函数不可能做成一个一对一的映射关系，其本质是一个多对一的映射，这也就引出了一个概念：哈希冲突或者说哈希碰撞。哈希碰撞是不可避免的，但是一个好的哈希函数的设计需要尽量避免哈希碰撞。
- Python2中使用使用开放地址法解决冲突。
- CPython使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构。由于这个实现细节，只有可哈希的对象才能作为字典的键。字典的三个基本操作（添加元素，获取元素和删除元素）的平均事件复杂度为O(1)。
3、可变数据类型为什么不能作为字典的键？
Python中所有不可变的内置类型都是可哈希的。可变数据类型（如列表，字典和集合）就是不可哈希的，因此不能作为字典的键。
4、常见的哈希碰撞解决方法
-
开放寻址法
开放寻址法中，所有的元素都存放在散列表里，当产生哈希冲突时，通过一个探测函数计算出下一个候选位置，如果下一个获选位置还是有冲突，那么不断通过探测函数往下找，直到找个一个空槽来存放待插入元素。
开放地址的意思是除了哈希函数得出的地址可用，当出现冲突的时候其他的地址也一样可用，常见的开放地址思想的方法有线性探测再散列，二次探测再散列等，这些方法都是在第一选择被占用的情况下的解决方法。 -
再哈希法
这个方法是按顺序规定多个哈希函数，每次查询的时候按顺序调用哈希函数，调用到第一个为空的时候返回不存在，调用到此键的时候返回其值。 -
链地址法
将所有关键字哈希值相同的记录都存在同一线性链表中，这样不需要占用其他的哈希地址，相同的哈希值在一条链表上，按顺序遍历就可以找到。 -
公共溢出区
其基本思想是：所有关键字和基本表中关键字为相同哈希值的记录，不管他们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。
