小齐本齐

小齐本齐 查看完整档案

海外编辑武汉大学  |  金融工程 编辑亚马逊  |  Full Stack 编辑 github.com/huiqit/SheIsSDEatNYC 编辑
编辑

公众号/B站:码农田小齐
在这里分享我的个人经历和技术文章,希望能给你带来力量和启发。

回复【666】领齐姐福利包。
回复【进群】有 4 类交流群,总有一款适合你:

  1. 国内读者交流群
  2. 海外读者交流群
  3. 自习打卡群,了解自习打卡规则请回复【自习】
  4. 好文分享群

愿我们一起成为更好的人,期待与你相遇️️

个人动态

小齐本齐 发布了文章 · 56 分钟前

排序算法入门之「选择排序」

选择排序

选择排序也是利用了“挡板法”这个经典思想。

挡板左边是已排序区间,右边是未排序区间,那么每次的“选择”是去找右边未排序区间的最小值,找到之后和挡板后面的第一个值换一下,然后再把挡板往右移动一位,保证排好序的这些元素在挡板的左边。

比如之前的例子:{5, 2, 0, 1}

我们用一个挡板来分隔数组是否排好序,
用指针 j 来寻找未排序区间的最小值;

第一轮 j 最初指向 5,然后遍历整个未排序区间,最终指向 0,那么 0 就和挡板后的第一个元素换一下,也就是和 5 交换一下位置,挡板向右移动一位,结束第一轮。

第二轮,j 从挡板后的2开始遍历,最终指向1,然后1和挡板后的第一个元素 2 换一下,挡板向右移动一位,结束第二轮。

第三轮,j 从2开始遍历,最终指向2,然后和2自己换一下,挡板向右移动一位,结束第三轮。

还剩一个元素,不用遍历了,就结束了。

选择排序与之前的插入排序对比来看,要注意两点:

  1. 挡板必须从 0 开始,而不能从 1 开始。虽然在这两种算法中,挡板的物理意义都是分隔已排序和未排序区间,但是它们的已排序区间里放的元素的意义不同:
  • 选择排序是只能把当前的最小值放进来,而不能放其他的;
  • 插入排序的第一个元素可以为任意值。

所以选择排序的挡板左边最开始不能有任何元素。

  1. 在外层循环时,
  • 选择排序的最后一轮可以省略,因为只剩下最大的那个元素了;
  • 插入排序的最后一轮不可省略,因为它的位置还没定呢。
class Solution {
 public void selectionSort(int[] input) {
  if(input == null || input.length <= 1) {
   return;
  } 
  for(int i = 0; i < input.length - 1; i++) {
   int minValueIndex = i;
   for(int j = i + 1; j < input.length; j++) {
    if(input[j] < input[minValueIndex]) {
     minValueIndex = j;
    }
   }
   swap(input, minValueIndex, i);
  }
 }
 private void swap(int[] input, int x, int y) {
  int tmp = input[x];
  input[x] = input[y];
  input[y] = tmp;
 }
}

时间复杂度

最内层的 if 语句每执行一次是 O(1) ,那么要执行多少次呢?

  • 当 i = 0 时,是 n-1 次;
  • 当 i = 1 时,是 n-2 次;
  • ...
  • 最后是 1 次;

所以加起来,总共是:
(n-1) + (n-2) + … + 1 = n*(n-1) / 2 = O(n^2)

是这样算出来的,而不是一拍脑袋说两层循环就是 O(n^2).

空间复杂度

这个很简单,最多的情况是 call swap() 的时候,然后 call stack 上每一层就用了几个有限的变量,所以是 O(1)。

那自然也是原地排序算法了。

稳定性

这个答案是否定的,选择排序并没有稳定性。

因为交换的过程破坏了原有的相对顺序,比如: {5, 5, 2, 1, 0} 这个例子,第一次交换是 0 和 第一个 5 交换,于是第一个 5 跑到了数组的最后一位,且再也无翻身之地,所以第一个 5 第二个 5 的相对顺序就已经打乱了。

这个问题在石头哥的那篇谷歌面经文章里有被考到哦,如果还没有看过这篇面经文章的,在公众号里回复「谷歌」二字,就可以看到了。

优化

选择排序的其中一步是选出每一轮的最小值,那么这一步如果使用 heapify() 来优化,就可以从 O(n) 优化到 O(logn),这其实就变成了 heapSort.

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 0 收藏 0 评论 0

小齐本齐 发布了文章 · 10月20日

排序算法入门之「插入排序」

插入排序

借用《算法导论》里的例子,就是我们打牌的时候,每新拿一张牌都会把它按顺序插入,这,其实就是插入排序。

齐姐声明:虽然我们用打牌的例子,但是可不能学胡适先生啊。

对于数组来说怎么做呢?

有一个重要的思想,叫做挡板法,就是用挡板把数组分成两个区间:

  • 挡板左边:已排序
  • 挡板右边:未排序

那么排序分三步走:

  1. 最初挡板是在数组的最左边,index = 0 的位置,也就是保证了已排序区间里一个数都没有,或者也可以包含一个数啦;
  2. 核心思想就是:
    依次遍历未排序区间里的元素,在已排序区间里找到正确的位置插入;
  3. 重复这个过程,直到未排序区间为空。

举个例子:{5, 2, 1, 0}

第一步,挡板最初在这里:

第二步,
把 2 插入已排序区间的正确位置,变成:

重复这个步骤,把 1 排好:

最后把 0 排好:

那代码也很简单:

public void insertionSort(int[] input) {
    if (input.length <= 1) {
        return;
    }
    for(int i = 1; i < input.length; i++) {
        int tmp = input[i];
        int j = i - 1;
        while(j >= 0 && input[j] > tmp) {
            input[j+1] = input[j];
            j --;
        }
        input[j+1] = tmp;
    }
}

我们来分析一下这个算法的时空复杂度。

时间复杂度

关于时间复杂度有两个要点

  • 是描述随着自变量的增长,所需时间的增长率;
  • 是渐近线复杂度,就是说

    • 不看系数
    • 只看最高阶项

那么我们关心的 worst case 的情况就是:
如果数组是近乎倒序的,每次插入都要在数组的第一个位置插入,那么已排序区间内的所有的元素都要往后移动一位,这一步平均是 O(n),那么重复 n 次就是 O(n^2).

空间复杂度

重点是一个峰值的概念,并不是累计使用的空间。
这里是 O(1) 没什么好说的。

引入一个概念:sorted in place,也就是原地排序

原地排序就是指空间复杂度为 O(1) 的算法,因为没有占用额外的空间,就是原地打转嘛。

其实 in-place 的思想并不是只在排序算法里有,只不过排序算法是一个最广为人知的例子罢了。本质上就是一个节省使用空间的思想。

但是对于排序算法,只分析它的时空复杂度是不够的,还有另外一个重要指标:

稳定性

这个是排序算法的一个重要指标,意思是元素之间的相对顺序是否保持了不变。

比如说:{5, 2, 2, 1, 0}

这个数组排序完成后这里面的两个 2 的相对顺序没有变,那么这个排序就是一个稳定排序。

那有同学可能就想,顺序变了又有什么关系呢?

其实,在实际工作中我们排序的对象不会只是一个数字,而是一个个的对象 (object),那么先按照对象的一个性质来排序,再按照另一个性质来排序,那就不希望原来的那个顺序被改变了。好像有点抽象,我们举个例子。

比如在股票交易系统里,有买卖双方的报价,那是如何匹配的呢?

  • 先按照价格排序;
  • 在相等的价格中,按照出价的时间顺序来排序。

那么一搬来说系统会维持一个按时间排序的价格序列,那么此时只需要用一个具有稳定性的排序算法,再按照价格大小来排序就好了。因为稳定性的排序算法可以保持大小相同的两个对象仍维持着原来的时间顺序。

那么插入排序是否是稳定性的排序呢?答案是肯定的。因为在我们插入新元素的时候是从后往前检查,并不是像打牌的时候随便插一个位置不能保证相对顺序。

大家可以看下下面的动画 就非常清楚了~

优化

插入排序其实是有很大的优化空间的,你可以搜一下“希尔排序”。

在刚开始学习的时候,深度固然重要,但因为广度不够,如果学的太深可能会很痛苦,一个知识点就无穷无尽的延展,这并不是一个高效的学习方式。

所以如果时间有限,就要做好深度和广度的平衡:

  • 在常用常考的知识点上多花时间精力,追求深度;
  • 在一些拓展性的知识点上点到为止,先知道有这么回事就行。

保持 open minded 的心态,后期就会有质的提高。

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 2 收藏 1 评论 0

小齐本齐 发布了文章 · 10月19日

面试必备的「反转链表」

反转链表这题真的是面试非常喜欢考的了,这题看起来简单,但是能用两种方法一遍 bug free 也是不容易的,面试的时候可以筛下来一大批人,无论是对 junior 还是 senior 面试都很爱考。

今天齐姐就带你梳理清楚思路,思路清楚了才能写码如有神

题目

这是从力扣中文站上截下来的,但是这个输出不太形象。

对链表的反转,并不是要把它实际翻个个,只是动一动 next 指针就好了。

什么意思呢?

我们先看对数组进行反转。

数组是一个物理上连续存储的数据结构,反转之后原来放 1 的位置就变成了放 5.

但是链表并不是,因为链表在物理上是不连续的,它的每个单元 ListNode 是通过 next 指针连接在一起的,而每个 ListNode 之间在内存里并不一定是挨着的。

所以反转链表,就不是非要把 1 的位置放 5,因为它们想在哪在哪。

那么怎么保证这个顺序呢?

  • 就是 next 指针。

沿着 next 指针的方向走下去,就是链表的顺序。这也就保证了,只要我们拿到了头节点,就掌控了整个 LinkedList.

那么题目中的例子,形象点是这个样子滴:

也就是元素自己不用动,只需要动动小指针,就是反转了。

递归解法

递归的三步骤大家还记得吗?

Base case + 拆解 + 组合

不记得的赶紧在公众号内回复「递归」二字,获取递归的入门篇详解。

那么我们来看这个题的:

base case:

当只有一个 node,或者没有 node 了呗,也就是

if(node == null || node.next == null) {
  return node;
}

其实呢,只剩一个 node 的时候严格来讲并不是 base case,而是 corner case,

因为它本可以再 break down 到 node == null 的,但因为后面有对 node.next 的 dereference 操作,所以不能省略。

拆解:

递归的拆解就是把大问题,分解成小一点点的问题,直到 base case 可以返回,进行第三步的组合。

那么这里就是

组合:

组合的意思是,假设我们能够拿到小问题的解,那么用小问题的解去构造大问题的解。

那么这个问题里如何构造呢?

这里很明显,在 2 后面接上 1 就行了,但是怎么拿到 2 呢?

别忘了,原问题里,此时还有 1 指向 2 呢~

也就是 node1.next = node2

然后把 2 指向 1:node2.next = node1

合起来就是:node1.next.next = node1

思路清楚就不绕,看着觉得绕的就是没想清楚哼~

代码

递归的代码写起来都很简洁:

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

时间复杂度

我们在「递归」这篇文章里说过,递归的时间复杂度分析方法就是把递归树画出来,每个节点的时间加起来就行了。

这个递归树是一个很简单的单项链表,每个节点上做的就是那三行代码,也就是「组合」做的事,即 O(1) 的时间,总共有 n 个节点,那么总的时间就是 O(n).

空间复杂度

那看递归树也很明显了,每一层也就用了点小变量,是 O(1),所以总的空间共是 O(n).

Iterative 解法

(谁能告诉我这个中文的专业说法。。

Iterative 的思路就是:
过一遍这个 Linked List,边过边把这个 node 的 next 指针指向前面那个 node,直到过完全部。

这样说太抽象,面试时也是,直接过例子。

那也就是把 1 的 next 指针翻过来指向 NULL;
把 2 的 next 指针翻过来指向 1;
把 3 的 next 指针翻过来指向 2;
...

所以我们还需要一个变量来记录当前 node 的前一个 node,不妨设为 prev.

同时呢,一旦我们把指针翻转过去,后面的那个 node 就丢了有木有!所以还需要有个额外的变量事先记录下后面的 node,设为 nxt,这样才不至于走丢~

Step1.

翻转箭头:把 1 的 next 指针指向 NULL;

这样子,同时我们也明确了,prev 的初始化应该是 NULL.

然后把这仨变量都移动到下一个位置:

Step2.

翻转箭头:把 2 的 next 指针指向 1,

然后三人行:

Step3.

翻转箭头:把 3 的 next 指针指向 2,

再齐步走:

Step4.

再把 4 的反过来:

再往后走:

Step5.

再把 5 的 next 反过来:

但是因为我们的 while 循环包含了

「翻转箭头」+「三人行」

两个步骤,所以还需要走完最后一个三人行,变成:

很多同学搞不清楚这个 while 循环的结束条件,其实很简单,你就走个例子画画图嘛!

那结束条件就是 curr = null 的时候,
最后返回的是 prev.

好了,看代码吧:

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while(curr != null) {
            ListNode nxt = curr.next;
            curr.next = prev; // 翻转箭头
            prev = curr; //三人行
            curr = nxt; //三人行
        }

        return prev;
    }
}

时间复杂度

这里的时间复杂度很明显了,就是过了一遍这个链表,所以是 O(n).

空间复杂度

空间是 O(1).

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 5 收藏 3 评论 0

小齐本齐 发布了文章 · 10月19日

为什么堆化 heapify() 只用 O(n) 就做到了?

heapify()

前面两篇文章介绍了什么是堆以及堆的两个基本操作,但其实呢,堆还有一个大名鼎鼎的非常重要的操作,就是 heapify() 了,它是一个很神奇的操作,

可以用 O(n) 的时间把一个乱序的数组变成一个 heap。

但是呢,heapify() 并不是一个 public API,看:

所以我们没有办法直接使用。

唯一使用 heapify() 的方式呢,就是使用
PriorityQueue(Collection<? extends E> c)

这个 constructor 的时候,人家会自动调用 heapify() 这个操作。

<span style="display:block;color:blue;">那具体是怎么做的呢?

哈哈源码已经暴露了:

从最后一个非叶子节点开始,从后往前做 siftDown().

因为叶子节点没必要操作嘛,已经到了最下面了,还能和谁 swap?

举个例子:

我们想把这个数组进行 heapify() 操作,想把它变成一个最小堆,拿到它的最小值。

那就要从 3 开始,对 3,7,5进行 siftDown().

Step 1.

尴尬 😅,3 并不用交换,因为以它为顶点的这棵小树已经满足了堆序性。

Step 2.

7 比它的两个孩子都要大,所以和较小的那个交换一下。

交换完成后;

Step 3.

最后一个要处理的就是 5 了,那这里 5 比它的两个孩子都要大,所以也和较小的那个交换一下。

换完之后结果如下,注意并没有满足堆序性,因为 4 还比 5 小呢。

所以接着和 4 换,结果如下:

这样整个 heapify() 的过程就完成了。

好了难点来了,为什么时间复杂度是 O(n) 的呢?

怎么计算这个时间复杂度呢?

其实我们在这个过程里做的操作无非就是交换交换。

那到底交换了多少次呢?

没错,交换了多少次,时间复杂度就是多少。

那我们可以看出来,其实同一层的节点最多交换的次数都是相同的。

那么这个总的交换次数 = 每层的节点数 * 每个节点最多交换的次数

这里设 k 为层数,那么这个例子里 k=3.

每层的节点数是从上到下以指数增长:

$$\ce{1, 2, 4, ..., 2^{k-1}}$$

每个节点交换的次数,

从下往上就是:

$$ 0, 1, ..., k-2, k-1 $$

那么总的交换次数 S(k) 就是两者相乘再相加:

$$S(k) = \left(2^{0} *(k-1) + 2^{1} *(k-2) + ... + 2^{k-2} *1 \right)$$

这是一个等比等差数列,标准的求和方式就是错位相减法

那么
$$2S(k) = \left(2^{1} *(k-1) + 2^{2} *(k-2) + ... + 2^{k-1} *1 \right)$$

两者相减得:

$$S(k) = \left(-2^{0} *(k-1) + 2^{1} + 2^{2} + ... + 2^{k-2} + 2^{k-1} \right)$$

化简一下:

