python面试之腾讯测试开发工程师

今天面试了腾讯的测试开发工程师岗位，总体感觉一般，问的问题都还是比较基础性的东西，当然也问了很多实习期间做的项目，各占一半吧。下面基础部分的东西总结一下：

1、假定我有100M的一个文本数据，但是我的电脑内存只有10M，我怎么在有限的资源条件的情况下，找出这个文本中出现次数最多的那一行字符串？

2、什么是最大堆（大顶堆）,堆排序的时间复杂度是多少？

         堆可以看做一个完全二叉树，同时该完全二叉树满足双亲结点大于等于孩子结点（大顶堆），或者双亲结点小于等于孩子结点（小顶堆）

         堆排序：堆排序也分为两个过程：（1）将初始化序列调整成为一个大顶堆（2）用最后一个元素和堆顶元素交换，然后不断调整剩下的元素成为一个新的大顶堆。

         堆排序的时间复杂度：o(nlogn)

          其他排序算法常见时间复杂度：

        

3、二叉树：

       满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

     平衡二叉树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

     完全二叉树：完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

      

4、用Python的面向对象思想，实现一个链表的插入和删除。