近日,中山大学郑永川构建了一个准备秋招的项目,该项目包含了九大模块,从算法到操作系统、网络、面向对象以及数据库、Java、分布式、工具、编码实践。

400114202_wx.jpg


目前该项目在GitHub上已经获得29012个Star,Fork 量也达到了8千多,相信对于同样要准备面试的程序员会有很大帮助


微信图片_20190114144755.jpg


下面,我们一起来看看该项目的九大模块:


算法


● 剑指 Offer 题解:目录根据原书第二版进行编排。

● Leetcode 题解:做了一个大致分类,并对每种分类题型的解题思路做了总结。

● 算法:主要参考 Robert Sedgewick 的算法书进行实现,源代码以及测试代码可在另一个仓库获取。



操作系统


● 计算机操作系统:参考 现代操作系统、Unix 环境高级编程、深入理解计算机系统。

● Linux:参考 鸟哥的 Linux 私房菜。



网络


● 计算机网络:参考 谢希仁的计算机网络、计算机网络 自顶向下方法、TCP/IP 详解。

● HTTP:参考 图解 HTTP,更多的是参考网上的文档,比如 MDN、维基百科等。

Socket:参考 Unix 网络编程。



面向对象 


● 设计模式:参考 Head First 设计模式、设计模式 可复用面向对象软件的基础,实现了 Gof 的 23 种设计模式。

● 面向对象思想:内容包括三大原则(继承、封装、多态)、类图、设计原则。



数据库


● 数据库系统原理:参考 数据库系统原理。

● SQL:参考 SQL 必知必会。

● Leetcode-Database 题解:Leetcode 上数据库题目的解题记录。

● MySQL:参考 高性能 MySQL。

● Redis:参考 Redis 设计与实现、Redis 实战。



Java


● Java 基础:参考 Effective Java、Java 编程思想,也有部分内容参考官方文档以及 StackOverflow。

● Java 虚拟机:参考 深入理解 Java 虚拟机。

● Java 并发:参考 Java 编程思想、深入理解 Java 虚拟机。

● Java 容器:包含容器源码的分析。

● Java I/O包含 NIO 的原理以及实例。



分布式


● 一致性:CAP、BASE、Paxos、Raft

● 分布式问题分析:分布式事务、分布式锁、分布式 Session、负载均衡



工具


● Git:一些 Git 的使用和概念。

● 正则表达式:参考 正则表达式必知必会



编码实践


● 重构:参考 重构 改善既有代码的设计。

● 代码可读性:参考 编写可读代码的艺术。

● 代码风格规范:Google 开源项目的代码风格规范。



剑指 Offer 题解


接下来我们以剑指 Offer 题解为例,深入了解一下该项目的部分知识点


1、数组中重复的数字


在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如,如果输入长度为 7 的数组 {2, 3, 1, 0, 2, 5},那么对应的输出是第一个重复的数字 2。


要求复杂度为 O(N) + O(1),也就是时间复杂度 O(N),空间复杂度 O(1)。因此不能使用排序的方法,也不能使用额外的标记数组。牛客网讨论区这一题的首票答案使用 nums[i] + length 来将元素标记,这么做会有加法溢出问题。


解题思路


这种数组元素在 [0, n-1] 范围内的问题,可以将值为 i 的元素放到第 i 个位置上。


以 (2, 3, 1, 0, 2, 5) 为例:


position-0 : (2,3,1,0,2,5// 2 <-> 1
             (1,3,2,0,2,5// 1 <-> 3
             (3,1,2,0,2,5// 3 <-> 0
             (0,1,2,3,2,5// already in position
position-1 : (0,1,2,3,2,5// already in position
position-2 : (0,1,2,3,2,5// already in position
position-3 : (0,1,2,3,2,5// already in position
position-4 : (0,1,2,3,2,5// nums[i] == nums[nums[i]], exit


遍历到位置 4 时,该位置上的数为 2,但是第 2 个位置上已经有一个 2 的值了,因此可以知道 2 重复。


public boolean duplicate(int[] nums, int length, int[] duplication) {
    if (nums == null || length <= 0)
        return false;
    for (int i = 0; i < length; i++) {
        while (nums[i] != i) {
            if (nums[i] == nums[nums[i]]) {
                duplication[0] = nums[i];
                return true;
            }
            swap(nums, i, nums[i]);
        }
    }
    return false;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
}



2、二维数组中的查找


题目描述


在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。


Consider the following matrix:
[
  [1,   4,  7, 11, 15
],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5return true.
Given target = 20return false.



解题思路


从右上角开始查找。因为矩阵中的一个数,它左边的数都比它小,下边的数都比它大。因此,从右上角开始查找,就可以根据 target 和当前元素的大小关系来缩小查找区间。


复杂度:O(M + N) + O(1)


public boolean Find(int target, int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
        return false;
    int rows = matrix.length, cols = matrix[0].length;
    int r = 0, c = cols - 1; // 从右上角开始
    while (r <= rows - 1 && c >= 0) {
        if (target == matrix[r][c])
            return true;
        else if (target > matrix[r][c])
            r++;
        else 
            c--;
    }
    return false;
}


项目地址:

https://github.com/CyC2018/Interview-Notebook


开源最前线(ID:OpenSourceTop) 猿妹整编

内容来源:https://github.com/CyC2018/Interview-Notebook