二叉树深度和大文件排序

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

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 虚拟机》中的相关章节（这个专栏我没买，所以只试读了有关垃圾回收的两篇）