(不好意思我实在受不了这个编辑器了。。。

所以 heapify() 时间复杂度是 O(n).

以上就是堆的三大重要操作,最后一个 heapify() 虽然不能直接操作,但是堆排序中用到了这种思路,之前的「选择排序」那篇文章里也提到了一些,感兴趣的同学可以后台回复「选择排序」获得文章~至于堆排序的具体实现和应用,以及为什么实际生产中并不爱用它,我们之后再讲。

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 1 收藏 1 评论 0

小齐本齐 发布了文章 · 10月16日

钱多活少饭好吃的公司,你愿意来吗?

今天在视频号里发了个福利,送谷歌师兄的刷题笔记!看视频领取哈。

之后也会每周在视频号里发福利的,大家点赞关注走起呀~


这里是《齐姐聊大厂》系列的第 10 篇

(前 9 篇见文末)

每周五早上 8 点,与你唠唠大厂的那些事


Linkedin 属于 FLAG 之一,也是湾区一大热门公司,以福利好著称:薪水排在前列,work life balance 好,食堂好吃,但同时节奏慢、politics 经常被诟病。

其他的呢,来看看在 Linkedin 家实习的小伙伴的分享吧~


Pros

先说好的方面,食堂确实是不错,3 个比较大的食堂都有中餐,而且每天的菜单都不一样,总体上来说中饭是不错的,而且饭后甜点也比较精致,还可以去喝杯咖啡/smoothie。比较遗憾的是晚饭 7 点钟开始,而且由于只有 1 家食堂提供晚餐的原因,晚餐的质量比较一言难尽。

work balance 是真的好,我 mentor 一般 10 点后来,中午去健身加吃饭 2 小时,下午 5 点多就走了。对于实习生的话,由于早餐只供应到 9 点半,早上一般需要 9 点到,晚饭 7 点才开始,也就是说一天在公司呆 10 个多小时你才能 3 餐都赶上,所以其实 manager 一般是比较鼓励实习生多去参加活动或者利用 campus 的设施的。

再来说工作方面,很多 team 都有自己的 office hour,甚至比较大的 team 每天都有 office hour,所以如果
对内部工具有什么问题的话,还是很容易能快速得到解答的。

Cons

再来说下不好的方面,算上 Linkedin,我一共有 6 次实习经历,Linkedin 是第一家让我感受到了 politics 氛围的公司。

具体表现就是开会特别多,自己的 design doc 一般需要取得组里 senior 的同意,所以会有无数次的修改,然后开会的效率比较低,一次会议就 1 个小时,但经常组里的 senior 会因为一个小点争论很久,导致会议推进缓慢。

同时 Linkedin 内部有一个 committee 叫 DMRC,专门负责审核你的 schema,内部的人会对你的 schema 大到 structure 上的问题,小到命名上的问题有意见,而通常你无法驳斥,因为一旦你想要争论,那么他们会要求择日详谈,这样你的 work progress 就会被 further delay,我 mentor 对此的评价就是 who will guard the guards?

另外就是,有一点 progress 恨不得让所有人都能知道,由于 Linkedin 现在招人一般都是 infra,而 Linkedin 的 infra (infrastructure) 一般都是自己造轮子,所以你的 contribution 有多大主要就看有多少别的 team 在用你造出来的轮子,所以只有有任何成绩都会 cc 一大票人广而告之。

最后,由于 Linkedin 内部结构扁平化,所以有大量的 engineer 顶着 senior title,其实就相当于别家的 SDE2,但是你想要再往上一级到 staff 那是非常的困难,至于 senior staff,那基本都是神龙见首不见尾的人,目前也就见过我组的 tech lead 被 promote 到了 senior staff,因为我们组整个的基点就源自于他的一篇论文。

据我自己的调查,从大 manager 口中得知,我们整个 data org 大概有 700 多号人,除去 director,manager 和 staff level 以上的 engineer,顶着 senior engineer 的 title 最少也有 500 人+,按照内部 wiki 查来的数据,每个 quarter 大约有 10 个 senior engineer 被提到 staff,每年大概 40 人左右,可想而知升 staff 多么的困难。

我 mentor 在微软呆了 5 年来的 Linkedin,进来 senior title,过了 5 年才被提到 staff,而我组里一个国人大哥刚被提到 senior 4 个月就跳到了 FB,拿的 E5。

Return offer

再来说说 return offer,由于组里国人很多,所以和组里的人相处的不错(我们是 2 个小组在一块组成的大组,我们小组有一个直属的印度 manager,隔壁小组由于我来的前 3 个月没有直属的 manager,一直是大 manager 代管,大 manager 也是国人)。尽管如此,最后还是没能拿到 return offer,我就说说我 manager 的评价以及我知道的一些消息吧。

首先,关于我们大组里 2 个 intern 的表现的会议是一起开的,据隔壁组的台湾人 mentor 说,我 mentor 帮我说了不少好话。

最后我 manager 的评价分两部分,第一部分是他觉得我 project 没写完,具体就是没有 deploy 到 production。但其实我写的是个 library,不是 stand alone service,所以需要找别人的 service 来 deploy,和我们组密切合作的
一个 service 上在 dark canary machine(这个 machine 上是 take real traffic,但不会 send back 任何 output)上测试已经通过了,只是当时临近圣诞节,由于 moratorium 的存在,圣诞节假期期间所有 service 都不能 deploy,所以那个 service 的 owner 不想冒着风险在圣诞假之前 deploy 进 production。

第二部分是由于他觉得我没写完我的 project,所以需要找另外的 strong proof 来 support 给 return offer 这个决定,但是他觉得我并没有非常 take initiative。

具体第一点是我 stay blocked for longer than necessary,这里主要指当时我写完了找不到一个 service 测试,和我们合作的那个组当时还没有搭建起来 dark canary,所以也不可能直接上 production 测。组里的一个 service 本来觉得可以测,但是由于是 samza app,并且它用的 lib 版本是个比较旧的,在升级的过程中出了问题,并且也是短时间内无法解决。

第二点是我没有尝试 bonus task,midterm 的时候他和我说如果我写完手头上的这个 project 就给 meet,如果能写完 bonus task 就是 exceeded,但是由于我最后时间不太够,别说写完,都没有尝试开始写。

总结

再来这次实习的总结,其实整个 internship,我觉得收获还是有的,学会了 end to end 的整个 process,也从 staff engineer 那学到了写 code 时需要关注的 dependency,和 single responsibility 等一系列的问题。

不过说实在的,我的 mentor 和 manager 真的没有给我太大的帮助,对于我帮助最大的是一个 virtual team member,严格意义上来讲是我们的客户。

这里插个好玩的事实,这个 virtual team member 其实只是给我们组义务帮忙,因为他们的 service 在用我们的 lib。不过他最开始看了我们这个 lib 的源码后,一周时间内推倒重来,重写了 50%多的 code,和我们的
tech lead 一番交流后就 push 了,感觉这个大腿算是抱对了。

需要注意的是,如果有机会重来一次这个 internship,我会在以下几点改善:

1.初期少划水,尽早开始进入状态干活,早干完比拖到最后勉强干完还是强得多的。

2.和 manager 1on1 一定不要闲聊,就聊 expectation 和 work,最后每次完了写个书面总结 emal 发给 manager,问他有没有什么要补充的,然后拿到回复,这样以后出了什么问题一切都有书面证据。

3.有解决不了的问题尽早向 manager 提出,同样记得用 email 沟通留下书面证据,如果你的 manager 态度不积极,和外面组沟通的时候 cc 你的 manager。

最后聊下我所知道的别的情况,去年秋季这一批实习据我所知绝大多数都拿到了 return。

我和我室友算是 2 个例外,我室友的话算是和他 mentor 相处的不太好,所以 manager 考虑到 team moral,
没有给 return。

别的我还知道有另一个国人本来没给 return,走了一周后打电话说是组里又有 hc 了可以给 return。

不过据我一个现在还在 Linkedin 实习的朋友说,Linkedin 在考虑停止自己造轮子,全面转移到 azure,所以未来几年 infra 的情况我不是太看好。另外,实习的最后 2 天,我去找大 manager 沟通,看能不能改变什么,因为听组里的人说,之前别的组有过的情况是 intern 没拿到自己组 offer,但是和隔壁一个组混的很熟,结果正好隔壁组有 hc,于是和隔壁组面了 2 轮直接去了隔壁组。

基本情况就是这么多了,由于这事已经过去了,讨论谁对谁错已经没有任何意义,所以就说这么多吧。


查看原文

赞 1 收藏 0 评论 4

小齐本齐 发布了文章 · 10月15日

Java 集合看这一篇就够了

大家好,这里是《齐姐聊数据结构》系列之大集合。

话不多说,直接上图:

Java 集合,也称作容器,主要是由两大接口 (Interface) 派生出来的:
Collection 和 Map

顾名思义,容器就是用来存放数据的。

那么这两大接口的不同之处在于:

  • Collection 存放单一元素;
  • Map 存放 key-value 键值对。

就是单身狗放 Collection 里面,couple 就放 Map 里。(所以你属于哪里?

学习这些集合框架,我认为有 4 个目标:

  1. 明确每个接口和类的对应关系;
  2. 对每个接口和类,熟悉常用的 API;
  3. 对不同的场景,能够选择合适的数据结构并分析优缺点;
  4. 学习源码的设计,面试要会答啊。

关于 Map,之前那篇 HashMap 的文章已经讲的非常透彻详尽了,所以本文不再赘述。如果还没看过那篇文章的小伙伴,快去公众号内回复「HashMap」看文章吧~

Collection

先来看最上层的 Collection.

Collection 里还定义了很多方法,这些方法也都会继承到各个子接口和实现类里,而这些 API 的使用也是日常工作和面试常见常考的,所以我们先来看下这些方法。

操作集合,无非就是「增删改查」四大类,也叫 CRUD:

Create, Read, Update, and Delete.

那我也把这些 API 分为这四大类:

功能方法
add()/addAll()
remove()/ removeAll()
Collection Interface 里没有
contains()/ containsAll()
其他isEmpty()/size()/toArray()

下面具体来看:

增:

boolean add(E e);

add() 方法传入的数据类型必须是 Object,所以当写入基本数据类型的时候,会做自动装箱 auto-boxing 和自动拆箱 unboxing。

还有另外一个方法 addAll(),可以把另一个集合里的元素加到此集合中。

boolean addAll(Collection<? extends E> c);

删:

boolean remove(Object o);

remove()是删除的指定元素。

那和 addAll() 对应的,
自然就有removeAll(),就是把集合 B 中的所有元素都删掉。

boolean removeAll(Collection<?> c);

改:

Collection Interface 里并没有直接改元素的操作,反正删和增就可以完成改了嘛!

查:

  • 查下集合中有没有某个特定的元素:
boolean contains(Object o);
  • 查集合 A 是否包含了集合 B:
boolean containsAll(Collection<?> c);

还有一些对集合整体的操作:

  • 判断集合是否为空:
boolean isEmpty();
  • 集合的大小:
int size();
  • 把集合转成数组:
Object[] toArray();

以上就是 Collection 中常用的 API 了。

在接口里都定义好了,子类不要也得要。

当然子类也会做一些自己的实现,这样就有了不同的数据结构。

那我们一个个来看。

List

List 最大的特点就是:有序可重复

看官网说的:

An ordered collection (also known as a sequence).

Unlike sets, lists typically allow duplicate elements.

这一下把 Set 的特点也说出来了,和 List 完全相反,Set 是 无序不重复的。

List 的实现方式有 LinkedList 和 ArrayList 两种,那面试时最常问的就是这两个数据结构如何选择。

对于这类选择问题:
一是考虑数据结构是否能完成需要的功能
如果都能完成,二是考虑哪种更高效

(万事都是如此啊。

那具体来看这两个 classes 的 API 和它们的时间复杂度:

功能方法ArrayListLinkedList
add(E e)O(1)O(1)
add(int index, E e)O(n)O(n)
remove(int index)O(n)O(n)
remove(E e)O(n)O(n)
set(int index, E e)O(1)O(n)
get(int index)O(1)O(n)

稍微解释几个:

add(E e) 是在尾巴上加元素,虽然 ArrayList 可能会有扩容的情况出现,但是均摊复杂度(amortized time complexity)还是 O(1) 的。

add(int index, E e)是在特定的位置上加元素,LinkedList 需要先找到这个位置,再加上这个元素,虽然单纯的「加」这个动作是 O(1) 的,但是要找到这个位置还是 O(n) 的。(这个有的人就认为是 O(1),和面试官解释清楚就行了,拒绝扛精。

remove(int index)是 remove 这个 index 上的元素,所以

  • ArrayList 找到这个元素的过程是 O(1),但是 remove 之后,后续元素都要往前移动一位,所以均摊复杂度是 O(n);
  • LinkedList 也是要先找到这个 index,这个过程是 O(n) 的,所以整体也是 O(n)。

remove(E e)是 remove 见到的第一个这个元素,那么

  • ArrayList 要先找到这个元素,这个过程是 O(n),然后移除后还要往前移一位,这个更是 O(n),总的还是 O(n);
  • LinkedList 也是要先找,这个过程是 O(n),然后移走,这个过程是 O(1),总的是 O(n).

那造成时间复杂度的区别的原因是什么呢?

  • 因为 ArrayList 是用数组来实现的。
  • 而数组和链表的最大区别就是数组是可以随机访问的(random access)

这个特点造成了在数组里可以通过下标用 O(1) 的时间拿到任何位置的数,而链表则做不到,只能从头开始逐个遍历。

也就是说在「改查」这两个功能上,因为数组能够随机访问,所以 ArrayList 的效率高。

那「增删」呢?

如果不考虑找到这个元素的时间,

数组因为物理上的连续性,当要增删元素时,在尾部还好,但是其他地方就会导致后续元素都要移动,所以效率较低;而链表则可以轻松的断开和下一个元素的连接,直接插入新元素或者移除旧元素。

但是呢,实际上你不能不考虑找到元素的时间啊。。。而且如果是在尾部操作,数据量大时 ArrayList 会更快的。

所以说:

  1. 改查选择 ArrayList;
  2. 增删在尾部的选择 ArrayList;
  3. 其他情况下,如果时间复杂度一样,推荐选择 ArrayList,因为 overhead 更小,或者说内存使用更有效率。

Vector

那作为 List 的最后一个知识点,我们来聊一下 Vector。这也是一个年龄暴露帖,用过的都是大佬。

那 Vector 和 ArrayList 一样,也是继承自 java.util.AbstractList<E>,底层也是用数组来实现的。

但是现在已经被弃用了,因为...它加了太多的 synchronized!

任何好处都是有代价的,线程安全的成本就是效率低,在某些系统里很容易成为瓶颈,所以现在大家不再在数据结构的层面加 synchronized,而是把这个任务转移给我们程序员==

那么面试常问题:Vector 和 ArrayList 的区别是什么,只答出来这个还还不太全面。

来看 stack overflow 上的高票回答:

一是刚才已经说过的线程安全问题;
二是扩容时扩多少的区别。

这个得看看源码:

Screen Shot 2020-07-01 at 4.50.19 PM

这是 ArrayList 的扩容实现,这个算术右移操作是把这个数的二进制往右移动一位,最左边补符号位,但是因为容量没有负数,所以还是补 0.

那右移一位的效果就是除以 2,那么定义的新容量就是原容量的 1.5 倍

不了解这个右移操作符的小伙伴,公众号内回复「二进制」快复习一下吧~

再来看 Vector 的:

因为通常 capacityIncrement 我们并不定义,所以默认情况下它是扩容两倍

答出来这两点,就肯定没问题了。

Queue & Deque

Queue 是一端进另一端出的线性数据结构;而 Deque 是两端都可以进出的。

Queue

Java 中的 这个 Queue 接口稍微有点坑,一般来说队列的语义都是先进先出(FIFO)的。

但是这里有个例外,就是 PriorityQueue,也叫 heap,并不按照进去的时间顺序出来,而是按照规定的优先级出去,并且它的操作并不是 O(1) 的,时间复杂度的计算稍微有点复杂,我们之后单独开一篇来讲。

那 Queue 的方法官网都总结好了,它有两组 API,基本功能是一样的,但是呢:

  • 一组是会抛异常的;
  • 另一组会返回一个特殊值。
功能抛异常返回值
add(e)offer(e)
remove()poll()
element()peek()

为什么会抛异常呢?

  • 比如队列空了,那 remove() 就会抛异常,但是 poll() 就返回 null;element() 就会抛异常,而 peek() 就返回 null 就好了。

那 add(e) 怎么会抛异常呢?

有些 Queue 它会有容量的限制,比如 BlockingQueue,那如果已经达到了它最大的容量且不会扩容的,就会抛异常;但如果 offer(e),就会 return false.

那怎么选择呢?:

  • 首先,要用就用同一组 API,前后要统一;
  • 其次,根据需求。如果你需要它抛异常,那就是用抛异常的;不过做算法题时基本不用,所以选那组返回特殊值的就好了。

Deque

Deque 是两端都可以进出的,那自然是有针对 First 端的操作和对 Last 端的操作,那每端都有两组,一组抛异常,一组返回特殊值:

功能抛异常返回值
addFirst(e)/ addLast(e)offerFirst(e)/ offerLast(e)
removeFirst()/ removeLast()pollFirst()/ pollLast()
getFirst()/ getLast()peekFirst()/ peekLast()

使用时同理,要用就用同一组。

Queue 和 Deque 的这些 API 都是 O(1) 的时间复杂度,准确来说是均摊时间复杂度。

实现类

它们的实现类有这三个:

所以说,

  • 如果想实现「普通队列 - 先进先出」的语义,就使用 LinkedList 或者 ArrayDeque 来实现;
  • 如果想实现「优先队列」的语义,就使用 PriorityQueue;
  • 如果想实现「栈」的语义,就使用 ArrayDeque。

我们一个个来看。

在实现普通队列时,如何选择用 LinkedList 还是 ArrayDeque 呢?

来看一下 StackOverflow 上的高票回答:

总结来说就是推荐使用 ArrayDeque,因为效率高,而 LinkedList 还会有其他的额外开销(overhead)。

那 ArrayDeque 和 LinkedList 的区别有哪些呢?

还是在刚才的同一个问题下,这是我认为总结的最好的:

  1. ArrayDeque 是一个可扩容的数组,LinkedList 是链表结构;
  2. ArrayDeque 里不可以存 null 值,但是 LinkedList 可以;
  3. ArrayDeque 在操作头尾端的增删操作时更高效,但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的;
  4. ArrayDeque 在内存使用方面更高效。

所以,只要不是必须要存 null 值,就选择 ArrayDeque 吧!

那如果是一个很资深的面试官问你,什么情况下你要选择用 LinkedList 呢?

  • 答:Java 6 以前。。。因为 ArrayDeque 在 Java 6 之后才有的。。

为了版本兼容的问题,实际工作中我们不得不做一些妥协。。

那最后一个问题,就是关于 Stack 了。

Stack

Stack 在语义上是 先进先出(LIFO) 的线性数据结构。

有很多高频面试题都是要用到栈的,比如接水问题,虽然最优解是用双指针,但是用栈是最直观的解法也是需要了解的,之后有机会再专门写吧。

那在 Java 中是怎么实现栈的呢?

虽然 Java 中有 Stack 这个类,但是呢,官方文档都说不让用了!

原因也很简单,因为 Vector 已经过被弃用了,而 Stack 是继承 Vector 的。

那么想实现 Stack 的语义,就用 ArrayDeque 吧:

Deque<Integer> stack = new ArrayDeque<>();

Set

最后一个 Set,刚才已经说过了 Set 的特定是无序不重复的。

就和数学里学的「集合」的概念一致。

Set 的常用实现类有三个:

HashSet: 采用 Hashmap 的 key 来储存元素,主要特点是无序的,基本操作都是 O(1) 的时间复杂度,很快。

LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构,特点就是既拥有了 O(1) 的时间复杂度,又能够保留插入的顺序。

TreeSet: 采用红黑树结构,特点是可以有序,可以用自然排序或者自定义比较器来排序;缺点就是查询速度没有 HashSet 快。

那每个 Set 的底层实现其实就是对应的 Map:

数值放在 map 中的 key 上,value 上放了个 PRESENT,是一个静态的 Object,相当于 place holder,每个 key 都指向这个 object。

那么具体的实现原理增删改查四种操作,以及哈希冲突hashCode()/equals() 等问题都在 HashMap 那篇文章里讲过了,这里就不赘述了,没有看过的小伙伴可以在公众号后台回复「HashMap」获取文章哦~

总结

再回到开篇的这张图,有没有清楚了一些呢?

每个数据结构下面其实都有很多内容,比如 PriorityQueue 也就是堆,齐姐之前也专门写过文章讲解它的相关操作,比如很有名的 heapify() 的过程为什么是 O(n) 的等面试常问题,感兴趣的小伙伴在公众号后台回复「堆」获取文章吧~

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 19 收藏 15 评论 1

小齐本齐 发布了文章 · 10月14日

Git 看这一篇就够了

上一篇讲 Git 的文章发出来没想到效果特别好,很多读者都要求继续深入的写。

那今天齐姐简单讲下 Git 的实现原理,知其所以然才能知其然;并且梳理了日常最常用的 12 个命令,分为三大类分享给你。

本文的结构如下:

  1. 作者和开发原由
  2. Git 的数据模型
  3. 常用命令
  4. 资源推荐

作者和开发原由

Talk is cheap. Show me the code.

这句话就出自 Linux 和 Git 的作者
Linus Torvalds

原本 Linux 内核的版本控制系统是用的 BitKeeper,然而 2005 年,BitMover 公司不再让 Linux 开发团队免费使用了。。

Linus 一听,不给用了?老子自己写!

于是,大佬十天之内完成了 Git 的第一个版本。

所以 Git 是一个免费的、开源的版本控制系统。

版本控制系统

版本控制其实每个人都用过,那些年修改过的简历:

小齐简历 2012 版
小齐简历 2013 版
小齐简历 2014 版
小齐简历 2015 版
小齐简历 2016 版
小齐简历 2017 版
小齐简历 2018 版
小齐简历 2019 版
...

还有那些年打死都不再改的毕业论文:

毕业论文最终版
毕业论文最最终版
毕业论文最最最终版
毕业论文最最最最终版
毕业论文最终不改版
毕业论文最终真不改版
毕业论文最终真真不改版
毕业论文最终打死不改版
毕业论文最终打死不改版 2
...

没错,这就是本地版本控制系统。

很明显,好处是简单,但是只能一个人在这改,无法和他人完成合作。那么以下两种主流的版本控制系统应运而生。

1. 集中化版本控制系统

Centralized Version Control Systems (CVCS)

比如:CVS, Subversion, Perforce, etc.

这种版本控制系统有一个单一的集中管理的服务器,保存所有文件的最新版本,大家可以通过连接到这台服务器上来获取或者提交文件。

这种模式相对本地版本控制系统是有所改进的,但是缺点也很明显,如果服务器宕机,那么轻则耽误工作、重则数据丢失。于是分布式版本控制系统应运而生。

2. 分布式版本控制系统

Distributed Version Control Systems (DVCS)

比如:Git, Mercurial, Bazaar, etc.

分布式的版本控制系统会把代码仓库完整地镜像下来,这样任何一个服务器发生故障,都可以用其他的仓库来修复。

更进一步,这种模式可以更方便的和不同公司的人进行同一项目的开发,因为两个远程代码仓库可以交互,这在之前的集中式系统中是无法做到的。

那么什么叫“把代码仓库完整地镜像下来”呢?

CVCS 每个版本存放的是当前版本与前一个版本的差异,因此也被称作基于差异的版本控制 (delta-based);

Git 存储的是所有文件的一个快照 (snapshot),如果有的文件没有修改,那就只保留一个 reference 指向之前存储的文件。

不是很好理解?那接着看吧~

Git 的数据模型

1. 什么是快照 (snapshot) 呢?

首先我们来学两个 Git 中的术语:

  • blob, 就是单个的文件;
  • tree, 就是一个文件夹。

快照则是被追踪的最顶层的树。

比如我的“公众号”文件夹的这么一个结构:

那么一个快照就是追踪的“公众号”这颗树。

2. 本地库的数据模型

Git 记录了每个快照的 parent,也就是当前这个文件夹的上一个版本。

那么快照的迭代更新的过程就可以表示为一个有向无环图,是不是很熟悉?我们在「拓扑」那篇文章里讲过,忘了的小伙伴快去公众号内回复「拓扑」获取拓扑的入门文章吧~

每个快照其实都对应了一次 commit,我们用代码来表示一下:

class commit {
  array<commit> parents
  String author
  String message
  Tree snapshot
}

这就是 Git 的数据模型。

blob, tree, snapshot 其实都一样,它们在 Git 中都是对象,都可以被引用或者被搜索,会基于它们的 SHA-1 hash 进行寻址。

git cat-file -t: 查看每个 SHA-1 的类型;
git cat-file -p: 查看每个对象的内容和简单的数据结构。

但是通过这个哈希值来搜索也太不方便了,毕竟这是一串 40 位的十六进制字符,就是第二部分 git log 里输出的那个编码

因此,Git 还给了一个引用 reference

比如,我们常见的 HEAD 就是一个特殊的引用。

本地库就是由 对象引用 构成的,或者叫 Repositories.

在硬盘上,Git 只存储 对象引用,所有的 Git 命令都对应提交一个快照。

那有哪些常用命令呢?

常用命令

本章分三大部分介绍日常常用命令:

  • 本地操作
  • 和远程库的交互
  • 团队协作 - 分支

本地操作

在学习常用命令之前,你首先需要知道的 Git 的「三个分区」和对应的文件的「三种状态」:

  • 工作区:就是你本地实际写代码的地方,无论你是用 vim 直接改也好,还是在 IDE 里写,都无所谓。

    • 对应的文件状态是:modified,已修改,但还没保存到数据库中。
  • 暂存区:就是临时存放的地方。

    • 对应的文件状态是:staged,Git 已经对该文件做了标记,下次提交知道要包含它。
  • 本地库:存放本地历史版本信息。

    • 对应的文件状态是:committed,文件已经安全的保存在本地数据库中。

1. $ git add

工作区改完了代码,就用 git add 提交到暂存区。

这里如果文件改动的比较多,但又不是每个都需要提交,我会设置 git ignore file,就表示这些文件不要提交,比如在 build project 的时候会自动生成的那些文件等等。

2. &dollar; git commit -m "comment"

从暂存区提交到本地库,就需要用 commit。

一般后面都会跟个 -m 加句 comment,简单说下改动的内容或者原因,我们公司大家默认也会把 Jira链接附上,这样就知道这个改动对应哪个任务。

那如果想再改,再重新 git add 即可,但是 commit 这句需要改成

$ git commit --amend

这样就还是一条 git log 信息。

3. &dollar; git log

git log 可以查看到提交过的信息,从近到远显示每次 commit 的 comment 还有作者、日期等信息,比如大概长这个样子:

commit 5abcd17dggs9s0a7a91nfsagd8ay76875afs7d6
Author: Xiaoqi<xiaoqi@163.com>
Date: xxx xxx xxx
改了 Test 文件

commit 后面的这个编号,是每次历史记录的一个索引。比如如果需要对版本进行前进或者后退的时候,就需要用到它。

这样打印的 log 太多,更简洁的打印方式是:

$ git log --oneline

就一行打印出来了。

或者:

$ git reflog

更常用一些。

4. &dollar; git reset

那我们刚刚说过,如果需要前进或退回到某个版本,就用

$ git reset --hard <编号>

这样就直接跳到了这个编号对应的那个版本。

那么这个 hard 是什么意思呢?

这里有 3 个参数:hard, soft, mixed,我们一一来说一下。

回到我们最重要的这张图上来:

我们刚刚说的前进或后退到某一版本,是对本地库进行的操作。

那有个问题:
本地库的代码跳到那个版本之后,工作区和暂存区的代码就和本地库的不同步了呀!

那这些参数就是用来控制这些是否同步的。

&dollar; git reset --hard xxx

三个区都同步,都跳到这个 xxx 的版本上。

&dollar; git reset --soft xxx

前面两个区不同步,就只有本地库跳到这个版本。

&dollar; git reset --mixed xxx

暂存区同步,工作区不动。

所以呢,用的多的就是 hard.

远程交互

和远程库的交互主要是,也就是写入和读取。

5. $ git push

小齐写完了代码,要提交到公司的代码库里,这个过程要用 git push.

当然了,这么用会被打的。。毕竟还要 cr 呢。

5. $ git clone

新来的实习生首先要 clone 整个项目到本地来,然后才能增删改查。

当然了实际工作中也没人这么用。。因为每家公司都会有自己包装的工具。不过如果是做 Github 上的开源项目,就用得上了。

6. $ git pull

小齐提交了新的代码之后,领导要审查呀,所以用 git pull 把最新的代码拉取下来瞅瞅。

实际上呢,

git pull = fetch + merge

7. $ git fetch

git fetch 这个操作是将远程库的数据下载到本地库,但是工作区中的文件没有更新。

而要谈 get merge,我们还需要先讲下分支

mergegit pull 默认的选项,合并其实还有另外一种方法:rebase,中文叫做变基

8. $ git rebase

rebase 的作用更多的是来整合分叉的历史,可以将某个分支上的所有修改都移到另一分支上,就像是变了基底。

分支与合并

首先我们来看几个关于分支的基本操作:

9. 查看分支:

$ git branch

类似于ls,能够列出当前所有分支。

git branch -v 能够显示更多信息。

10. 创建分支:

$ git branch <branchName>

11. 切换分支:

$ git checkout <branchName>

有了分支之后必然会有合并:

12. 合并分支:

$ git merge <branchName>

而合并时就可能会有冲突,什么时候会有冲突呢?:

在同一个文件的同一个位置修改时。

因为 Git 会努力的把你们改动不同的地方合并在一起,但如果实在是在同一个地方改的,那它也没办法了,只能留给程序员去手动处理了。

当然了,每个命令延伸下去还有无限多个,本文不可能涵盖全部,所以在此重磅推荐齐姐精心挑选的三大学习资源,大家可以自行享用~

学习资源

git help

其实我个人使用最多的是git help

真心方便又好用啊!

比如 git help pull:

先介绍了有哪些参数,然后 description 详细解释了它的工作原理,下面还有图解,有木有太香!!

不过这种方式更像是 cheatsheet,当你已经知道了这个命令、只是忘了它的用法的时候去查。

如果你想系统的学习,那么下面 👇 的更适合你。

Pro Git

这本书是强烈推荐了!!

Pro Git 这本书不仅讲了 Git 的基础用法、高级用法,以及最后还深入讲解了 Git 的原理,非常细致全面。

书的电子版也能在网站上直接下载。

英文版:

  • https://git-scm.com/book/en/v2

中文版:

  • https://git-scm.com/book/zh/v2

玩游戏

Practice makes perfect!

推荐一个宝藏资源:玩游戏来练 Git

项目:https://github.com/pcottle/learnGitBranching

网址:https://learngitbranching.js.org/

我熟悉很多工具都是通过小游戏来练习的,比如 vim 的操作,还是蛮推荐这种方式的。就不剧透啦,大家自己去探索吧~

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 28 收藏 21 评论 0

小齐本齐 发布了文章 · 10月10日

入职大厂,齐姐精选的 9 道 Java 集合面试题

Java 集合框架其实都讲过了,有一篇讲 Collection 的,有一篇讲 HashMap 的,那没有看过的小伙伴快去补下啦,文末也都有链接;看过的小伙伴,那本文就是检测学习成果的时候啦img

今天这篇文章是单纯的从面试的角度出发,以回答面试题为线索,再把整个 Java 集合框架复习一遍,希望能帮助大家拿下面试。

先上图:

当面试官问问题时,我会先把问题归类,锁定这个知识点在我的知识体系中的位置,然后延展开来想这一块有哪些重点内容,面试官问这个是想考察什么、接下来还想问什么。

这样自己的思路不会混乱,还能预测面试官下一个问题,或者,也可以引导面试官问出你精心准备的问题,这场面试本质上就是你在主导、你在 show off 自己扎实的基础知识和良好的沟通交流能力。

其实我在 LRU 那篇文章里就说到过这个观点,然后就有读者问我,说会不会被面试官看穿?

答:看出来了又怎样?面试官阅人无数,是有可能看出来的,但是也只会莞尔一笑,觉得这个同学很用心。

精心准备面试既是对面试官个人时间的尊重,也是表明了你对这家公司的兴趣,这样的员工不是每家公司都想要的吗?

好了,进入正题,今天就来解决这 9 大面试题。

1. ArrayList vs LinkedList

这题的问法很多,比如

  • 最简单的就直接问 ArrayList 和 LinkedList 的区别和联系;
  • 或者问你什么时候要选择 ArrayList,什么时候选择 LinkedList;
  • 或者在你们聊到某个场景、或者在算法题中,面试官问你如何选择。

万变不离其宗。

首先结论是:

  • 绝大多数的情形下都偏向于用 ArrayList,除非你有明确的要使用 LinkedList 的理由。
  • 如果你不确定用哪个,就用 ArrayList

两者在实现层面的区别是:

  • ArrayList 是用一个可扩容的数组来实现的 (re-sizing array);
  • LinkedList 是用 doubly-linked list 来实现的。

数组和链表之间最大的区别就是数组是可以随机访问的(random access)。

这个特点造成了在数组里可以通过下标用 O(1) 的时间拿到任何位置的数,而链表则做不到,只能从头开始逐个遍历。

两者在增删改查操作上的区别:

  • 在「改查」这两个功能上,因为数组能够随机访问,所以 ArrayList 的效率高;
  • 在「增删」这两个功能上,如果不考虑找到这个元素的时间,数组因为物理上的连续性,当要增删元素时,在尾部还好,但是其他地方就会导致后续元素都要移动,所以效率较低;而链表则可以轻松的断开和下一个元素的连接,直接插入新元素或者移除旧元素。

但是呢,实际上你不能不考虑找到元素的时间啊。。。虽然 LinkedList 可以 O(1) 的时间插入和删除元素,可以你得先找到地方啊!

不是有个例子么,修理这个零件只需要 1 美元,但是找到这个零件需要 9999 美元。我们平时修 bug 也是如此,重点是找到 root cause 的过程。

而且如果是在尾部操作,数据量大时 ArrayList 会更快的。

事实上,LinkedList 是很多性能问题的 bug,那么为什么呢?

因为 ListNode 在物理内存里的不连续,导致它用了很多小的内存片段,这会影响很多进程的性能以及 cache-locality(局部性);所以即便是理论上的时间复杂度和 ArrayList 一样时,也会导致实际上比 ArrayList 慢很多。

2. ArrayList vs Vector

答:

  1. Vector 是线程安全的,而 ArrayList 是线程不安全的;
  2. 扩容时扩多少的区别,文邹邹的说法就是 data growth methods不同,

    • Vector 默认是扩大至 2 倍;
    • ArrayList 默认是扩大至 1.5 倍。

回顾下这张图,

Vector 和 ArrayList 一样,也是继承自 java.util.AbstractList,底层也是用数组来实现的。

但是现在已经被弃用了,因为它是线程安全的。任何好处都是有代价的,线程安全的代价就是效率低,在某些系统里很容易成为瓶颈,所以现在大家不再在数据结构的层面加 synchronized,而是把这个任务转移给我们程序员。

那怎么知道扩容扩多少的呢?

看源码:


这是 Vecotr 的扩容实现,因为通常并不定义 capacityIncrement,所以默认情况下它是扩容两倍。

VS

这是 ArrayList 的扩容实现,算术右移操作是把这个数的二进制往右移动一位,最左边补符号位,但是因为容量没有负数,所以还是补 0.

那右移一位的效果就是除以 2,那么定义的新容量就是原容量的 1.5 倍。

3. ArrayDeque vs LinkedList

首先要清楚它们之间的关系:

答:

  1. ArrayDeque 是一个可扩容的数组,LinkedList 是链表结构;
  2. ArrayDeque 里不可以存 null 值,但是 LinkedList 可以;
  3. ArrayDeque 在操作头尾端的增删操作时更高效,但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的;
  4. ArrayDeque 在内存使用方面更高效。
  5. 所以,只要不是必须要存 null 值,就选择 ArrayDeque 吧!

那如果是一个很资深的面试官问你,什么情况下你要选择用 LinkedList 呢?

答:Java 6 以前。因为 ArrayDeque 在 Java 6 之后才有的。
为了版本兼容的问题,实际工作中我们不得不做一些妥协。

4. HashSet 实现原理

答:

HashSet 是基于 HashMap 来实现的,底层采用 Hashmap 的 key 来储存元素,主要特点是无序的,基本操作都是 O(1) 的时间复杂度,很快。
所以它的实现原理可以用 HashMap 的来解释。

5. HashMap 实现原理

答:

  • JDK1.6/1.7数组 + 链表
  • JDK 1.8数组 + 红黑树

具体说来,

对于 HashMap 中的每个 key,首先通过 hash function 计算出一个哈希值,这个哈希值就代表了在桶里的编号,而“桶”实际上是通过数组来实现的,但是桶有可能比数组大呀,所以把这个哈希值模上数组的长度得到它在数组的 index,就这样把它放在了数组里。

这是理想情况下的 HashMap,但现实中,不同的元素可能会算出相同的哈希值,这就是哈希碰撞,即多个 key 对应了同一个桶。

为了解决哈希碰撞呢,Java 采用的是 Separate chaining 的解决方式,就是在碰撞的地方加个链子,也就是上文说的链表或者红黑树

具体的 put()get()这两个重要 API 的操作过程和原理,大家可以在公众号后台回复「HashMap」获取文章阅读。

6. HashMap vs HashTable

答:

  1. Hashtable 是线程安全的,HashMap 并非线程安全;
  2. HashMap 允许 key 中有 null 值,Hashtable 是不允许的。这样的好处就是可以给一个默认值。

其实 HashMap 与 Hashtable 的关系,就像 ArrayList 与 Vector,以及 StringBuilder 与 StringBuffer。

Hashtable 是早期 JDK 提供的接口,HashMap 是新版的。这些新版的改进都是因为 Java 5.0 之后允许数据结构不考虑线程安全的问题,因为实际工作中我们发现没有必要在数据结构的层面上上锁,加锁和放锁在系统中是有开销的,内部锁有时候会成为程序的瓶颈。

所以 HashMap, ArrayList, StringBuilder 不再考虑线程安全的问题,性能提升了很多。

7. 为什么改 equals() 一定要改 hashCode()?

答:

首先基于一个假设:任何两个 objecthashCode 都是不同的。也就是 hash function 是有效的。

那么在这个条件下,有两个 object 是相等的,那如果不重写 hashCode(),算出来的哈希值都不一样,就会去到不同的 buckets 了,就迷失在茫茫人海中了,再也无法相认,就和 equals() 条件矛盾了,证毕。

  1. hashCode() 决定了 key 放在这个桶里的编号,也就是在数组里的 index
  2. equals() 是用来比较两个 object 是否相同的。

8. 如何解决哈希冲突?

一般来说哈希冲突有两大类解决方式:

  • Separate chaining
  • Open addressing

Java 中采用的是第一种 Separate chaining,即在发生碰撞的那个桶后面再加一条“链”来存储。

那么这个“链”使用的具体是什么数据结构,不同的版本稍有不同,上文也提到过了:

  • JDK1.6 和 1.7 是用链表存储的,这样如果碰撞很多的话,就变成了在链表上的查找,worst case 就是 O(n);
  • JDK 1.8 进行了优化,当链表长度较大时(超过 8),会采用红黑树来存储,这样大大提高了查找效率。

(话说,这个还真的喜欢考,已经在多次面试中被问过了,还有面试官问为什么是超过“8”才用红黑树 🤔)

第二种方法 open addressing 也是非常重要的思想,因为在真实的分布式系统里,有很多地方会用到 hash 的思想但又不适合用 seprate chaining

这种方法是顺序查找,如果这个桶里已经被占了,那就按照“某种方式”继续找下一个没有被占的桶,直到找到第一个空的。

如图所示,John Smith 和 Sandra Dee 发生了哈希冲突,都被计算到 152 号桶,于是 Sandra 就去了下一个空位 - 153 号桶,当然也会对之后的 key 发生影响:Ted Baker 计算结果本应是放在 153 号的,但鉴于已经被 Sandra 占了,就只能再去下一个空位了,所以到了 154 号。

这种方式叫做 Linear probing 线性探查,就像上图所示,一个个的顺着找下一个空位。当然还有其他的方式,比如去找平方数 Double hashing.

9. Collection vs Collections

这俩看似相近,实则相差十万八千里,就好像好人好人卡的区别似的。

Collection

  • 集合接口;
  • Java 集合框架root interface
  • 落脚点是一个 interface
  • 包含了以下这些接口和类:

想系统学习 Collection,可以在公众号内回复「集合」,获取爆款文章。

Collections 是工具类 utility class,是集合的操作类,提供了一些静态方法供我们使用,比如:

  • addAll()
  • binarySearch()
  • sort()
  • shuffle()
  • reverse()

好了,以上就是集合的常考面试题汇总和答案了,希望不仅能帮助你拿下面试,也能真的理解透彻,灵活运用。

最近看到自己的文章在其他平台被他人搬运,请大家认准全网统一唯一标识「码农田小齐」,并且恳请大家如果看到没有写明作者和来源出处的我的文章,告知我一声,这些文章都是自己的心肝宝贝啊嗷呜~

最后,如果你觉得一个人坚持的很难,想有小伙伴一起学习、互相监督打气的,记得加入我的自习室。

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 5 收藏 4 评论 1

小齐本齐 发布了文章 · 10月7日

一分钟了解堆的基本操作

基本操作

任何一个数据结构,无非就是增删改查四大类:

功能方法时间复杂度
offer(E e)O(logn)
poll()O(logn)
无直接的 API删 + 增
peek()O(1)

这里 peek() 的时间复杂度很好理解,因为堆的用途就是能够快速的拿到一组数据里的最大/最小值,所以这一步的时间复杂度一定是 O(1) 的,这就是堆的意义所在。

那么我们具体来看 offer(E e)poll() 的过程。

offer(E e)

比如我们新加一个 0 到刚才这个最小堆里面:

那很明显,0 是要放在最上面的,可是,直接放上去就不是一棵完全二叉树了啊。。

所以说,

  • 我们先保证加了元素之后这棵树还是一棵完全二叉树,
  • 然后再通过 swap 的方式进行微调,来满足堆序性。

这样就保证满足了堆的两个特点,也就是保证了加入新元素之后它还是个堆

那具体怎么做呢:

Step 1.

先把 0 放在最后接上,别一上来就想着上位;

OK!总算先上岸了,然后我们再一步步往上走。

这里「能否往上走」的标准在于:
是否满足堆序性

也就是说,现在 5 和 0 之间不满足堆序性,那么交换位置,换到直到满足堆序性为止

这里对于最小堆来说的堆序性,就是小的数要在上面

Step 2. 与 5 交换

此时 0 和 3 不满足堆序性了,那么再交换。

Step 3. 与 3 交换

还不行,0 还比 1 小,所以继续换。

Step 4. 与 1 交换

OK!这样就换好了,一个新的堆诞生了~

总结一下这个方法:

先把新元素加入数组的末尾,再通过不断比较与 parent 的值的大小,决定是否交换,直到满足堆序性为止。

这个过程就是 siftUp(),源码如下:

时间复杂度

这里不难发现,其实我们只交换了一条支路上的元素,

也就是最多交换 O(height) 次。

那么对于完全二叉树来说,除了最后一层都是满的,O(height) = O(logn)

所以 offer(E e) 的时间复杂度就是 O(logn) 啦。

poll()

poll() 就是把最顶端的元素拿走。

对了,没有办法拿走中间的元素,毕竟要 VIP 先出去,小弟才能出去。

那么最顶端元素拿走后,这个位置就空了:

我们还是先来满足堆序性,因为比较容易满足嘛,直接从最后面拿一个来补上就好了,先放个傀儡上来。

Step1. 末尾元素上位

这样一来,堆序性又不满足了,开始交换元素。

那 8 比 7 和 3 都大,应该和谁交换呢?

假设与 7 交换,那么 7 还是比 3 大,还得 7 和 3 换,麻烦。

所以是与左右孩子中较小的那个交换。

Step 2. 与 3 交换

下去之后,还比 5 和 4 大,那再和 4 换一下。

Step 3. 与 4 交换

OK!这样这棵树总算是稳定了。

总结一下这个方法:

先把数组的末位元素加到顶端,再通过不断比较与左右孩子的值的大小,决定是否交换,直到满足堆序性为止。

这个过程就是 siftDown(),源码如下:

时间复杂度

同样道理,也只交换了一条支路上的元素,也就是最多交换 O(height) 次。

所以 offer(E e) 的时间复杂度就是 O(logn) 啦。

那以上就是有关堆的基本操作啦!对于堆,还有一个比较特别的操作,就是 heapify(),这是一个很神奇的操作,至于神奇在何处、为什么它能做到、它是怎么做到的,我们下一篇文章再说~

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 2 收藏 2 评论 0

小齐本齐 发布了文章 · 10月6日

一分钟带你学懂——什么是堆?

上一篇的 「Java 集合框架」里,还剩下一个大问题没有说的,那就是 PriorityQueue,优先队列,也就是堆,Heap。

什么是堆?

堆其实就是一种特殊的队列——优先队列。

普通的队列游戏规则很简单:就是先进先出;但这种优先队列搞特殊,不是按照进队列的时间顺序,而是按照每个元素的优先级来比拼,优先级高的在堆顶

这也很容易理解吧,比如各种软件都有会员制度,某软件用了会员就能加速下载的,不同等级的会员速度还不一样,那就是优先级不同呀。

还有其实每个人回复微信消息也是默默的把消息放进堆里排个序:先回男朋友女朋友的,然后再回其他人的。

这里要区别于操作系统里的那个“堆”,这两个虽然都叫堆,但是没有半毛钱关系,都是借用了 Heap 这个英文单词而已。

我们再来回顾一下「」在整个 Java 集合框架中的位置:

也就是说,

  • PriorityQueue 是一个类 (class);
  • PriorityQueue 继承自 Queue 这个接口 (Interface);

<span style="display:block;color:blue;">那 heap 在哪呢?

heap 其实是一个抽象的数据结构,或者说是逻辑上的数据结构,并不是一个物理上真实存在的数据结构。

<span style=";color:blue;">heap 其实有很多种实现方式,</span>比如 binomial heap, Fibonacci heap 等等。但是面试最常考的,也是最经典的,就是 binary heap 二叉堆,也就是用一棵完全二叉树来实现的。

<span style="display:block;color:blue;">那完全二叉树是怎么实现的?

其实是用数组来实现的!

所以 binary heap/PriorityQueue 实际上是用数组来实现的。

这个数组的排列方式有点特别,因为它总会维护你定义的(或者默认的)优先级最高的元素在数组的首位,所以不是随便一个数组都叫「堆」,实际上,它在你心里,应该是一棵「完全二叉树」。

这棵完全二叉树,只存在你心里和各大书本上;实际在在内存里,哪有什么树?就是数组罢了。

那为什么完全二叉树可以用数组来实现?是不是所有的树都能用数组来实现?

这个就涉及完全二叉树的性质了,我们下一篇会细讲,简单来说,因为完全二叉树的定义要求了它在层序遍历的时候没有气泡,也就是连续存储的,所以可以用数组来存放;第二个问题当然是否。

堆的特点

  1. 堆是一棵完全二叉树;
  2. 堆序性 (heap order): 任意节点都优于它的所有孩子

    a. 如果是任意节点都大于它的所有孩子,这样的堆叫大顶堆,Max Heap;

    b. 如果是任意节点都小于它的所有孩子,这样的堆叫小顶堆,Min Heap;

左图是小顶堆,可以看出对于每个节点来说,都是小于它的所有孩子的,注意是所有孩子,包括孙子,曾孙...

  1. 既然堆是用数组来实现的,那么我们可以找到每个节点和它的父母/孩子之间的关系,从而可以直接访问到它们。

比如对于节点 3 来说,

  • 它的 Index = 1,
  • 它的 parent index = 0,
  • 左孩子 left child index = 3,
  • 右孩子 right child index = 4.

可以归纳出如下规律:

  • 设当前节点的 index = x,
  • 那么 parent index = (x-1)/2,
  • 左孩子 left child index = 2*x + 1,
  • 右孩子 right child index = 2*x + 2.

有些书上可能写法稍有不同,是因为它们的数组是从 1 开始的,而我这里数组的下标是从 0 开始的,都是可以的。

这样就可以从任意一个点,一步找到它的孙子、曾孙子,真的太方便了,在之后讲具体操作时大家可以更深刻的体会到。

那有关堆的基本操作,以及为什么 heapify() 是 O(n) 的,我们之后再聊。

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 3 收藏 2 评论 0

小齐本齐 发布了文章 · 9月30日

在家工作了半年,齐姐这些有意思的事想和你们分享

在家工作已经 7 个月了,下周就进入今年的最后一个季度,大家的 new year resolution 还好吗?

我反正是一堆没完成且完不成的,比如学车这种,现在这病毒满天飞也没法学。

唉说起开车还是我一大痛处。因为我上学早,高考后我还不到 18 岁,所以没法考驾照,以至于浪费了最好的一段时间。后来大四了被我妈唠叨着终于在过完年返校之前拿下了驾照,但我一直没开过车。。所以几年过去我现在还是不会开车(羞愧)。

在我看来会开车应该算一项生存技能,就和会做饭一样,不会没关系,但是会了会方便很多,特别是能带着爸妈去自驾,也是我的一个小小的愿望。

提高效率小心得

说回在家工作,一开始在家工作还是很不习惯的。

之前通勤每天都很有节奏,早上的每分每秒都是安排好的。而不需要去公司之后,那种紧迫感就没了,导致我早上会浪费很多时间。所以后来我赶紧制定新的计划,养成新的习惯和节奏。

目前我的安排是:

  • 7:30 起床
  • 7:30 - 8:00 健身(一般是跟着 zoey 或者长腿姑娘练)
  • 8:00 - 8:30 洗漱、早餐(同时听 WSJ)
  • 8:30 - 9:00 回复微信、准备直播、看新闻
  • 9:00 开始工作

这个节奏目前我还是比较满意的,虽然不是那种每分每秒都要掐点的,但也是比较充实而且能长期适用的,周末也不用改变。

其实在家工作有好多有意思的事,这里从朋友圈汇总了下大家出的幺蛾子:

  1. 午觉睡的太香,梦到了自己开会,于是把会睡过去了。
  2. 发邮件写了满满一堆却忘了添加附件。
  3. Skype 和同事八卦不小心发给了老板还没办法撤回。
  4. 开会时点烧烤以为自己 mute 了其实并没有。
  5. 开会时候撸猫以为没人发现,其实所有人都在看那只猫。

回归主题,这里我也总结了几个在家工作提高效率的小心得分享给大家~

  1. 设定一个专属的工作区,告诉自己在这里只有工作。

比如我是用屏风隔开的,把客厅分为了工作区和健身区。

  1. 穿衣打扮梳妆不能省。

记得几年前听到一个小姐姐跟我讲,她每天在家也要涂防晒霜,我心里的白眼 🙄️ 恐怕都要翻上天了。

而如今,没想到自己在家还会化妆 🙄

最初是因为我要和老板 1:1,要开视频开会的,所以打扮了一下,然后我就发现自己那天心情很好,整个人状态也很好,工作效率就很高!

学生时代总是被教育不要打扮啊,天天穿校服。以至于我到了大四还不知道粉底液为何物,毕业之前拍毕业照还找别人化的妆。

来到纽约之后发现精致的妆容是小姐姐们的标配,其实化妆是表达了对自己、对别人的重视,也是一种生活态度。

  1. 固定工作时间。

这个是直播自习给我带来的习惯。

在直播之前,每天啥时候开始工作取决于那天早上几点有会、同事有没有找我的...但相对应的就是每天晚上工作到很晚,毕竟活是要做完的,时间都是要花的。

那现在,我已经习惯了 9 点准时开始工作,手机放一边,全身心专注的工作,这样效率倍增。

但是没做好的一点就是晚上下班的时间,依然还是没有明确的界限,而且如果是 on call,那简直就是工作到睡觉。。

  1. 多露脸,刷存在感。

在家工作毕竟老板看不到人,而老板一天到晚这么忙,就需要我们多去刷脸。

比如如果老板交给我的任务,那就每天都要 update 进度,说一声自己怎么样了,让老板心里有数。

然后组里开会时多说话,多评论,以及我们有两周一次的 demo 的会议,基本我每次都参加,讲一下过去两周自己做的亮点。

上次讲了一个还被大老板点名说要之后给整个部门做 tech talk,这样下次和大老板 1:1 时也有话题可聊。

  1. 利用好和老板 1:1 的机会。

每周和老板的一对一是一个非常好的回顾总结的机会。

每次老板给我的建议都非常中肯。现在觉得当老板好难啊,手下 6 个人,每个人在做什么、有什么问题、进度怎样都要了如指掌,觉得老板对我的 mid year review 比我自己写的都好。。很多细节我都没写出来(也是觉得没必要写),老板都还记得。

有人给反馈真的是挺难得的。比如我的某些文章的阅读量低,只能靠自己推理猜测(恳请大家给我反馈);而工作上老板可以很明确的告诉我哪里做得不够,应该怎么改进,对于提升自己真的非常有帮助。

这也是我建议大家毕业后的第一份工作去大公司的原因,大公司有完善的 review 的机制,可以很好的帮你去提升自己。当然如果个人能力足够强, 又有很高的情商,在哪都是一样的。


其实在家工作我是觉得大家都更认真了。

之前在公司 6 点基本就没人了,但是现在 6 点几乎所有人都在线,各种群里的消息还是不停。

截至目前为止,组里的人基本每人休假都不超过 3 天。要知道我们一年是有 23 天假期的啊!

而且为了鼓励大家休假,8 月部门领导奖励大家每人 1 天假期。于是大家就只休 1 天。。

现在公司又给每个人 10 天的 personal day,也就是现在每个人都应该有 30 天左右的假期,而今年,只剩 3 个月了。。

大家宁愿浪费掉也不休假,我想,这就是囚徒困境吧。

为了自己不在这次危机中掉队,每个人都拼命的工作,把自己的 performance 弄的非常好。

但结果呢?公司发现大家远程办公都很成功,结果就真的不需要我们了啊。公司可以从其他州、其他国家,雇佣便宜的劳动力,反正都是远程啊。

健身

健身应该是我今年的一大痛点了。

最初是在伯克利养成健身的习惯,后来回武大之后只能自己简单练练,再后来来了美国,公寓和学校都有健身房,于是这几年健身没停过,每周至少也回去运动 3 次。

而今年。。。本年度的增肌塑形目标是完不成了。

虽然器械都到位了,但是毕竟有好多还是固定器械更好用,借口不想增加脂肪,所以现在改为维持期。。

于是。。健身区从这个样子:

<img data-original="https://tva1.sinaimg.cn/large/007S8ZIlly1gj8dg24k8nj31400u0kjl.jpg" alt="健身区1" style="zoom:50%;" />

变成了这个样子:

<img data-original="https://tva1.sinaimg.cn/large/007S8ZIlly1gj8dgpsgj3j30u01407wi.jpg" style="zoom:50%;" />

宅家半年,能够明显的感受到自己身体的变化,比如 3 个月没出门后的第一次出门,能感觉体能的大幅下降,哪怕是现在也能感受到心肺不如以前。

我自认为我是很自律的人,但是长期在家带来的精神上的压抑,而且剧烈运动后免疫力会下降,所以运动强度也不敢太大。

但后来纽约开放之后,大概在 7 月,我开始了每周末出门骑行,并且平时在家也加强了锻炼,感觉身体在恢复。

对了,每次骑行也录了视频,但是一直也没剪 🤭

这个月,我终于下定决心买了升降桌!真的是我这半年最好的投资。

<img data-original="https://tva1.sinaimg.cn/large/007S8ZIlly1gj8em51lamj30u0140npd.jpg" style="zoom:50%;" />

有了升降桌之后,幸福感大大提升!一是不会久坐了,二是可以在看视频的时候也活动一下。

唯一的缺点就是这个桌子有点小。。对我来说放两个电脑和屏幕之后放不下任何东西了。

但同时也逼着我把桌面都清理干净,只能保留目前手头在做的需要用到的东西,反而更专注了呢。

  • 3 月的时候觉得 4 月要回公司了,没买;
  • 4 月的时候觉得 6 月要回公司了,没买;
  • 后来公司给了报销费用,买别的了;
  • 6 月的时候觉得已经过去 3 个月了,不用也罢;
  • 9 月的时候觉得,生活每时每刻都值得认真对待,怎么过今年,就怎么过一生。

毕竟钱没了还能再赚,身体坏了就什么都没了。

云自习

最后呢,照例月末宣传一下我的自习室。

如果还不了解的同学可以看下之前 8 月、9 月的这两篇文章:

我是如何高效率地学习、工作、生活的?

我是如何做到自律的?

如果你想在 10 月和我们一起学习,提高自己自律的能力,那就在公众号后台回复【自习】,加入自习室吧~~

送书

喜迎国庆中秋,华章书院联合齐姐给大家送出 4 本高并发的书~~

这本书从底层原理总结和归纳各个技术细节,结合真实的案例深入分析微基准测试、性能度量、Java 高并发类库的原理及应用。详细介绍了 Java 微基准测试工具集 JMH 与平台级性能指标数据度量工具 Metrics 的使用方法,帮助读者快速开发出高效、健壮的并发应用程序。

本次的送书规则就是抽奖啦~~

开奖时间是北京时间 10 月 3 号晚上 8 点

祝大家节日快乐,玩得开心!

查看原文

赞 4 收藏 1 评论 0

小齐本齐 发布了文章 · 9月29日

靠这些秋招秘笈,齐姐的学妹今年已经拿到了 8 个offer!

小齐说:

现在秋招进行时,正在找工作的小伙伴进度都怎么样了呀?

今天这篇文章是我武大的学妹今年秋招的经验分享,庆妹去年才决定转行,现在已手握 N+ 个 offer ~

这篇文章干货满满,庆妹对每一块面试考察点都给出非常具体、详细的资料和书籍推荐,我看了都很有启发,希望对你也能有所帮助呀。


2020 年秋招过了一半了,我目前收到了百度,快手,Shopee,作业帮,TpLlink 的意向书,腾讯,华为和微博面试也已经通过,等待录用。岗位都与后台开发、C++开发有关。

我本身并不是计算机专业,比不上收割 SSP offer 的大佬。这篇文章我就跟大家谈谈非科班的后台开发求职路线吧。

背景介绍

去年这个时候我的编程水平也就是能用 C 语言写 HelloWord 的水平,我的学习路线就是一个真实的纯小白的进化史了。

介绍一下我的编程背景,我研究生就读的武汉大学 xx 学院的二年制专业硕士,研究方向与深度学习有关。本科时上过 C 语言、数据结构、计算机网络这些课程,不过都忘的差不多了。

由于我是专硕,在研究生第一学年结束就要马上开始找工作,所以我在刚入学就有了就业意识。

那时候和 2019 年秋招的一位学长交流了许多,学长拿了武汉字节,上海拼多多的 offer,字节年薪30 万,拼多多年薪50 万

从来没有见过这么多钱的我瞬间惊呆了!原来在互联网开发可以赚这么多钱。我对开发工作产生了一些心动。

并且学长鼓励我在一年之内是完全能够达到他这样的水平,于是我就初步将后台开发方向作为我的就业方向。

C++ vs Java?

选择哪一门编程语言?

目前秋招后台开发求职主要有两种语言,C++和 java。

Java 的就业方向更广,阿里美团,银行和一些中小厂技术栈 80% 以上是 Java,生态圈更加完善,比较好提升背景项目。正因为这样,学 Java 的人很多,竞争非常激烈。

选 C++也有优点,腾讯的技术栈主要是 C++,学习 C++可以走算法优化方向,这是算法落地的一个热门方向。而且, C++比 Java 学习的知识点要少。

过去的我确实也在语言的选择上纠结了好久,但是当我走过秋招,发现其实语言并没有想象的那么重要。

在做笔试的时候两种编程方式都可以选择。在面试的时候,面试官会针对我们熟悉的语言针对考察。所以无论是 C++还是 Java,甚至是 python 或是 C#都是没问题的。

由于当时实验室的师兄都用的 C++,如果学习遇到了困难我有人可以问,于是最后我选择了 C++。

资料分享

接下来谈谈学习后台开发需要看的资料,主要分为

  • C++语言
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • 项目经历
  • Linux 使用
  • 数据库
  • 设计模式

这 8 大部分。

其中前五个部分是需要重点准备的,后面三个部分学有余力可以充分准备,没有时间的话了解常考面试题也是可以的。

如果你想准备其他语言,除了语言部分,其他部分都是适用的。

C++ 语言

C++ primer 前三大部分——C++基础、C++标准库和类设计者的工具,学习 C++基本语法,容器的常用用法,了解 C++11 新特性。

进阶阶段推荐看《STL 源码剖析》和 _Effective C++_,前者了解 C++容器的底层数据结构,后者涉及了很多 C++面试的内容。

数据结构与算法

了解数据结构看“如果天空不死”的数据结构部分博客,这个博客利用画图的方式把数据结构用浅显易懂的方式表示出来。看博客时除了排序算法部分要看程序以外,其余部分熟悉概念即可。

学习算法我是上了牛客网左程云老师的算法视频课,我非常推荐这门课程,因为这门课讲解了面试中最常见的数据结构考点和面试算法题考点,还讲解了一些看起来高大上的内容可供面试装逼。

当然,算法部分还需要通过刷算法题,不断巩固熟练度。《剑指 offer》和 Leetcode 前 hot100 争取刷三遍。

做到以上,面试 90%能遇到原题。

计算机网络

先看《图解 TCP/IP》,对 TCP/IP 协议有些初步印象

接下来看《计算机基础》,只要看有关 TCP 和 IP 协议的部分。

通过博客学习 HTTP 协议,例如 CS2018.

进阶阶段需要学习计算机网络编程,看《UNIX 网络编程卷 1》

操作系统

推荐《深入理解计算机基础》,从第五章虚拟内存开始看。这本书非常经典,能够熟知这本的知识,面试中的操作系统问题绝对没问题。

清华大学操作系统课程,学堂在线可看。

有些大佬推荐看现代操作系统,Linux 内核这些书,这些书面试中考察的不多,可以以后工作了看。

下次一定。

项目准备

看了陈硕《Linux 高性能服务器编程》这本书,基于这本书在 github 上学习了一位大佬写的 web 服务器。

学 C++方向的很多同学都准备了 web 服务器,导致我后期面试跟别人撞车。

项目经历可以说是我的弱项了。有精力想要冲大厂的同学,可以看看陈硕的 Module 库,了解下一些开源库的源码,比如 libevent nginx 等。

Linux 使用

我看了 B 站尚学堂的 Linux 视频教程,课程内容涵盖了大多数面试内容。

数据库

基础入门看《MySql 必知必会》,进阶看《高性能服务器》前四章。

设计模式

学会单例模式和工厂模式这两种模式即可。

什么时候投简历最好?提前批!

2020 年疫情期间,我花了三个月把之前提到的学习资料看了一遍,还花了些零零散散的时间看了牛客网上的面试经典问题。

六月份,我的秋招之旅便开始了。

七月初很顺利的斩获了我的第一个 offer——Tplink 后端开发。七月份很多互联网知名公司提前批都开始了,于是我开始了疯狂海投、笔试和面试的过程,最忙的时候一天有 5 场面试。

大家一定要在提前批抓住机会,不要等到完全做好准备了再投简历。

一是你准备好了,别人也就准备好了。

二是很多公司提前批免除了笔试的过程,面试难度也比正式批要小。

三是到了正式批,很多人会学会搞骚操作。

我了解到居然有一个实验室的人同时帮一个同学做笔试的情况,我就说怎么到了正式批我的笔试通过率变低了。

面试是一个查漏补缺的过程,面试完之后做好总结,“以战养战”才是进步最快的方式。

七月中旬牛客做了一个 SP 提前批专场的活动,每个公司都有投,虽然说多数毫无音信,甚至一些不太知名的游戏公司直接通知我简历不过,把我气的半死,不过我最想去的 Shoppe 通过了简历筛选,免除了笔试环节,要知道笔试就要挂很多人。最后我的 offer 基本上都是在提前批拿到的。

当然找工作免不了焦虑的时候。

八月上旬字节提前批三面挂,网易互娱一面挂,快手 HR 面之后也没有准信,那段时间真的有些低气压。

我不是一个心态很好的人,失败的时候就会生气焦虑。我也不喜欢给自己灌鸡汤,找不到工作我就是烦。

我觉得这很正常啊,是个人找不到心仪的工作都会很崩溃,那段时间经常我还经常跟我妈吵架。

可生活不能老这样,我得调节自己,烦躁的时候我就啥也不干,玩玩手机,放空自己。

在找工作期间我还养了两只小乌龟,他们太可爱了,看着他们就特别解压。

另外,找工作别看牛客,一堆大佬 show 自己收到大佬 offer,越看越烦。

八月中旬心态崩溃,去长沙玩了一圈,回到家隔天收到了 Shopee 意向书,心里放松了大半。

之后的过程也慢慢的越来越顺利,继续笔试面试的过程,在九月初赶在开学前收获了百度,快手的意向书。

回到学校以后,由于导师盯得紧,能面试的时间很少。所以接下来的阶段,主要是利用有限的时间冲冲大厂,再准备一些心仪的国企银行。

当然了,互联网也许不是人生的最优解,毕竟容易出现中年危机不是?

但是无论是去国企还是银行,都需要提前准备的意识。

如果大家有准备前端算法或者其他方向的,可以参考这下面这个牛客网址:https://www.nowcoder.com/discuss/351700


非常感谢庆妹的无私分享,也祝庆妹在接下来的面试中一切顺利,好好享受最后一年学生时光,齐姐真是羡慕你们呀~

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 2 收藏 1 评论 0

小齐本齐 发布了文章 · 9月25日

在市值破万亿美元的公司工作,是一种怎样的体验?

<span style="display:block;text-align:center;">这里是《齐姐聊大厂》系列的第 7 篇

<span style="display:block;text-align:center;">(前 6 篇见文末)

<span style="display:block;text-align:center;">每周五早上 8 点,与你唠唠大厂的那些事。

小齐说:

8 月 19 日,苹果公司股价飙升至 468 美元,总市值首次超过 2 万亿美元。

虽然疫情影响了苹果的线下零售,但是第三季度营业额高达 596.9 亿美元,远高于市场对它的预期。

第一代苹果发布会,我看过不下于五遍。一方面是惊叹于当之无愧的革命性产品,改变了世界的产品,也改变了几十亿人的生活方式;另一方面是被乔帮主的魅力所折服,毕竟我是听过十遍乔帮主在斯坦福大学演讲的人。

这里我们只谈产品和技术,并不代表任何其他立场。

今天有幸请到博士大佬 littlelab,分享他在苹果公司工作的体验,让我们一起来感受下吧~


离开苹果有一段时间了,感觉还是很怀念那段工作经历,如果不是不同的职业道路选择,我想自己应该还在那个组,只是现在写这篇文章的是别人,而读者是我。

这是毕业后的第一份工作,对于一个刚从火坑专业中挣扎出来的 PhD 来说,拿到一份优厚的薪水,已经感激涕零。虽然到了湾区后,听到其它公司的薪酬大开眼界,但是想想自己顺利的入职经历,依然有种对公司的感动。

日子一天天过去,头半年很有意思,虽然辛苦,但是学到很多东西。因为每天都在接触新事物,每天都在认识新人,所以很喜欢上班。

组里中国人很多,大家中午一起吃饭。我老板特别能讲,有段时间最喜欢听他在午饭的时候吹牛,一吹能吹一个小时。然后大家再回去,打杯咖啡, 在自己的小隔间里忙碌起来。

过了一年的时间,渐渐开始关心自己的职业发展,开始想到 3 年后的自己,想到 5 年后的自己,也开始关心起周围人的履历。

苹果能人太多,很多 manager 都是某个领域的大牛或者小牛,有的还有几本书。不少领军人物已经到了白发苍苍的年纪,被苹果从其它公司挖过来。有的过来当一方大员开疆拓土,有的过来组建团队管理下属,也有过来养老的,写写 spec,但依然像尊神一样让人仰止。

Spec: specifications,对产品或者协议的指标规定,一般在设计新的协议时会出现,往往由一些领域里有影响力的公司牵头,组织专家制定。

我的小 manager 来苹果五年多了,从业也十多年了,之前还收获了很多奖项,小到 DesignCon 的 best paper,大到其它公司发给他的终身成就奖,大大小小都摆在办公室里。因为从小来美国,英文说的和美国人没区别,project meeting 上经常舌战群雄。

DesignCon 是电路板和电磁仿真领域的工业界的重要会议,很多公司会上去发布新的技术。能够拿到 best paper 这个奖项的很少。

不过他也等五年才升上 manager。

他的上司大 manager 更是著作加身,不知道他在苹果工作多久了,到他那个级别,已经需要把一些精力放到政治斗争上了。

五年是个不短的时间,然而五年不是向上升迁的决定条件,只是必要条件而已。

组里的人每个都兢兢业业,做技术报告比 PhD 的答辩论文还仔细。

也有不少五年多还是 IC 的,不是技术不行,有可能是语言吧,也有可能是年龄太轻,当然更重要的是因为没有那么多职位。

IC: Individual Contributor,不管人的职位都叫 IC,和 manager 相对。

如果我就这样安心的工作,也许工作个十几年,我也能学到顶尖技术,虽然可能还是个 IC。

苹果我长期还是看好的,虽然大家诟病它表现出来的创新力,但那只是冰山一角。但我也能看到未来自己日复一日的生活,正如每天和我一起吃饭的 senior engineer 一样,平静和充实。

在这里,绝大部分人的职业声誉都将从此被抹去,因为你不能给外面做报告,不能发表论文,不能积攒自己在业界的影响力。

在苹果可能很多人都认识你,出了苹果也许一个人都不认识你。那时的我就像湾区千千万万的中年工程师一样,默默的为公司贡献着自己的青春和潜力。

然而年轻人就是这样不知足,想折腾。

前后组里走了好几个年轻的 IC,我也是其中之一。大家去了不同的公司,不同的行业,不同的国家。

每个人都有自己独特的追求,但若问我们离职有什么共同的原因,我想不为待遇,只为一颗对得起青春的躁动的心吧。


小齐说:非常感谢 littlelab 的分享,因为苹果对保密非常看重,所以虽然已经离职了,博士也不便多说,还希望大家理解。

其实身边能加入苹果的还是很少的,原因之一是苹果的面试难度不亚于谷歌,之二是苹果基本不招应届生,更多偏向于有工作经验的或者博士。

本文已收录至我的 Github 上:https://github.com/xiaoqi6666/NYCSDE,这个 Github 汇总了我所有的文章和资料,之后也会一直更新和维护。点击阅读原文即可直达,还希望大家帮忙点个 Star,你们的支持和认可,就是我创作的最大动力!


最后呢,附上周一线程池这篇文章文末的送书中奖名单:

  • 二三
  • jonyare
  • 冯煜
  • 😪
  • 🦋

恭喜以上 5 位同学啦~

没有中奖的同学也不要灰心,每个月都会有至少一次的送书活动,积极互动混脸熟都会有的。感谢大家的支持,我们下期见!

往期《齐姐聊大厂》文章

每周五早上 8 点,公众号首发。

查看原文

赞 1 收藏 1 评论 0

小齐本齐 发布了文章 · 9月24日

从 LRU Cache 带你看面试的本质

前言

大家好,这里是《齐姐聊算法》系列之 LRU 问题。

在讲这道题之前,我想先聊聊「技术面试究竟是在考什么」这个问题。

技术面试究竟在考什么

在人人都知道刷题的今天,面试官也都知道大家会刷题准备面试,代码大家都会写,那面试为什么还在考这些题?那为什么有些人代码写出来了还挂了?

大家知道美国的大厂面试 80%是在考算法,这其实是最近 5-10 年以谷歌、雅虎为首才兴起的;国内大厂对于算法的考察虽然没有这么狂热,但也越来越重视了。

那么算法面试真的只是在考算法吗?显然不是。本质上考的是思考问题的方式,分析、解决问题的能力,以及和同事沟通交流的能力,看你能否主动推进去解决问题。

答题思路

套路就是:

  • clarify 问题
  • 分析思路、时空复杂度、分析哪里可以优化、如何优化
  • 写代码
  • run test cases

虽说是套路,但何尝不是一个高效的工作方式?

那拿到一个问题,首先应该是去 clarify 这个问题,因为工作就是如此,不像在刷题网站做题什么都给你定义好了,面试官通常都不会一次性给你所有条件,而是需要你思考之后去问他。那通过这个环节,面试官就知道了你遇到问题是怎么去思考的,你考虑的是否全面,怎么去和别人沟通的,今后和你一起工作的状态是怎样的。

就像我们平时工作时,需要和 product manager 不断的 clarify 需求,特别是没定义清楚的部分,反反复复的讨论,也是磨刀不误砍柴工。那这个过程,在我司可能就要 1-2 周,不会很着急的就开始,否则努力错了方向就是南辕北辙,得不偿失。那么面试时也是一样,代码都写完了面试官说这不是我想问的,那时候已经没时间了,买单的是我们自己。

第二点分析思路就是重中之重了,也是本文的核心,会以 LRU Cache 这到经典题为例,展示我是如何思考、分析的。

第三点写代码,没什么好说的,终究是需要落到实处的。

第四点跑测试,很多同学可能会忘,所以如果你能主动提出 run test cases,过几个例子检验一下,是很好的。

  • 一来是给自己一个修正的机会,因为有很多 bug 是你跑两个例子就能发现的,那即使有点 bug 你没发现,只要你做完了这一步,面试官当场也没发现的话,那面试结束后面试官虽然会拍照留念,但也不会闲的无聊再自己打到电脑上跑的;
  • 二来是展示你的这种意识,跑测试的意识,这种意识是很重要的。

有些人说每道题我都做出来了,为什么还是挂了?那照着这四点对比一下,看看是哪个环节出了问题。

常考不衰的原因

另外这道题为什么各大公司都喜欢考呢?

一是因为它能够多方面、多维度的考察 candidate:这道题考察的是基本功,考对数据结构理解使用,考能不能写出 readable 的代码。一场 45 分钟-60 分钟的面试,如何摸清楚 candidate 的真实水平,也是不容易的啊。

二是因为这道题可难可易,可以简单到像 Leetcode 上那样把 API 什么的都已经定义好了,也可以难到把 System Design 的内容都包含进来,聊一下 Redis 中的近似 LRU 算法。

所以 follow up 就可以无限的深入下去,如果面试官想问的你都能回答的头头是道,那 strong hire 自然跑不掉。那有些同学只会到第一层或者第二层,面试是优中选优的过程,其他同学会的比你多,沟通交流能力又好,自然就是别人拿 offer 了。

那今天就以这道题为例,在这里浅谈一下我的思考过程,为大家抛砖引玉,欢迎在留言区分享你的想法。

LRU Cache

LRU 是什么

LRU = Least Recently Used 最近最少使用
它是一种缓存逐出策略 cache eviction policies

LRU 算法是假设最近最少使用的那些信息,将来被使用的概率也不大,所以在容量有限的情况下,就可以把这些不常用的信息踢出去,腾地方。

比如有热点新闻时,所有人都在搜索这个信息,那刚被一个人搜过的信息接下来被其他人搜索的概率也大,就比前两天的一个过时的新闻被搜索的概率大,所以我们把很久没有用过的信息踢出去,也就是 Least Recently Used 的信息被踢出去。

举个例子:我们的内存容量为 5,现在有 1-5 五个数。

我们现在想加入一个新的数:6
可是容量已经满了,所以需要踢出去一个。

那按照什么规则踢出去,就有了这个缓存逐出策略。比如:

  • FIFO (First In First Out) 这个就是普通的先进先出。
  • LFU (Least Frequently Used) 这个是计算每个信息的访问次数,踢走访问次数最少的那个;如果访问次数一样,就踢走好久没用过的那个。这个算法其实很高效,但是耗资源,所以一般不用。
  • LRU (Least Recently Used) 这是目前最常用了。

LRU 的规则是把很长时间没有用过的踢出去,那它的隐含假设就是,认为最近用到的信息以后用到的概率会更大。

那我们这个例子中就是把最老的 1 踢出去,变成:

不断迭代...

Cache 是什么?

简单理解就是:把一些可以重复使用的信息存起来,以便之后需要时可以快速拿到。

那至于它存在哪里就不一定了,最常见的是存在内存里,也就是 memory cache,但也可以不存在内存里。

使用场景就更多了,比如 Spring 中有 @Cacheable 等支持 Cache 的一系列注解。上个月我在工作中就用到了这个 annotation,当然是我司包装过的,大大减少了 call 某服务器的次数,解决了一个性能上的问题。

再比如,在进行数据库查询的时候,不想每次请求都去 call 数据库,那我们就在内存里存一些常用的数据,来提高访问性能。

这种设计思想其实是遵循了著名的“二八定律”。在读写数据库时,每次的 I/O 过程消耗很大,但其实 80% 的 request 都是在用那 20% 的数据,所以把这 20% 的数据放在内存里,就能够极大的提高整体的效率。

总之,Cache 的目的是存一些可以复用的信息,方便将来的请求快速获得。

LRU Cache

那我们知道了 LRU,了解了 Cache,合起来就是 LRU Cache 了:

当 Cache 储存满了的时候,使用 LRU 算法把老家伙清理出去。

思路详解

说了这么多,Let's get to the meat of the problem!

这道经典题大家都知道是要用 HashMap + Doubly Linked List,或者说用 Java 中现成的 LinkedHashMap,但是,为什么?你是怎么想到用这两个数据结构的?面试的时候不讲清楚这个,不说清楚思考过程,代码写对了也没用。

和在工作中的设计思路类似,没有人会告诉我们要用什么数据结构,一般的思路是先想有哪些 operations,然后根据这些操作,再去看哪些数据结构合适。

分析 Operations

那我们来分析一下对于这个 LRU Cache 需要有哪些操作:

  1. 首先最基本的操作就是能够从里面读信息,不然之后快速获取是咋来的;
  2. 那还得能加入新的信息,新的信息进来就是 most recently used 了;
  3. 在加新信息之前,还得看看有没有空位,如果没有空间了,得先把老的踢出去,那就需要能够找到那个老家伙并且删除它;
  4. 那如果加入的新信息是缓存里已经有的,那意思就是 key 已经有了,要更新 value,那就只需要调整一下这条信息的 priority,它已经从那次被宠幸晋升为贵妃了~

找寻数据结构

那第一个操作很明显,我们需要一个能够快速查找的数据结构,非 HashMap 莫属,还不了解 HashMap 原理和设计规则的在公众号内发消息「HashMap」,送你一篇爆款文章;

可是后面的操作 HashMap 就不顶用了呀。。。

来来来,我们来数一遍基本的数据结构:
Array, LinkedList, Stack, Queue, Tree, BST, Heap, HashMap

在做这种数据结构的题目时,就这样把所有的数据结构列出来,一个个来分析,有时候不是因为这个数据结构不行,而是因为其他的数据结构更好。

怎么叫更好?忘了我们的衡量标准嘛!时空复杂度,赶紧复习递归那篇文章,公众号内回复「递归」即可获得。

那我们的分析如下:

Array, Stack, Queue 这三种本质上都是 Array 实现的(当然 Stack, Queue 也可以用 LinkedList 来实现。。),一会插入新的,一会删除老的,一会调整下顺序,array 不是不能做,就是得 O(n) 啊,用不起。

BST 同理,时间复杂度是 O(logn).

Heap 即便可以,也是 O(logn).

LinkedList,有点可以哦,按照从老到新的顺序,排排站,删除、插入、移动,都可以是 O(1) 的诶!但是删除时我还需要一个 previous pointer 才能删掉,所以我需要一个 Doubly LinkedList.

那么我们的数据结构敲定为:
HashMap + Doubly LinkedList

定义清楚数据结构的内容

选好了数据结构之后,还需要定义清楚每个数据结构具体存储的是是什么,这两个数据结构是如何联系的,这才是核心问题。

我们先想个场景,在搜索引擎里,你输入问题 Questions,谷歌给你返回答案 Answer。

那我们就先假设这两个数据结构存的都是 <Q, A>,然后来看这些操作,如果都很顺利,那没问题,如果有问题,我们再调整。

那现在我们的 HashMap 和 LinkedList 长这样:

然后我们回头来看这四种操作:

操作 1,没问题,直接从 HashMap 里读取 Answer 即可,O(1);

操作 2,新加入一组 Q&A,两个数据结构都得加,那先要判断一下当前的缓存里有没有这个 Q,那我们用 HashMap 判断,

  • 如果没有这个 Q,加进来,都没问题;
  • 如果已经有这个 Q,HashMap 这里要更新一下 Answer,然后我们还要把 LinkedList 的那个 node 移动到最后或者最前,因为它变成了最新被使用的了嘛。

可是,怎么找 LinkedList 的这个 node 呢?一个个 traverse 去找并不是我们想要的,因为要 O(n) 的时间嘛,我们想用 O(1) 的时间操作。

那也就是说这样记录是不行的,还需要记录 LinkedList 中每个 ListNode 的位置,这就是本题关键所在。

那自然是在 HashMap 里记录 ListNode 的位置这个信息了,也就是存一下每个 ListNode 的 reference。

想想其实也是,HashMap 里没有必要记录 Answer,Answer 只需要在 LinkedList 里记录就可以了。

之后我们更新、移动每个 node 时,它的 reference 也不需要变,所以 HashMap 也不用改动,动的只是 previous, next pointer.

那再一想,其实 LinkedList 里也没必要记录 Question,反正 HashMap 里有。

这两个数据结构是相互配合来用的,不需要记录一样的信息。

更新后的数据结构如下:

这样,我们才分析出来用什么数据结构,每个数据结构里存的是什么,物理意义是什么。

那其实,Java 中的 LinkedHashMap 已经做了很好的实现。但是,即便面试时可以使用它,也是这么一步步推导出来的,而不是一看到题目就知道用它,那一看就是背答案啊。

有同学问我,如果面试官问我这题做没做过,该怎么回答?

答:实话实说。

真诚在面试、工作中都是很重要的,所以实话实说就好了。但如果面试官没问,就不必说。。。

其实面试官是不 care 你做没做过这道题的,因为大家都刷题,基本都做过,问这个问题没有意义。只要你能把问题分析清楚,讲清楚逻辑,做过了又怎样?很多做过了题的人是讲不清楚的。。。

总结

那我们再总结一下那四点操作:

第一个操作,也就是 get() API,没啥好说的;

二三四,是 put() API,有点小麻烦:

画图的时候边讲边写,每一步都从 high level 到 detail 再到代码,把代码模块化。

  • 比如“Welcome”是要把这个新的信息加入到 HashMap 和 LinkedList 里,那我会用一个单独的 add() method 来写这块内容,那在下面的代码里我取名为 appendHead(),更精准;
  • “踢走老的”这里我也是用一个单独的 remove() method 来写的。

当年我把这图画出来,面试官就没让我写代码了,直接下一题了...

那如果面试官还让你写,就写呗。。。

class LRUCache {
  // HashMap: <key = Question, value = ListNode>
  // LinkedList: <Answer>

  public static class Node {
      int key;
      int val;
      Node next;
      Node prev;
      public Node(int key, int val) {
          this.key = key;
          this.val = val;
      }
  }

  Map<Integer, Node> map = new HashMap<>();
  private Node head;
  private Node tail;
  private int cap;

  public LRUCache(int capacity) {
      cap = capacity;
  }

  public int get(int key) {
      Node node = map.get(key);
      if(node == null) {
          return -1;
      } else {
          int res = node.val;
          remove(node);
          appendHead(node);
          return res;
      }
  }

  public void put(int key, int value) {
      // 先 check 有没有这个 key
      Node node = map.get(key);
      if(node != null) {
          node.val = value;
          // 把这个node放在最前面去
          remove(node);
          appendHead(node);
      } else {
          node = new Node(key, value);
          if(map.size() < cap) {
              appendHead(node);
              map.put(key, node);
          } else {
              // 踢走老的
              map.remove(tail.key);
              remove(tail);
              appendHead(node);
              map.put(key, node);
          }
      }
  }

  private void appendHead(Node node) {
      if(head == null) {
          head = tail = node;
      } else {
          node.next = head;
          head.prev = node;
          head = node;
      }
  }

  private void remove(Node node) {
      // 这里我写的可能不是最 elegant 的,但是是很 readable 的
      if(head == tail) {
          head = tail = null;
      } else {
          if(head == node) {
              head = head.next;
              node.next = null;
          } else if (tail == node) {
              tail = tail.prev;
              tail.next = null;
              node.prev = null;
          } else {
              node.prev.next = node.next;
              node.next.prev = node.prev;
              node.prev = null;
              node.next = null;
          }
      }
  }


}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

总结


那再回到面试上来,为什么很多面试是以算法考察为主的?这样的面试道理何在?算法题面试真的能衡量一个人的工作能力吗?(当然了,对于有些工作经验的人还会考察系统设计方面的内容。)

这是我一直在思考的问题,工作之后愈发觉得,这样的面试真的是有效的。

因为我们需要的是能够去解决未知的问题的能力,知识可能会被遗忘,但是思考问题的方式方法是一直跟随着我们的,也是我们需要不断提高的。那么在基本功扎实的前提下,有正确的方法和思路做指引,nothing is impossible.

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...


查看原文

赞 4 收藏 1 评论 0

小齐本齐 发布了文章 · 9月21日

一文学懂递归和动态规划

前言

大家好,这里是《齐姐聊算法》系列之递归和 DP 问题。

递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对时间空间复杂度的理解和分析。

本文只讲一题,也是几乎所有算法书讲递归的第一题,但力争讲出花来,在这里分享四点不一样的角度,让你有不同的收获。

  • 时空复杂度的详细分析
  • 识别并简化递归过程中的重复运算
  • 披上羊皮的狼
  • 适当炫技助我拿到第一份工作

算法思路

大家都知道,一个方法自己调用自己就是递归,没错,但这只是理解递归的最表层的理解。

那么递归的实质是什么?

答:<span style="color:blue">递归的实质是能够把一个大问题分解成比它小点的问题,然后我们拿到了小问题的解,就可以用小问题的解去构造大问题的解。</span>

那小问题的解是如何得到的?

答:用再小一号的问题的解构造出来的,小到不能再小的时候就是到了零号问题的时候,也就是 base case 了。

那么总结一下递归的三个步骤:

Base case:就是递归的零号问题,也是递归的终点,走到最小的那个问题,能够直接给出结果,不必再往下走了,否则,就会成死循环;

拆解:每一层的问题都要比上一层的小,不断缩小问题的 size,才能从大到小到 base case;

组合:得到了小问题的解,还要知道如何才能构造出大问题的解。

所以每道递归题,我们按照这三个步骤来分析,把这三个问题搞清楚,代码就很容易写了。

斐波那契数列

这题虽是老生常谈了,但相信我这里分享的一定会让你有其他收获。

题目描述

斐波那契数列是一位意大利的数学家,他闲着没事去研究兔子繁殖的过程,研究着就发现,可以写成这么一个序列:1,1,2,3,5,8,13,21… 也就是每个数等于它前两个数之和。那么给你第 n 个数,问 F(n) 是多少。

解析

用数学公式表示很简单:

$$f(n) = f(n-1) + f(n-2)$$

代码也很简单,用我们刚总结的三步:

  • base case: f(0) = 0, f(1) = 1.
  • 分解:f(n-1), f(n-2)
  • 组合:f(n) = f(n-1) + f(n-2)

那么写出来就是:

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        } else if (N == 1) {
            return 1;
        }
        return fib(N-1) + fib(N-2);
    }
}

但是这种解法 Leetcode 给出的速度经验只比 15% 的答案快,因为,它的时间复杂度实在是太高了!

过程分析

这就是我想分享的第一点,如何去分析递归的过程。

首先我们把这颗 Recursion Tree 画出来,比如我们把 F(5) 的递归树画出来:

那实际的执行路线是怎样的?

首先是沿着最左边这条线一路到底:F(5) → F(4) → F(3) → F(2) → F(1),好了终于有个 base case 可以返回 F(1) = 1 了,然后返回到 F(2) 这一层,再往下走,就是 F(0),又触底反弹,回到 F(2),得到 F(2) = 1+0 =1 的结果,把这个结果返回给 F(3),然后再到 F(1),拿到结果后再返回 F(3) 得到 F(3) = 左 + 右 = 2,再把这个结果返上去...

这种方式本质上是由我们计算机的冯诺伊曼体系造就的,目前一个 CPU 一个核在某一时间只能执行一条指令,所以不能 F(3) 和 F(4) 一起进行了,一定是先执行了 F(4) (本代码把 fib(N-1) 放在前面),再去执行 F(3).

我们在 IDE 里 debug 就可以看到栈里面的情况:这里确实是先走的最左边这条线路,一共有 5 层,然后再一层层往上返回。

没看懂的小伙伴可以看视频讲解哦~

完整版视频还请大家移步 B 站,搜索「田小齐」「递归」,即可看到我的视频讲解。

<video data-original="../../2.%20%E5%85%AC%E4%BC%97%E5%8F%B7/5%20Recursion%20-%20Fib/%E5%8E%8B%E6%A0%88%E8%BF%87%E7%A8%8B%E8%AF%A6%E8%A7%A3.MP4"></video>

时间复杂度分析

如何评价一个算法的好坏?

很多问题都有多种解法,毕竟条条大路通罗马。但如何评价每种方法的优劣,我们一般是用大 O 表达式来衡量时间和空间复杂度。

时间复杂度:随着自变量的增长,所需时间的增长情况。

这里大 O 表示的是一个算法在 worst case 的表现情况,这就是我们最关心的,不然春运抢车票的时候系统 hold 不住了,你跟我说这个算法很优秀?

当然还有其他衡量时间和空间的方式,比如

Theta: 描述的是 tight bound
Omega(n): 这个描述的是 best case,最好的情况,没啥意义

<span style="color:blue">这也给我们了些许启发,不要说你平时表现有多好,没有意义;面试衡量的是你在 worst case 的水平;不要说面试没有发挥出你的真实水平,扎心的是那就是我们的真实水平。

那对于这个题来说,时间复杂度是多少呢?

答:因为我们每个节点都走了一遍,所以是把所有节点的时间加起来就是总的时间。

在这里,我们在每个节点上做的事情就是相加求和,是 O(1) 的操作,且每个节点的时间都是一样的,所以:

总时间 = 节点个数 * 每个节点的时间

那就变成了求节点个数的数学题:

在 N = 5 时,

最上面一层有1个节点,
第二层 2 个,
第三层 4 个,
第四层 8 个,
第五层 16 个,如果填满的话,想象成一颗很大的树:)

