数据结构和算法-面试题

roseying 2020-02-23

##########################################

"""
数据结构:
1,用Python代码简单实现一个栈。实现pop/push及max方法,要求能在O(1)时间内取得最大值。

排序算法:
写个快速排序热热身,分析一下复杂度,如果不使用额外的空间,应该怎么写?快排平均复杂度多少,最坏情况如何优化;
请列举常见排序并通过代码实现任意三种。冒泡/选择/插入/快排
几种常用排序的算法复杂度是多少;
单向链表如何使用快速排序算法进行排序;


查找算法:
用Python实现一个二分查找的函数。
 请列举常见查找并通过代码实现任意三种。无序查找/二分查找/插值查找
如何遍历一个内部未知的文件夹(两种树的优先遍历方式)


算法复杂度
手写:一个长度n的无序数字元素列表,如何求中位数,如何尽快的估算中位数,你的算法复杂度是多少;
手写:已知一个长度n的无序列表,元素均是数字,要求把所有间隔为d的组合找出来,你写的解法算法复杂度多少;


list,dict和数据结构和算法
1,Python中的列表是如何实现的?Python中的列表使用了分离式技术实现的动态顺序表。
2,Python中列表的索引查询的时间复杂度是多少?O(1)
3,dict与list的查找复杂度?dict用hash实现,查找的时间复杂度是O(1),list则为O(n)。


"""

##########################################

##########################################

##########################################

##########################################

相关推荐