二叉树深度和大文件排序

用户头像
escray
关注
发布于: 2020 年 08 月 29 日
二叉树深度和大文件排序

极客时间《面试现场》学习笔记

05 | 考官面对面:我是如何面试程序员的?   



我估计是没有办法通过杨波老师的面试了,主要是编程能力和技术水平方面的问题,试着回答一下杨老师罗列出来的问题,大部分是从网络上找到的答案。



  1. 求二叉树深度



// LeetCode 104
// Maximum Depth of Binary Tree
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
  }
}
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}
// 时间复杂度 O(n)
// 空间复杂度 O(height)



如果在面试现场不会写这道题,那么估计回来以后看一下代码,会吐一口血。这道题在 LeetCode 中应该是 Easy 程度的。如果真的想通过算法笔试,至少要把 LeetCode 里面 easy 的题目刷一遍吧。



其实在最后一步忘记加 1,倒是有可能。



这个算是树的深度优先遍历,其实还可以广度优先遍历来算深度,但是有点舍本逐末的感觉,就不贴代码了。



求二叉树最大深度



  1. 普通电脑 100G 字符串大文件排序



其实我一开始想到的可能可以考虑桶排序,但是如何分桶不太好操作,如果单纯按首字母或者前两个字母分的话,可能有的桶比较空,而有的会溢出。



多路归并排序

图片转自 100G 数据,只有 100M 内存,怎么排序?



参考网络上的回答,首先先按照 1G 左右的大小,将大文件分成 100 个小文件。(怎么分?可能还是需要遍历一下文件的)



然后分别对 100 个文件中的字符串进行排序,并且将排序后的文件写入磁盘。



从每个排好序的文件中取最小的字符串,一共 100 个;



在内存中进行排序(快排?),将最小的那个写入最终的文件(最终文件是否还需要考虑切分?);与此同时,从选出最小字符串的那个小文件中,取出下一个字符串(第二小),进行插入排序(这个时候 99 个字符串已经有序了);重复这个步骤,知道所有的字符串都被取出。



有一个好听的名字叫做“多路归并排序”,其实是 Merge sort 的变体。



我觉的比较有技巧的地方其实是取出一个最小值之后,如果递补,以满足每次都能取出最小的那个。



这道题考点好多。



后面几道题这次不写了,光是垃圾回收一道题,就可以讲很久,我直接去极客时间看邓雨迪老师的《深入拆解 Java 虚拟机》中的相关章节(这个专栏我没买,所以只试读了有关垃圾回收的两篇)



发布于: 2020 年 08 月 29 日 阅读数: 26
用户头像

escray

关注

Let's Go 2017.11.19 加入

大龄程序员

评论

发布
暂无评论
二叉树深度和大文件排序