这里就不要在意这个没填满的地方了,肯定是会有差这么几个 node,但是大 O 表达的时间复杂度我们刚说过了,求的是 worst case.

那么总的节点数就是:
1 + 2 + 4 + 8 + 16

这就是一个等比数列求和了,当然你可以用数学公式来算,但还有个小技巧可以帮助你快速计算:

<span style="color:blue"> 其实前面每一层的节点相加起来的个数都不会超过最后一层的节点的个数,总的节点数最多也就是最后一层节点数 * 2,然后在大 O 的时间复杂度里面常数项也是无所谓的,所以这个总的时间复杂度就是:

<span style="color:blue">

最后一层节点的个数:2^n

空间复杂度分析

一般书上写的空间复杂度是指:

算法运行期间所需占用的所有内存空间

但是在公司里大家常用的,也是面试时问的指的是
Auxiliary space complexity

运行算法时所需占用的额外空间。

<span style="color:blue"> 举例说明区别:比如结果让你输出一个长度为 n 的数组,那么这 O(n) 的空间是不算在算法的空间复杂度里的,因为这个空间是跑不掉的,不是取决于你的算法的。

那空间复杂度怎么分析呢?

我们刚刚说到了冯诺伊曼体系,从图中也很容易看出来,是最左边这条路线占用 stack 的空间最多,一直不断的压栈,也就是从 5 到 4 到 3 到 2 一直压到 1,才到 base case 返回,每个节点占用的空间复杂度是 O(1),所以加起来总的空间复杂度就是 O(n).

我在上面👆的视频里也提到了,不懂的同学往上翻看视频哦~

优化算法

那我们就想了,为什么这么一个简简单单的运算竟然要指数级的时间复杂度?到底是为什么让时间如此之大。

那也不难看出来,在这棵 Recursion Tree 里,有太多的重复计算了。

比如一个 F(2) 在这里都被计算了 3 次,F(3) 被计算了 2 次,每次还都要再重新算,这不就是狗熊掰棒子吗,真的是一把辛酸泪。

那找到了原因之后,为了解决这种重复计算,计算机采用的方法其实和我们人类是一样的:记笔记

对很多职业来说,比如医生、律师、以及我们工程师,为什么越老经验值钱?因为我们见得多积累的多,下次再遇到类似的问题时,能够很快的给出解决方案,哪怕一时解决不了,也避免了一些盲目的试错,我们会站在过去的高度不断进步,而不是每次都从零开始。

回到优化算法上来,那计算机如何记笔记呢?

我们要想求 F(n),无非也就是要
记录 F(0) ~ F(n-1) 的值
那选取一个合适的数据结构来存储就好了。

那这里很明显了,用一个数组来存:

Index012345
F(n)011235

那有了这个 cheat sheet,我们就可以从前到后得到结果了,这样每一个点就只算了一遍,用一个 for loop 就可以写出来,代码也非常简单。

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        }
        if (N== 1) {
            return 1;
        }
        int[] notes = new int[N+1];
        notes[0] = 0;
        notes[1] = 1;
        for(int i = 2; i <= N; i++) {
            notes[i] = notes[i-1] + notes[i-2];
        }
        return notes[N];
    }
}

这个速度就是 100% 了~

但是我们可以看到,空间应该还有优化的余地。

那仔细想想,其实我们记笔记的时候需要记录这么多吗?需要从幼儿园到小学到初中到高中的笔记都留着吗?

那其实每项的计算只取决于它前面的两项,所以只用保留这两个就好了。

那我们可以用一个长度为 2 的数组来计算,或者就用 2 个变量。

更新代码:

class Solution {
    public int fib(int N) {
        int a = 0;
        int b = 1;
        if(N == 0) {
            return a;
        }
        if(N == 1) {
            return b;
        }
        for(int i = 2; i <= N; i++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
}

这样我们就把空间复杂度优化到了 O(1),时间复杂度和用数组记录一样都是 O(n).

这种方法其实就是动态规划Dynamic Programming,写出来的代码非常简单。

<span style="color:blue">那我们比较一下 Recursion 和 DP:

Recursion 是从大到小,层层分解,直到 base case 分解不了了再组合返回上去;
DP 是从小到大,记好笔记,不断进步。

也就是 Recursion + Cache = DP

如何记录这个笔记,如何高效的记笔记,这是 DP 的难点。

有人说 DP 是拿空间换时间,但我不这么认为,这道题就是一个很好的例证。

在用递归解题时,我们可以看到,空间是 O(n) 在栈上的,但是<span style="display:block;color:blue">用 DP 我们可以把空间优化到 O(1),DP 可以做到时间空间的双重优化。</span>

其实呢,斐波那契数列在现实生活中也有很多应用。

比如在我司以及很多大公司里,每个任务要给分值,1分表示大概需要花1天时间完成,然后分值只有1,2,3,5,8这5种,(如果有大于8分的任务,就需要把它 break down 成8分以内的,以便大家在两周内能完成。)
因为任务是永远做不完的而每个人的时间是有限的,所以每次小组会开会,挑出最重要的任务让大家来做,然后每个人根据自己的 available 的天数去 pick up 相应的任务。

披着羊皮的狼

<span style="color:blue">那有同学可能会想,这题这么简单,这都 2020 年了,面试还会考么?

答:真的会。

只是不能以这么直白的方式给你了。

比如很有名的爬楼梯问题:

一个 N 阶的楼梯,每次能走一层或者两层,问一共有多少种走法。

这个题这么想:

站在当前位置,只能是从前一层,或者前两层上来的,所以 f(n) = f(n-1) + f(n-2).

这题是我当年面试时真实被问的,那时我还在写 python,为了炫技,<span style="color:blue">还用了lambda function:

f = lambda n: 1 if n in (1, 2) else f(n-1) + f(n-2)

递归的写法时间复杂度太高,所以又写了一个 for loop 的版本

def fib(n)
  a, b = 1, 1
  for i in range(n-1):
    a, b = b, a+b
  return a 

<span style="color:blue">然后还写了个 caching 的方法:

def cache(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper
@cache
def fibR(n):
    if n==1 or n==2: return 1
    return fibR(n-1) + fibR(n-2)

<span style="color:blue">还顺便和面试官聊了下 tail recursion:

tail recursion 尾递归:就是递归的这句话是整个方法的最后一句话。

那这个有什么特别之处呢?

尾递归的特点就是我们可以很容易的把它转成 iterative 的写法,当然有些智能的编译器会自动帮我们做了(不是说显性的转化,而是在运行时按照 iterative 的方式去运行,实际消耗的空间是 O(1))

那为什么呢?

因为回来的时候不需要 backtrack,递归这里就是最后一步了,不需要再往上一层返值。
def fib(n, a=0, b=1):
    if n==0: return a
      if n==1: return b
    return fib(n-1, b, a+b)

<span style="color:blue">最终,拿出了我的杀手锏:lambda and reduce

fibRe = lambda n: reduce(lambda x, n: [x[1], x[0]+x[1]], range(n), [0, 1])

看到面试官满意的表情后,就开始继续深入的聊了...

所以说,不要以为它简单,同一道题可以用七八种方法来解,分析好每个方法的优缺点,引申到你可以引申的地方,展示自己扎实的基本功,这场面试其实就是你 show off 的机会,这样才能骗过面试官啊~lol

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

前言

大家好,这里是《齐姐聊算法》系列之递归和 DP 问题。

递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对时间空间复杂度的理解和分析。

本文只讲一题,也是几乎所有算法书讲递归的第一题,但力争讲出花来,在这里分享四点不一样的角度,让你有不同的收获。

  • 时空复杂度的详细分析
  • 识别并简化递归过程中的重复运算
  • 披上羊皮的狼
  • 适当炫技助我拿到第一份工作

算法思路

大家都知道,一个方法自己调用自己就是递归,没错,但这只是理解递归的最表层的理解。

那么递归的实质是什么?

答:<span style="color:blue">递归的实质是能够把一个大问题分解成比它小点的问题,然后我们拿到了小问题的解,就可以用小问题的解去构造大问题的解。</span>

那小问题的解是如何得到的?

答:用再小一号的问题的解构造出来的,小到不能再小的时候就是到了零号问题的时候,也就是 base case 了。

那么总结一下递归的三个步骤:

Base case:就是递归的零号问题,也是递归的终点,走到最小的那个问题,能够直接给出结果,不必再往下走了,否则,就会成死循环;

拆解:每一层的问题都要比上一层的小,不断缩小问题的 size,才能从大到小到 base case;

组合:得到了小问题的解,还要知道如何才能构造出大问题的解。

所以每道递归题,我们按照这三个步骤来分析,把这三个问题搞清楚,代码就很容易写了。

斐波那契数列

这题虽是老生常谈了,但相信我这里分享的一定会让你有其他收获。

题目描述

斐波那契数列是一位意大利的数学家,他闲着没事去研究兔子繁殖的过程,研究着就发现,可以写成这么一个序列:1,1,2,3,5,8,13,21… 也就是每个数等于它前两个数之和。那么给你第 n 个数,问 F(n) 是多少。

解析

用数学公式表示很简单:

$$f(n) = f(n-1) + f(n-2)$$

代码也很简单,用我们刚总结的三步:

  • base case: f(0) = 0, f(1) = 1.
  • 分解:f(n-1), f(n-2)
  • 组合:f(n) = f(n-1) + f(n-2)

那么写出来就是:

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        } else if (N == 1) {
            return 1;
        }
        return fib(N-1) + fib(N-2);
    }
}

但是这种解法 Leetcode 给出的速度经验只比 15% 的答案快,因为,它的时间复杂度实在是太高了!

过程分析

这就是我想分享的第一点,如何去分析递归的过程。

首先我们把这颗 Recursion Tree 画出来,比如我们把 F(5) 的递归树画出来:

那实际的执行路线是怎样的?

首先是沿着最左边这条线一路到底:F(5) → F(4) → F(3) → F(2) → F(1),好了终于有个 base case 可以返回 F(1) = 1 了,然后返回到 F(2) 这一层,再往下走,就是 F(0),又触底反弹,回到 F(2),得到 F(2) = 1+0 =1 的结果,把这个结果返回给 F(3),然后再到 F(1),拿到结果后再返回 F(3) 得到 F(3) = 左 + 右 = 2,再把这个结果返上去...

这种方式本质上是由我们计算机的冯诺伊曼体系造就的,目前一个 CPU 一个核在某一时间只能执行一条指令,所以不能 F(3) 和 F(4) 一起进行了,一定是先执行了 F(4) (本代码把 fib(N-1) 放在前面),再去执行 F(3).

我们在 IDE 里 debug 就可以看到栈里面的情况:这里确实是先走的最左边这条线路,一共有 5 层,然后再一层层往上返回。

没看懂的小伙伴可以看视频讲解哦~

完整版视频还请大家移步 B 站,搜索「田小齐」「递归」,即可看到我的视频讲解。

<video data-original="../../2.%20%E5%85%AC%E4%BC%97%E5%8F%B7/5%20Recursion%20-%20Fib/%E5%8E%8B%E6%A0%88%E8%BF%87%E7%A8%8B%E8%AF%A6%E8%A7%A3.MP4"></video>

时间复杂度分析

如何评价一个算法的好坏?

很多问题都有多种解法,毕竟条条大路通罗马。但如何评价每种方法的优劣,我们一般是用大 O 表达式来衡量时间和空间复杂度。

时间复杂度:随着自变量的增长,所需时间的增长情况。

这里大 O 表示的是一个算法在 worst case 的表现情况,这就是我们最关心的,不然春运抢车票的时候系统 hold 不住了,你跟我说这个算法很优秀?

当然还有其他衡量时间和空间的方式,比如

Theta: 描述的是 tight bound
Omega(n): 这个描述的是 best case,最好的情况,没啥意义

<span style="color:blue">这也给我们了些许启发,不要说你平时表现有多好,没有意义;面试衡量的是你在 worst case 的水平;不要说面试没有发挥出你的真实水平,扎心的是那就是我们的真实水平。

那对于这个题来说,时间复杂度是多少呢?

答:因为我们每个节点都走了一遍,所以是把所有节点的时间加起来就是总的时间。

在这里,我们在每个节点上做的事情就是相加求和,是 O(1) 的操作,且每个节点的时间都是一样的,所以:

总时间 = 节点个数 * 每个节点的时间

那就变成了求节点个数的数学题:

在 N = 5 时,

最上面一层有1个节点,
第二层 2 个,
第三层 4 个,
第四层 8 个,
第五层 16 个,如果填满的话,想象成一颗很大的树:)

这里就不要在意这个没填满的地方了,肯定是会有差这么几个 node,但是大 O 表达的时间复杂度我们刚说过了,求的是 worst case.

那么总的节点数就是:
1 + 2 + 4 + 8 + 16

这就是一个等比数列求和了,当然你可以用数学公式来算,但还有个小技巧可以帮助你快速计算:

<span style="color:blue"> 其实前面每一层的节点相加起来的个数都不会超过最后一层的节点的个数,总的节点数最多也就是最后一层节点数 * 2,然后在大 O 的时间复杂度里面常数项也是无所谓的,所以这个总的时间复杂度就是:

<span style="color:blue">

最后一层节点的个数:2^n

空间复杂度分析

一般书上写的空间复杂度是指:

算法运行期间所需占用的所有内存空间

但是在公司里大家常用的,也是面试时问的指的是
Auxiliary space complexity

运行算法时所需占用的额外空间。

<span style="color:blue"> 举例说明区别:比如结果让你输出一个长度为 n 的数组,那么这 O(n) 的空间是不算在算法的空间复杂度里的,因为这个空间是跑不掉的,不是取决于你的算法的。

那空间复杂度怎么分析呢?

我们刚刚说到了冯诺伊曼体系,从图中也很容易看出来,是最左边这条路线占用 stack 的空间最多,一直不断的压栈,也就是从 5 到 4 到 3 到 2 一直压到 1,才到 base case 返回,每个节点占用的空间复杂度是 O(1),所以加起来总的空间复杂度就是 O(n).

我在上面👆的视频里也提到了,不懂的同学往上翻看视频哦~

优化算法

那我们就想了,为什么这么一个简简单单的运算竟然要指数级的时间复杂度?到底是为什么让时间如此之大。

那也不难看出来,在这棵 Recursion Tree 里,有太多的重复计算了。

比如一个 F(2) 在这里都被计算了 3 次,F(3) 被计算了 2 次,每次还都要再重新算,这不就是狗熊掰棒子吗,真的是一把辛酸泪。

那找到了原因之后,为了解决这种重复计算,计算机采用的方法其实和我们人类是一样的:记笔记

对很多职业来说,比如医生、律师、以及我们工程师,为什么越老经验值钱?因为我们见得多积累的多,下次再遇到类似的问题时,能够很快的给出解决方案,哪怕一时解决不了,也避免了一些盲目的试错,我们会站在过去的高度不断进步,而不是每次都从零开始。

回到优化算法上来,那计算机如何记笔记呢?

我们要想求 F(n),无非也就是要
记录 F(0) ~ F(n-1) 的值
那选取一个合适的数据结构来存储就好了。

那这里很明显了,用一个数组来存:

Index012345
F(n)011235

那有了这个 cheat sheet,我们就可以从前到后得到结果了,这样每一个点就只算了一遍,用一个 for loop 就可以写出来,代码也非常简单。

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        }
        if (N== 1) {
            return 1;
        }
        int[] notes = new int[N+1];
        notes[0] = 0;
        notes[1] = 1;
        for(int i = 2; i <= N; i++) {
            notes[i] = notes[i-1] + notes[i-2];
        }
        return notes[N];
    }
}

这个速度就是 100% 了~

但是我们可以看到,空间应该还有优化的余地。

那仔细想想,其实我们记笔记的时候需要记录这么多吗?需要从幼儿园到小学到初中到高中的笔记都留着吗?

那其实每项的计算只取决于它前面的两项,所以只用保留这两个就好了。

那我们可以用一个长度为 2 的数组来计算,或者就用 2 个变量。

更新代码:

class Solution {
    public int fib(int N) {
        int a = 0;
        int b = 1;
        if(N == 0) {
            return a;
        }
        if(N == 1) {
            return b;
        }
        for(int i = 2; i <= N; i++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
}

这样我们就把空间复杂度优化到了 O(1),时间复杂度和用数组记录一样都是 O(n).

这种方法其实就是动态规划Dynamic Programming,写出来的代码非常简单。

<span style="color:blue">那我们比较一下 Recursion 和 DP:

Recursion 是从大到小,层层分解,直到 base case 分解不了了再组合返回上去;
DP 是从小到大,记好笔记,不断进步。

也就是 Recursion + Cache = DP

如何记录这个笔记,如何高效的记笔记,这是 DP 的难点。

有人说 DP 是拿空间换时间,但我不这么认为,这道题就是一个很好的例证。

在用递归解题时,我们可以看到,空间是 O(n) 在栈上的,但是<span style="display:block;color:blue">用 DP 我们可以把空间优化到 O(1),DP 可以做到时间空间的双重优化。</span>

其实呢,斐波那契数列在现实生活中也有很多应用。

比如在我司以及很多大公司里,每个任务要给分值,1分表示大概需要花1天时间完成,然后分值只有1,2,3,5,8这5种,(如果有大于8分的任务,就需要把它 break down 成8分以内的,以便大家在两周内能完成。)
因为任务是永远做不完的而每个人的时间是有限的,所以每次小组会开会,挑出最重要的任务让大家来做,然后每个人根据自己的 available 的天数去 pick up 相应的任务。

披着羊皮的狼

<span style="color:blue">那有同学可能会想,这题这么简单,这都 2020 年了,面试还会考么?

答:真的会。

只是不能以这么直白的方式给你了。

比如很有名的爬楼梯问题:

一个 N 阶的楼梯,每次能走一层或者两层,问一共有多少种走法。

这个题这么想:

站在当前位置,只能是从前一层,或者前两层上来的,所以 f(n) = f(n-1) + f(n-2).

这题是我当年面试时真实被问的,那时我还在写 python,为了炫技,<span style="color:blue">还用了lambda function:

f = lambda n: 1 if n in (1, 2) else f(n-1) + f(n-2)

递归的写法时间复杂度太高,所以又写了一个 for loop 的版本

def fib(n)
  a, b = 1, 1
  for i in range(n-1):
    a, b = b, a+b
  return a 

<span style="color:blue">然后还写了个 caching 的方法:

def cache(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper
@cache
def fibR(n):
    if n==1 or n==2: return 1
    return fibR(n-1) + fibR(n-2)

<span style="color:blue">还顺便和面试官聊了下 tail recursion:

tail recursion 尾递归:就是递归的这句话是整个方法的最后一句话。

那这个有什么特别之处呢?

尾递归的特点就是我们可以很容易的把它转成 iterative 的写法,当然有些智能的编译器会自动帮我们做了(不是说显性的转化,而是在运行时按照 iterative 的方式去运行,实际消耗的空间是 O(1))

那为什么呢?

因为回来的时候不需要 backtrack,递归这里就是最后一步了,不需要再往上一层返值。
def fib(n, a=0, b=1):
    if n==0: return a
      if n==1: return b
    return fib(n-1, b, a+b)

<span style="color:blue">最终,拿出了我的杀手锏:lambda and reduce

fibRe = lambda n: reduce(lambda x, n: [x[1], x[0]+x[1]], range(n), [0, 1])

看到面试官满意的表情后,就开始继续深入的聊了...

所以说,不要以为它简单,同一道题可以用七八种方法来解,分析好每个方法的优缺点,引申到你可以引申的地方,展示自己扎实的基本功,这场面试其实就是你 show off 的机会,这样才能骗过面试官啊~lol

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 15 收藏 10 评论 1

小齐本齐 发布了文章 · 9月18日

一代巨星的陨落!

这里是《齐姐聊大厂》系列的第 6 篇

(前 5 篇见文末)

每周五早上 8 点,与你唠唠大厂的那些事。

小齐说:

2016 年 7 月 25 日,Verizon 最终敲定以 48 亿美金收购雅虎的核心资产,与之前收购的 AOL 合并,成立名为 Oath 的公司,后更名为 Verizon Media。

雅虎的剩余业务更名为 Altaba Inc,CEO - Marissa Mayer 在收购完成之后退出董事会。

作为昔日互联网的巨头,创立于 1994 年的雅虎两年后便在华尔街上市。在那个年代,雅虎的搜索业务无人能及,并且还首创在搜索中插入广告来盈利,这种盈利模式让它在短短几年之内实现了市值的成倍增长。

于是,雅虎开始扩张业务种类,而此时,越来越多的人看到了这个行业。

后来,雅虎的搜索业务被谷歌赶超;分类广告业务输给了 Craigslist;就连拍卖业务也被 eBay 碾压;更有 Facebook 等强大竞争对手,导致其市场份额不断缩小。

从 2007 年开始,雅虎在四年间换了四任 CEO,2012 年 Marissa Mayer 从谷歌离任来到雅虎,但也未能挽救其颓势。

雅虎并不是一个人,曾经的诺基亚、摩托罗拉都是它的好伙伴。

在这个瞬息万变的时代,唯有变化才是不变,这是其魅力所在,也是其残酷所在。

今天我邀请到我的朋友 FrostA,曾在雅虎工作了三年,完整经历了从 Yahoo 到 Oath 到 Verizon Media 的全过程,从第一视角跟大家分享她在雅虎的工作体验。


先吐槽

技术

雅虎现在的技术其实还有一些能拿得出手的,比如说前两年开源的 Vespa,据说当年 M 姐把所有关键组都转移到总部不然就直接砍掉,结果只有 Vespa 坚持在挪威不搬家,M 姐也拿他们没办法。

每年公司内部还有自己的科技论坛会议,去过两次,其实能看到很多有趣的创新的东西。不过想一想我写的那种垃圾都能被选上,好像水平也不怎么高,括弧笑。

只不过我觉得公司内部最大的问题是没有一个强有力的 CTO 去推行很多平台性的东西,没有统一的 ML 平台,没有统一的 Microservice,不是说没有人做,但是推广程度不高,更像是有一两个组在从零建立起整个用户群。

福利

曾经湾区数一数二的食堂现在简直难以下咽。

刚入职那段时间还有每周一次的 sushi time,赶上夏天有实习生的时候呼朋唤友好不热闹。

现在各种大刀阔斧的砍食物,中餐每天就三个菜爱吃不吃,咖喱倒是单独搞了个柜台,队伍还是那么长。

啊对,晚饭没了。

矿泉水砍了,你说是为了保护环境我也算是支持吧。

零食饮料都跟着前 CEO 一起走了,省钱俩字就差写脸上了。

卖大楼

一流企业卖大楼,用了多少年的 HeadQuarter 以后就是 G 家的了,但是早知道要卖你干嘛还折腾了一整年全部重新装修了一遍呢。

改名

中间改叫了一年的 Oath,也跟前 CEO 一起被换了。现在官方名字变成了 Verizon Media,但是还是 Oath Holdings 给你发钱,过海关我都不知道我该说给谁工作,括弧笑*2。

缺钱

在这干了 3 年,晋升的还算快,进来是 SDE1,半年升职到 SDE2,又一年升到 SDE3,到最后总包大概一年能有 180、190K 左右?

但是一个同期的同事,干了一年跳西雅图 A,又一年跳回湾区 G,一问人家 250K,估计还是照顾我感受往少了说。。

401K 干满 3 年才给。

401K 是美国的退休金计划,自己存一部分,公司会给交一部分。

RSU 分三年给。升职的时候画个饼,年终填点渣,这几年攒下来没拿到手的饼大概有 70k,估计不如其他几家一次 refresh。

RSU:Restricted Stock Unit,就是股票。

裁员

从 17 年入职以来公司大裁员三次的样子吧,头两年小裁员也搞了不少,不过最近一年多好像就裁了一次,估计是裁的差不多了吧,括弧笑*3。

离职

裁员带来的直接结果就是大量本来没什么被裁风险的人纷纷主动离职,高层频繁变动很容易给人一种不安感,所以很多排期老哥选择了主动离开。

缺人

裁员+离职我就不重复了,再加上给不出有竞争力的 offer,这两年我面过 30+应届生,看好的无一例外都去了 G。

开源节流加起来,跟我说少了一半的人我都信,刚来的时候起晚了停车位都难找,到现在 11 点上班还能停楼门前,怪不得要卖大楼。

缺人的直接影响就是很多项目没人负责,大量的交接占据了工作的很大一部分,有什么疑问点开 git log 发现 user undefined。

个人发展

缺点说了一堆,不过我还是在这个公司待了 3 年,主要的原因还是我觉得这里对我个人发展有帮助,从几个角度说吧。

晋升

虽然我还是 junior 级别主要靠混日子,不过晋升这种一个萝卜一个坑的事,想要快速升职,要么去一家高速发展的公司能不断产生新的空位,要么就是去一家能不断腾出空位的公司。

因为人才流失,所以公司对于还留在公司的人还算慷慨,身边年长的同事晋升都没有遇到什么太大阻碍,甚至十来个人的组大老板已经成了 senior director,水涨船高我也能跟着升职容易一些。

学习

因为缺人,所以什么项目都能掺一脚。

这几年我从前端做到后端,从大数据做到调参,时不时还跟 TL 讨论一下新系统的架构设计,这种接触到各种不同领域的机会单纯做一颗高薪螺丝钉是遇不到的。

再加上瘦死的骆驼比马大,单说雅虎邮箱现在每天数据量还是上 B 的,跑一个 hadoop 还是有几千个 node 的,而且用起来没什么限制,这种平台也算是有一定的竞争力。

自由度

这点可能跟组有关,我印度老板对我做什么工作基本就是放任,有想法了就去做,想尝试换个领域就安排不同的工作内容,不能说完全没有烦心的工作,不过自主权比较大,可以自己决定很多事情做不做,怎么做。

WLB

WLB: work life balance,以后这个不写注释了哦!

我从最开始 9 点上班到 10 点到 10 点半踩点开早会到 11 点,反正大家都在摸,我稍微摸会鱼好像问题也不大,所以这些年一直没怎么感受到秃头的压力,括弧笑*4。

总的来说,虽然雅虎这些年一直走下坡路,不过如果能找到恰当的机会,我感觉还是很适合一部分人的。


非常感谢 FrostA 的无私分享!行业内对雅虎的评价不一,但凡事都有两面,顺应时代变化,抓住属于自己的机会,为自己做积累,你就是那颗最亮的星~

本文已收录至我的 Github 上:https://github.com/xiaoqi6666/NYCSDE,这个 Github 汇总了我所有的文章和资料,之后也会一直更新和维护。点击阅读原文即可直达,还希望大家帮忙点个 Star,你们的支持和认可,就是我创作的最大动力!

这是《齐姐聊大厂》系列的第 6 篇,如果你喜欢这篇文章,不要忘记点赞哦!也欢迎留言告诉小齐你感兴趣的大厂~

我是小齐,终身学习者,每晚 9 点,自习室里我们不见不散 ❤️

查看原文

赞 1 收藏 0 评论 0

小齐本齐 发布了文章 · 9月17日

拓扑排序就这么回事

前言

大家好,这里是《齐姐聊算法》系列之拓扑排序问题。

Topological sort 又称 Topological order,这个名字有点迷惑性,因为拓扑排序并不是一个纯粹的排序算法,它只是针对某一类图,找到一个可以执行的线性顺序。

这个算法听起来高大上,如今的面试也很爱考,比如当时我在面我司时有整整一轮是基于拓扑排序的设计。

但它其实是一个很好理解的算法,跟着我的思路,让你再也不会忘记她。

有向无环图

刚刚我们提到,拓扑排序只是针对特定的一类图,那么是针对哪类图的呢?

答:Directed acyclic graph (DAG),有向无环图。即:

  1. 这个图的边必须是有方向的;
  2. 图内无环。

那么什么是方向呢?

比如微信好友就是有向的,你加了他好友他可能把你删了你却不知道。。。那这个朋友关系就是单向的。。

什么是环?环是和方向有关的,从一个点出发能回到自己,这是环。

所以下图左边不是环,右边是。

那么如果一个图里有环,比如右图,想执行 1 就要先执行 3,想执行 3 就要先执行 2,想执行 2 就要先执行 1,这成了个死循环,无法找到正确的打开方式,所以找不到它的一个拓扑序。

总结:

  • 如果这个图不是 DAG,那么它是没有拓扑序的;
  • 如果是 DAG,那么它至少有一个拓扑序;
  • 反之,如果它存在一个拓扑序,那么这个图必定是 DGA.

所以这是一个充分必要条件

拓扑排序

那么这么一个图的「拓扑序」是什么意思呢?

我们借用百度百科的这个课程表来说明。

课程代号课程名称先修课程
C1高等数学
C2程序设计基础
C3离散数学C1, C2
C4数据结构C3, C5
C5算法语言C2
C6编译技术C4, C5
C7操作系统C4, C9
C8普通物理C1
C9计算机原理C8

这里有 9 门课程,有些课程是有先修课程的要求的,就是你要先学了「最右侧这一栏要求的这个课」才能再去选「高阶」的课程。

那么这个例子中拓扑排序的意思就是:
就是求解一种可行的顺序,能够让我把所有课都学了。

那怎么做呢?

首先我们可以用来描述它,
图的两个要素是顶点和边
那么在这里:

  • 顶点:每门课
  • 边:起点的课程是终点的课程的先修课

画出来长这个样:

这种图叫 AOV (Activity On Vertex) 网络,在这种图里:

  • 顶点:表示活动;
  • 边:表示活动间的先后关系

**所以一个 AOV 网应该是一个 DAG,即有向无环图,否则某些活动会无法进行。
<span style="display:block;color:orangered;">那么所有活动可以排成一个可行线性序列,这个序列就是拓扑序列。**

那么这个序列的实际意义是:
按照这个顺序,在每个项目开始时,能够保证它的前驱活动都已完成,从而使整个工程顺利进行。

回到我们这个例子中:

  1. 我们一眼可以看出来要先学 C1, C2,因为这两门课没有任何要求嘛,大一的时候就学呗;
  2. 大二就可以学第二行的 C3, C5, C8 了,因为这三门课的先修课程就是 C1, C2,我们都学完了;
  3. 大三可以学第三行的 C4, C9;
  4. 最后一年选剩下的 C6, C7。

这样,我们就把所有课程学完了,也就得到了这个图的一个拓扑排序

注意,有时候拓扑序并不是唯一的,比如在这个例子中,先学 C1 再学 C2,和先 C2 后 C1 都行,都是这个图的正确的拓扑序,但这是两个顺序了。

所以面试的时候要问下面试官,是要求解任意解,还是列出所有解。

我们总结一下,

在这个图里的表示的是一种依赖关系,如果要修下一门课,就要先把前一门课修了。

这和打游戏里一样一样的嘛,要拿到一个道具,就要先做 A 任务,再完成 B 任务,最终终于能到达目的地了。

算法详解

在上面的图里,大家很容易就看出来了它的拓扑序,但当工程越来越庞大时,依赖关系也会变得错综复杂,那就需要用一种系统性的方式方法来求解了。

那么我们回想一下刚刚自己找拓扑序的过程,为什么我们先看上了 C1, C2?

因为它们没有依赖别人啊,
也就是它的入度为 0.

入度:顶点的入度是指「指向该顶点的边」的数量;
出度:顶点的出度是指该顶点指向其他点的边的数量。

所以我们先执行入度为 0 的那些点,
那也就是要记录每个顶点的入度。
因为只有当它的 入度 = 0 的时候,我们才能执行它。

在刚才的例子里,最开始 C1, C2 的入度就是 0,所以我们可以先执行这两个。

那在这个算法里第一步就是得到每个顶点的入度。

Step0: 预处理得到每个点的入度

我们可以用一个 HashMap 来存放这个信息,或者用一个数组会更精巧。

在文中为了方便展示,我就用表格了:

C1C2C3C4C5C6C7C8C9
入度002212211

Step1

拿到了这个之后,就可以执行入度为 0 的这些点了,也就是 C1, C2.

那我们把可以被执行的这些点,放入一个待执行的容器里,这样之后我们一个个的从这个容器里取顶点就好了。

至于这个容器究竟选哪种数据结构,这取决于我们需要做哪些操作,再看哪种数据结构可以为之服务。

那么首先可以把[C1, C2]放入容器中,

然后想想我们需要哪些操作吧!

我们最常做的操作无非就是把点放进来把点拿出去执行了,也就是需要一个 offerpoll 操作比较高效的数据结构,那么 queue 就够用了。

(其他的也行,放进来这个容器里的顶点的地位都是一样的,都是可以执行的,和进来的顺序无关,但何必非得给自己找麻烦呢?一个常规顺序的简简单单的 queue 就够用了。)

然后就需要把某些点拿出去执行了。

【划重点】当我们把 C1 拿出来执行,那这意味这什么?

<span style="display:block;color:blue;">答:意味着「以 C1 为顶点」的「指向其他点」的「边」都消失了,也就是 C1 的出度变成了 0.

如下图,也就是这两条边可以消失了。

step1

那么此时我们就可以更新 C1 所指向的那些点也就是 C3 和 C8入度 了,更新后的数组如下:

C3C4C5C6C7C8C9
入度12122<span style="display:block;color:blue;">01

<span style="display:block;color:blue;">那我们这里看到很关键的一步,C8 的入度变成了 0!

也就意味着 C8 此时没有了任何依赖,可以放到我们的 queue 里等待执行了。

此时我们的 queue 里就是:[C2, C8].

Step2

下一个我们再执行 C2,

Step2

那么 C2 所指向的C3, C5入度-1

更新表格:

C3C4C5C6C7C9
入度<span style="display:block;color:blue;">02<span style="display:block;color:blue;">0221

也就是 C3 和 C5 都没有了任何束缚,可以放进 queue 里执行了。

queue 此时变成:[C8, C3, C5]

Step3

那么下一步我们执行 C8,

Step3

相应的 C8 所指的 C9 的入度-1.
更新表格:

C4C6C7C9
入度222<span style="display:block;color:blue;">0

那么 C9 没有了任何要求,可以放进 queue 里执行了。

queue 此时变成:[C3, C5, C9]

Step4

接下来执行 C3,

Step4

相应的 C3 所指的 C4 的入度-1.
更新表格:

C4C6C7
入度<span style="display:block;color:blue;">122

<span style="display:block;color:blue;">但是 C4 的入度并没有变成 0,所以这一步没有任何点可以加入 queue.

queue 此时变成 [C5, C9]

Step5

再执行 C5,

Step5

那么 C5 所指的 C4 和 C6 的入度- 1.
更新表格:

C4C6C7
入度<span style="display:block;color:blue;">0<span style="display:block;color:blue;">12

这里 C4 的依赖全都消失啦,那么可以把 C4 放进 queue 里了:

queue = [C9, C4]

Step6

然后执行 C9,

Step6

那么 C9 所指的 C7 的入度- 1.

C6C7
入度<span style="display:block;color:blue;">1<span style="display:block;color:blue;">1

这里 C7 的入度并不为 0,还不能加入 queue,

此时 queue = [C4]

Step7

接着执行 C4,

Step7

所以 C4 所指向的 C6 和 C7 的入度-1,
更新表格:

C6C7
入度<span style="display:block;color:blue;">0<span style="display:block;color:blue;">0

C6 和 C7 的入度都变成 0 啦!!把它们放入 queue,继续执行到直到 queue 为空即可。

总结

好了,那我们梳理一下这个算法:

<span style="display:block;color:blue;">数据结构
这里我们的入度表格可以用 map 来存放,关于 map 还有不清楚的同学可以看之前我写的 HashMap 的文章哦~

Map: <key = Vertex, value = 入度>

但实际代码中,我们用一个 int array 来存储也就够了,graph node 可以用数组的 index 来表示,value 就用数组里的数值来表示,这样比 Map 更精巧。

然后用了一个普通的 queue,用来存放可以被执行的那些 node.

<span style="display:block;color:blue;">过程
我们把入度为 0 的那些顶点放入 queue 中,然后通过每次执行 queue 中的顶点,就可以让依赖这个被执行的顶点的那些点的 入度-1,如果有顶点的入度变成了 0,就可以放入 queue 了,直到 queue 为空。

<span style="display:block;color:blue;">细节
这里有几点实现上的细节:

当我们 check 是否有新的顶点的 入度 == 0 时,没必要过一遍整个 map 或者数组,只需要 check 刚刚改动过的就好了。

另一个是如果题目没有给这个图是 DAG 的条件的话,那么有可能是不存在可行解的,那怎么判断呢?很简单的一个方法就是比较一下最后结果中的顶点的个数和图中所有顶点的个数是否相等,或者加个计数器,如果不相等,说明就不存在有效解。所以这个算法也可以用来判断一个图是不是有向无环图

很多题目给的条件可能是给这个图的 edge list,也是表示图的一种常用的方式。那么给的这个 list 就是表示图中的。这里要注意审题哦,看清楚是谁 depends on 谁。其实图的题一般都不会直接给你这个图,而是给一个场景,需要你把它变回一个图。

<span style="display:block;color:blue;">时间复杂度

注意 ⚠️:对于图的时间复杂度分析一定是两个参数,面试的时候很多同学张口就是 O(n)...

对于有 v 个顶点和 e 条边的图来说,

第一步,预处理得到 map 或者 array,需要过一遍所有的边才行,所以是 O(e);

第二步,把 入度 == 0 的点入队出队的操作是 O(v),如果是一个 DAG,那所有的点都需要入队出队一次;

第三步,每次执行一个顶点的时候,要把它指向的那条边消除了,这个总共执行 e 次;

总:O(v + e)

<span style="display:block;color:blue;">空间复杂度

用了一个数组来存所有点的 indegree,之后的 queue 也是最多把所有的点放进去,所以是 O(v).

<span style="display:block;color:blue;">代码

关于这课程排序的问题,Leetcode 上有两道题,一道是 207,问你能否完成所有课程,也就是问拓扑排序是否存在;另一道是 210 题,是让你返回任意一个拓扑顺序,如果不能完成,那就返回一个空 array。

这里我们以 210 这道题来写,更完整也更常考一些。

Leetcode210

这里给的 input 就是我们刚刚说到的 edge list.

Example 1.

Input: 2, [[1,0]]
Output: [0,1]
Explanation: 这里一共 2 门课,1 的先修课程是 0. 所以正确的选课顺序是[0, 1].

Example 2.

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation:这里这个例子画出来如下图

Example 3.

Input: 2, [[1,0],[0,1]]
Output: null
Explanation: 这课没法上了
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        int[] indegree = new int[numCourses];

        // get the indegree for each course
        for(int[] pre : prerequisites) {
            indegree[pre[0]] ++;
        }

        // put courses with indegree == 0 to queue
        Queue<Integer> queue = new ArrayDeque<>();
        for(int i = 0; i < numCourses; i++) {
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // execute the course
        int i = 0;
        while(!queue.isEmpty()) {
            Integer curr = queue.poll();
            res[i++] = curr;

            // remove the pre = curr
            for(int[] pre : prerequisites) {
                if(pre[1] == curr) {
                    indegree[pre[0]] --;
                    if(indegree[pre[0]] == 0) {
                        queue.offer(pre[0]);
                    }
                }
            }
        }

        return i == numCourses ? res : new int[]{};
    }
}

另外,拓扑排序还可以用 DFS - 深度优先搜索 来实现,限于篇幅就不在这里展开了,大家可以参考GeeksforGeeks的这个资料。

实际应用

我们上文已经提到了它的一个 use case,就是选课系统,这也是最常考的题目。

而拓扑排序最重要的应用就是关键路径问题,这个问题对应的是 AOE (Activity on Edge) 网络。

AOE 网络:顶点表示事件,边表示活动,边上的权重来表示活动所需要的时间。
AOV 网络:顶点表示活动,边表示活动之间的依赖关系。

在 AOE 网中,从起点到终点具有最大长度的路径称为关键路径,在关键路径上的活动称为关键活动。AOE 网络一般用来分析一个大项目的工序,分析至少需要花多少时间完成,以及每个活动能有多少机动时间。

具体是怎么应用分析的,大家可以参考这个视频 的 14 分 46 秒,这个例子还是讲的很好的。

其实对于任何一个任务之间有依赖关系的图,都是适用的。

比如 pom 依赖引入 jar 包时,大家有没有想过它是怎么导进来一些你并没有直接引入的 jar 包的?比如你并没有引入 aop 的 jar 包,但它自动出现了,这就是因为你导入的一些包是依赖于 aop 这个 jar 包的,那么 maven 就自动帮你导入了。

其他的实际应用,比如说:

  1. 语音识别系统的预处理;
  2. 管理目标文件之间的依赖关系,就像我刚刚说的 jar 包导入;
  3. 深度学习中的网络结构处理。

如有其他补充,欢迎大家在评论区不吝赐教。

以上就是本文的全部内容了,拓扑排序是非常重要也是非常爱考的一类算法,面试大厂前一定要熟练掌握。

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 0 收藏 0 评论 0

小齐本齐 发布了文章 · 9月16日

必考算法之 Top K 问题

大家好,这里是《齐姐聊算法》系列之 Top K 问题。

Top K 问题是面试中非常常考的算法题。

8

Leetcode 上这两题大同小异,这里以第一题为例。

题意:
给一组词,统计出现频率最高的 k 个。
比如说 “I love leetcode, I love coding” 中频率最高的 2 个就是 I 和 love 了。

有同学觉得这题特别简单,但其实这题只是母题,它可以升级到<span style="color:blue;font-weight:bold;">系统设计</span>层面来问:

在某电商网站上,过去的一小时内卖出的最多的 k 种货物。

我们先看算法层面:

<span style="color:orangered;font-weight:bold;">思路:

统计下所有词的频率,然后按频率排序取最高的前 k 个呗。

<span style="color:orangered;font-weight:bold;">细节:

用 HashMap 存放单词的频率,用 minHeap/maxHeap 来取前 k 个。

<span style="color:orangered;font-weight:bold;">实现:

  1. 建一个 HashMap <key = 单词,value = 出现频率>,遍历整个数组,相应的把这个单词的出现次数 + 1.

    这一步时间复杂度是 O(n).

  2. 用 size = k 的 minHeap 来存放结果,定义好题目中规定的比较顺序
    a. 首先按照出现的频率排序;
    b. 频率相同时,按字母顺序。
  3. 遍历这个 map,如果
    a. minHeap 里面的单词数还不到 k 个的时候就加进去;
    b. 或者遇到更高频的单词就把它替换掉。

<span style="color:orangered;font-weight:bold;">时空复杂度分析:

第一步是 O(n),第三步是 nlog(k),所以加在一起时间复杂度是 O(nlogk).

用了一个额外的 heap 和 map,空间复杂度是 O(n).

代码:

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // Step 1
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            Integer count = map.getOrDefault(word, 0);
            count++;
            map.put(word, count);
        }
        
        // Step 2
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k+1, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
                if(e1.getValue() == e2.getValue()) {
                    return e2.getKey().compareTo(e1.getKey());
                }
                return e1.getValue().compareTo(e2.getValue());
            }
        });
        
        // Step 3
        List<String> res = new ArrayList<>();
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            minHeap.offer(entry);
            if(minHeap.size() > k) {
                minHeap.poll();
            }
        }
        while(!minHeap.isEmpty()) {
            res.add(minHeap.poll().getKey());
        }
        Collections.reverse(res);
        return res;
    }
}

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 1 收藏 1 评论 0

小齐本齐 发布了文章 · 9月15日

有关 HashMap 面试会问的一切

前言

大家好,本篇文章是《齐姐说数据结构》系列的第三篇,更多数据结构和算法的文章已经整理在我的 Github 上了:https://github.com/xiaoqi6666...

HashMap 是无论在工作还是面试中都非常常见常考的数据结构。

比如 Leetcode 第一题 Two Sum 的某种变种的最优解就是需要用到 HashMap 的,高频考题 LRU Cache 是需要用到 LinkedHashMap 的。

HashMap 用起来很简单,底层实现也不复杂,先来看几道常见的面试题吧。相信大家多多少少都能回答上来一点,不清楚的地方就仔细阅读本文啦~这篇文章带你深挖到 HashMap 的老祖宗,保证吊打面试官

  • == 和 equals() 的区别?
  • 为什么重写 equals() 就必须要重写 hashCode()?
  • Hashtable, HashSet 和 HashMap 的区别和联系
  • 处理 hash 冲突有哪些方法?Java 中用的哪一种?为什么?另一种方法你在工作中用过吗?在什么情况下用得多?
  • 徒手实现一个 HashMap 吧

本文分以下章节:

  • Set 和 Map 家族简介
  • HashMap 实现原理
  • 哈希冲突详解
  • HashMap 基本操作
  • 习题 Two Sum
  • 习题 LRU

Set 家族

在讲 Map 之前,我们先来看看 Set。

集合的概念我们初中数学就学过了,就是里面不能有重复元素,这里也是一样。

Set 在 Java 中是一个接口,可以看到它是 java.util 包中的一个集合框架类,具体的实现类有很多:

其中比较常用的有三种:

HashSet: 采用 Hashmap 的 key 来储存元素,主要特点是无序的,基本操作都是 O(1) 的时间复杂度,很快。

LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构,特点就是既拥有了 O(1) 的时间复杂度,又能够保留插入的顺序。

TreeSet: 采用红黑树结构,特点是可以有序,可以用自然排序或者自定义比较器来排序;缺点就是查询速度没有 HashSet 快。

Map 家族

Map 是一个键值对 (Key - Value pairs),其中 key 是不可以重复的,毕竟 set 中的 key 要存在这里面。

那么与 Set 相对应的,Map 也有这三个实现类:

HashMap: 与 HashSet 对应,也是无序的,O(1)。

LinkedHashMap: 这是一个「HashMap + 双向链表」的结构,落脚点是 HashMap,所以既拥有 HashMap 的所有特性还能有顺序。

TreeMap: 是有序的,本质是用二叉搜索树来实现的。

HashMap 实现原理

对于 HashMap 中的每个 key,首先通过 hash function 计算出一个 hash 值,这个hash值就代表了在 buckets 里的编号,而 buckets 实际上是用数组来实现的,所以把这个数值模上数组的长度得到它在数组的 index,就这样把它放在了数组里。

那么这里有几个问题:

如果不同的元素算出了相同的哈希值,那么该怎么存放呢?

答:这就是哈希碰撞,即多个 key 对应了同一个桶。

HashMap 中是如何保证元素的唯一性的呢?即相同的元素会不会算出不同的哈希值呢?

答:通过 hashCode()equals() 方法来保证元素的唯一性。

如果 pairs 太多,buckets 太少怎么破?

答:Rehasing. 也就是碰撞太多的时候,会把数组扩容至两倍(默认)。所以这样虽然 hash 值没有变,但是因为数组的长度变了,所以算出来的 index 就变了,就会被分配到不同的位置上了,就不用挤在一起了,小伙伴们我们江湖再见~

那什么时候会 rehashing 呢?也就是怎么衡量桶里是不是足够拥挤要扩容了呢?

答:load factor. 即用 pair 的数量除以 buckets 的数量,也就是平均每个桶里装几对。Java 中默认值是 0.75f,如果超过了这个值就会 rehashing.

关于 hashCode() 和 equals()

如果 key 的 hashCode() 值相同,那么有可能是要发生 hash collision 了,也有可能是真的遇到了另一个自己。那么如何判断呢?继续用 equals() 来比较。

也就是说,

hashCode() 决定了 key 放在这个桶里的编号,也就是在数组里的 index;

equals() 是用来比较两个 object 是否相同的。

那么该如何回答这道<span style="color:black;font-weight:bold;">经典面试题</span>:

<span style="color:blue;font-weight:bold;">为什么重写 equals() 方法,一定要重写 hashCode() 呢?

答:首先我们有一个假设:任何两个 object 的 hashCode 都是不同的。

那么在这个条件下,有两个 object 是相等的,那如果不重写 hashCode(),算出来的哈希值都不一样,就会去到不同的 buckets 了,就迷失在茫茫人海中了,再也无法相认,就和 equals() 条件矛盾了,证毕。

撒花~~🎉🎉🎉

接下来我们再对这两个方法一探究竟:

其实 hashCode() 和 equals() 方法都是在 Object class 这个老祖宗里定义的,Object 是所有 Java 中的 class 的鼻祖,默认都是有的,甩不掉的。

那既然是白给的,我们先来看看大礼包里有什么,谷歌 Object 的 Oracle 文档:

所以这些方法都是可以直接拿来用的呢~

回到 hashCode() 和 equals(),那么如果这个新的 class 里没有重写 (override) 这两个方法,就是默认继承 Object class 里的定义了。

那我们点进去来看看 equals() 是怎么定义的:

记笔记:

equals() 方法就是比较这两个 references 是否指向了同一个 object.

嗯???你在逗我吗??那岂不是和 == 一样了??

补充:
我们常用的比较大小的符号之 ==
如果是 primitive type,那么 == 就是比较数值的大小;
如果是 reference type,那么就比较的是这两个 reference 是否指向了同一个 object。

再补充:
Java 的数据类型可以分为两种:
Primitive type 有且仅有8种:byte, short, int, long, float, double, char, boolean.
其他都是 Reference type.
所以虽然 Java 声称 “Everything is object”,但是还是有非 object 数据类型的存在的。

我不信,我要去源码里看看它是怎么实现的。

哈,还真是的,绕了这么半天,equals() 就是用 == 来实现的!

那为什么还弄出来这么个方法呢?

<span style="color:blue;font-weight:bold;">答:为了让你 override~

比如一般来说我们比较字符串就是想比较这两个字符串的内容的,那么:

str1 = “tianxiaoqi”;
str2 =  new String(“tianxiaoqi”);

str1 == str2; // return false
str1.equals(str2); // return true 

因为 String 里是重写了 equals() 方法的:

老祖宗留给你就是让你自己用的,如果你不用,那人家也提供了默认的方法,也是够意思了。

好了,我们再去看 hashCode() 的介绍:

那至于 hashCode() 返回的究竟是什么,和本文关联不太大,有兴趣的同学可以看参考这篇文章参考文章"),结论就是:

返回的并不一定是对象的(虚拟)内存地址,具体取决于运行时库和JVM的具体实现。

但无论是怎么实现的,都需要遵循文档上的约定,也就是对不同的 object 会返回唯一的哈希值

### 哈希冲突详解

一般来说哈希冲突有两大类解决方式

  1. Separate chaining
  2. Open addressing

Java 中采用的是第一种 Separate chaining,即在发生碰撞的那个桶后面再加一条“链”来存储,那么这个“链”使用的具体是什么数据结构,不同的版本稍有不同:

在 JDK1.6 和 1.7 中,是用链表存储的,这样如果碰撞很多的话,就变成了在链表上的查找,worst case 就是 O(n);

在 JDK 1.8 进行了优化,当链表长度较大时(超过 8),会采用红黑树来存储,这样大大提高了查找效率。

(话说,这个还真的喜欢考,已经在多次面试中被问过了,还有面试官问为什么是超过“8”才用红黑树🤔)

第二种方法 open addressing 也是非常重要的思想,因为在真实的分布式系统里,有很多地方会用到 hash 的思想但又不适合用 seprate chaining

这种方法是顺序查找,如果这个桶里已经被占了,那就按照“某种方式”继续找下一个没有被占的桶,直到找到第一个的。

空的

如图所示,John Smith 和 Sandra Dee 发生了哈希冲突,都被计算到 152 号桶,于是 Sandra 就去了下一个空位 - 153 号桶,当然也会对之后的 key 发生影响:Ted Baker 计算结果本应是放在 153 号的,但鉴于已经被 Sandra 占了,就只能再去下一个空位了,所以到了 154 号。

这种方式叫做 Linear probing 线性探查,就像上图所示,一个个的顺着找下一个空位。当然还有其他的方式,比如去找平方数,或者 Double hashing.

HashMap 基本操作

每种数据结构的基本操作都无外乎<span style="color:orangered;font-weight:bold;">增删改查</span>这四种,具体到 HashMap 来说,

  • 增:put(K key, V value)
  • 删:remove(Object key)
  • 改:还是用的 put(K key, V value)
  • 查:get(Object key) / containsKey(Object key)

细心的同学可能发现了,为什么有些 key 的类型是 Object,有些是 K 呢?这还不是因为 equals()...

这是因为,在 get/remove 的时候,不一定是用的同一个 object。

还记得那个 str1 和 str2 都是田小齐的例子吗?那比如我先 put(str1, value),然后用 get(str2) 的时候,也是想要到 tianxiaoqi 对应的 value 呀!不能因为我换了身衣服就不认得我了呀!所以在 get/remove 的时候并没有很限制 key 的类型,方便另一个自己相认。

其实这些 API 的操作流程大同小异,我们以最复杂的 put(K key, V value) 来讲:

  1. 首先要拿到 array 中要放的位置的 index
  • 怎么找 index 呢,这里我们可以单独用 getIndex() method 来做这件事;
  • 具体怎么做,就是通过 hash function 算出来的值,模上数组的长度;
  1. 那拿到了这个位置的 Node,我们开始 traverse 这个 LinkedList,这就是在链表上的操作了,
  • 如果找的到,就更新一下 value;
  • 如果没找到,就把它放在链表上,可以放头上,也可以放尾上,一般我喜欢放头上,因为新加入的元素用到的概率总是大一些,但并不影响时间复杂度。

代码如下:

  public V put(K key, V value) {
    int index = getIndex(key);
    Node<K, V> node = array[index];
    Node<K, V> head = node; 
    while (node != null) {
        // 原来有这个 key,仅更新值
        if (checkEquals(key, node)) {
            V preValue = node.value;
            node.value = value;
            return preValue;
        }
        node = node.next;
    }
    // 原来没有这个 key,新加这个 node
    Node<K, V> newNode = new Node(key, value); 
    newNode.next = head;
    array[index] = newNode;
    return null;
}

至于更多的细节比如加一些 rehashing 啊,load factor 啊,大家可以参考源码。

读完源码大家可以做做 Leetcode 706 题练手,so easy~

### 与 Hashtable 的区别

这是一个年龄暴露贴,HashMap 与 Hashtable 的关系,就像 ArrayList 与 Vector,以及 StringBuilder 与 StringBuffer。

Hashtable 是早期 JDK 提供的接口,HashMap 是新版的;
它们之间最显著的区别,就是 Hashtable 是线程安全的,HashMap 并非线程安全。

这是因为 Java 5.0 之后允许数据结构不考虑线程安全的问题,因为实际工作中我们发现没有必要在数据结构的层面上上锁,加锁和放锁在系统中是有开销的,内部锁有时候会成为程序的瓶颈。

所以 HashMap, ArrayList, StringBuilder 不再考虑线程安全的问题,性能提升了很多,当然,线程安全问题也就转移给我们程序员了。

另外一个区别就是:HashMap 允许 key 中有 null 值,Hashtable 是不允许的。这样的好处就是可以给一个默认值。

在算法面试中,有关 HashMap 的算法题也很常见,比如有名的 Top K 问题,还有 LRU Cache 问题,这两道题都是非常高频的考题,之后也会讲到,还请大家继续关注我吧!


如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 21 收藏 15 评论 0

小齐本齐 发布了文章 · 9月14日

多线程必考的「生产者 - 消费者」模型,看齐姐这篇文章就够了

生产者 - 消费者模型 Producer-consumer problem 是一个非常经典的多线程并发协作的模型,在分布式系统里非常常见。也是面试中无论中美大厂都非常爱考的一个问题,对应届生问的要少一些,但是对于有工作经验的工程师来说,非常爱考。

这个问题有非常多的版本和解决方式,在本文我重点是和大家壹齐理清思路,由浅入深的思考问题,保证大家看完了都能有所收获。

问题背景

简单来说,这个模型是由两类线程构成:

  • 生产者线程:“生产”产品,并把产品放到一个队列里;
  • 消费者线程:“消费”产品。

有了这个队列,生产者就只需要关注生产,而不用管消费者的消费行为,更不用等待消费者线程执行完;消费者也只管消费,不用管生产者是怎么生产的,更不用等着生产者生产。

所以该模型实现了生产者和消费者之间的解藕异步

什么是异步呢?

比如说你和你女朋友打电话,就得等她接了电话你们才能说话,这是同步。

但是如果你跟她发微信,并不需要等她回复,她也不需要立刻回复,而是等她有空了再回,这就是异步。

但是呢,生产者和消费者之间也不能完全没有联系的。

  • 如果队列里的产品已经满了,生产者就不能继续生产;
  • 如果队列里的产品从无到有,生产者就得通知一下消费者,告诉它可以来消费了;
  • 如果队列里已经没有产品了,消费者也无法继续消费;
  • 如果队列里的产品从满到不满,消费者也得去通知下生产者,说你可以来生产了。

所以它们之间还需要有协作,最经典的就是使用 Object 类里自带的 wait()notify() 或者 notifyAll() 的消息通知机制。

上述描述中的等着,其实就是用 wait() 来实现的;

通知,就是 notify() 或者 notifyAll()

那么基于这种消息通知机制,我们还能够平衡生产者和消费者之间的速度差异

如果生产者的生产速度很慢,但是消费者消费的很快,就像是我们每月工资就发两次,但是每天都要花钱,也就是 1:15.

那么我们就需要调整生产者(发工资)为 15 个线程,消费者保持 1 个线程,这样是不是很爽~

**总结下该模型的三大优点:
解藕,异步,平衡速度差异。**

wait()/notify()

接下来我们需要重点看下这个通知机制。

wait()notify() 都是 Java 中的 Object 类自带的方法,可以用来实现线程间的通信。

上一节讲的 11 个 APIs 里我也提到了它,我们这里再展开讲一下。

wait() 方法是用来让当前线程等待,直到有别的线程调用 notify() 将它唤醒,或者我们可以设定一个时间让它自动苏醒。

调用该方法之前,线程必须要获得该对象的对象监视器锁,也就是只能用在加锁的方法下。

而调用该方法之后,当前线程会释放锁。(提示:这里很重要,也是下文代码中用 while 而非 if 的原因。)

notify() 方法只能通知一个线程,如果多个线程在等待,那就唤醒任意一个。

notifyAll() 方法是可以唤醒所有等待线程,然后加入同步队列。

这里我们用到了 2 个队列:

  • 同步队列:对应于我们上一节讲的线程状态中的 Runnable,也就是线程准备就绪,就等着抢资源了。
  • 等待队列:对应于我们上一节讲的线程状态中的 Waiting,也就是等待状态。

这里需要注意,从等待状态线程无法直接进入 Q2,而是要先重新加入同步队列,再次等待拿锁,拿到了锁才能进去 Q2;一旦出了 Q2,锁就丢了。

Q2 里,其实只有一个线程,因为这里我们必须要加锁才能进行操作。

实现

这里我首先建了一个简单的 Product 类,用来表示生产和消费的产品,大家可以自行添加更多的 fields

public class Product  {
    private String name;

    public Product(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

主函数里我设定了两类线程,并且这里选择用普通的 ArrayDeque 来实现 Queue,更简单的方式是直接用 Java 中的 BlockingQueue 来实现。

BlockingQueue 是阻塞队列,它有一系列的方法可以让线程实现自动阻塞,常用的 BlockingQueue 有很多,后面会单独出一篇文章来讲。

这里为了更好的理解并发协同的这个过程,我们先自己处理。

public class Test {
    public static void main(String[] args) {
        Queue<Product> queue = new ArrayDeque<>();

        for (int i = 0; i < 100; i++) {
            new Thread(new Producer(queue, 100)).start();
            new Thread(new Consumer(queue, 100)).start();
        }
    }
}

然后就是 ProducerConsumer 了。

public class Producer implements Runnable{
    private Queue<Product> queue;
    private int maxCapacity;

    public Producer(Queue queue, int maxCapacity) {
        this.queue = queue;
        this.maxCapacity = maxCapacity;
    }

    @Override
    public void run() {
        synchronized (queue) {
            while (queue.size() == maxCapacity) { //一定要用 while,而不是 if,下文解释
                try {
                    System.out.println("生产者" + Thread.currentThread().getName() + "等待中... Queue 已达到最大容量,无法生产");
                    wait();
                    System.out.println("生产者" + Thread.currentThread().getName() + "退出等待");
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            if (queue.size() == 0) { //队列里的产品从无到有,需要通知在等待的消费者
                queue.notifyAll();
            }
            Random random = new Random();
            Integer i = random.nextInt();
            queue.offer(new Product("产品"  + i.toString()));
            System.out.println("生产者" + Thread.currentThread().getName() + "生产了产品:" + i.toString());
        }
    }
}

其实它的主逻辑很简单,我这里为了方便演示加了很多打印语句才显得有点复杂。

我们把主要逻辑拎出来看:

 public void run() {
        synchronized (queue) {
            while (queue.size() == maxCapacity) { //一定要用 while,而不是 if,下文解释
                try {
                    wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            if (queue.size() == 0) {
                queue.notifyAll();
            }
            queue.offer(new Product("产品"  + i.toString()));
        }
    }
}

这里有 3 块内容,再对照这个过程来看:

  1. 生产者线程拿到锁后,其实就是进入了 Q2 阶段。首先检查队列是否容量已满,如果满了,那就要去 Q3 等待;
  2. 如果不满,先检查一下队列原本是否为空,如果原来是空的,那就需要通知消费者;
  3. 最后生产产品。

这里有个问题,为什么只能用 while 而不是 if

其实在这一小段,生产者线程经历了几个过程:

  1. 如果队列已满,它就没法生产,那也不能占着位置不做事,所以要把锁让出来,去 Q3 - 等待队列 等着;
  2. 在等待队列里被唤醒之后,不能直接夺过锁来,而是要先加入 Q1 - 同步队列 等待资源;
  3. 一旦抢到资源,关门上锁,才能来到 Q2 继续执行 wait() 之后的活,但是,此时这个队列有可能又满了,所以退出 wait() 之后,还需要再次检查 queue.size() == maxCapacity 这个条件,所以要用 while

那么为什么可能又满了呢?

因为线程没有一直拿着锁,在被唤醒之后,到拿到锁之间的这段时间里,有可能其他的生产者线程先拿到了锁进行了生产,所以队列又经历了一个从不满到满的过程。

总结:在使用线程的等待通知机制时,一般都要在 while 循环中调用 wait() 方法。

消费者线程是完全对称的,我们来看代码。

public class Consumer implements Runnable{
    private Queue<Product> queue;
    private int maxCapacity;

    public Consumer(Queue queue, int maxCapacity) {
        this.queue = queue;
        this.maxCapacity = maxCapacity;
    }

    @Override
    public void run() {
        synchronized (queue) {
            while (queue.isEmpty()) {
                try {
                    System.out.println("消费者" + Thread.currentThread().getName() + "等待中... Queue 已缺货,无法消费");
                    wait();
                    System.out.println("消费者" + Thread.currentThread().getName() + "退出等待");
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            if (queue.size() == maxCapacity) {
                queue.notifyAll();
            }

            Product product = queue.poll();
            System.out.println("消费者" + Thread.currentThread().getName() + "消费了:" + product.getName());
        }
    }
}

结果如下:

小结

生产者 - 消费者问题是面试中经常会遇到的题目,本文首先讲了该模型的三大优点:解藕,异步,平衡速度差异,然后讲解了等待/通知的消息机制以及在该模型中的应用,最后进行了代码实现。

文中所有代码已经放到了我的 Github 上:https://github.com/xiaoqi6666/NYCSDE

这个 Github 汇总了我所有的文章和资料,之后也会一直更新和维护,还希望大家帮忙点个 Star,你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

查看原文

赞 4 收藏 3 评论 0