ARTS 第11周 LeetCode 200 Number of Islands | Page Cache | 面试中的PUA

casmo澎湃哥 · · 450 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

ARTS

ARTS 是陈浩(网名左耳朵耗子)在极客时间专栏里发起的一个活动,目的是通过分享的方式来坚持学习。

每人每周写一个 ARTS:Algorithm 是一道算法题,Review 是读一篇英文文章,Technique/Tips 是分享一个小技术,Share 是分享一个观点。

本周内容

本周的 ARTS 你将看到:

  1. LeetCode 200 Number of Islands 看起来是求连通域,实际上却在扫雷?
  2. Page Cache 到底是什么?
  3. 你是否在面试中遭遇过 PUA ?

Algorithm

本周要讲的是 LeetCode 200 Number of Islands. 这是一道求「连通域」的题目,即求被 0 包围的 1 的区域有多少个。

一个需要注意的点就是,遍历整个矩阵是无法避免的,而一个「岛屿」可能包含多个 1,因此如何避免一个岛屿被重复的计算呢?一种简单的办法就是找到一个岛屿之后就将它的全部节点标记成 0. 这样就可以避免岛屿被重复计算。

那么如何把一个已经找到的岛屿全部标记为 0 呢?最简答的方式就是 DFS, 发现某个点是 1 之后,对这个点的「上下左右」进行 DFS,知道找不到 1 为止。

func numIslands(grid [][]byte) int {
    var ans int
    if len(grid) == 0 {
        return ans
    }
    nc, nr := len(grid), len(grid[0])
    var dfs func(c, r int)
    // 通过深度优先遍历,将同一个岛全部置 0
    dfs = func(c, r int) {
        grid[c][r] = '0'
        if c > 0 && grid[c-1][r] == '1' {
            dfs(c-1, r)
        }
        if c < nc-1 && grid[c+1][r] == '1' {
            dfs(c+1, r)
        }
        if r > 0 && grid[c][r-1] == '1' {
            dfs(c, r-1)
        }
        if r < nr-1 && grid[c][r+1] == '1' {
            dfs(c, r+1)
        }
        return
    }

    // 开始扫雷!
    for c := 0; c < nc; c++ {
        for r := 0; r < nr; r++ {
            if grid[c][r] == '1' {
                ans++
                dfs(c, r)
            }
        }
    }
    return ans
}

Review 文章推荐

本周看了一些 Page Cache 相关的内容,当然「科普」类型的居多,比如下面这篇Page Cache, the Affair Between Memory and Files.

当使用 free 命令查看系统内存使用情况时,一般会得到 6 列数据:
total used free shared buffers cached.

这里我们暂时只关心最后两列,也就是 buffers 和 cached. buffers 代表直接读写块设备(block device)所使用的缓存页,cached 代表普通文件数据所占用的缓存页。

其实当我们谈论缓存时,实际上需要考虑三部分。他们是: global_page_state(NR_FILE_PAGES) total_swapcache_pages i.bufferram.

global_page_state(NR_FILE_PAGES) 顾名思义代表缓存页的总数。

total_swapcache_pages 指的是:没有关联任何文件的内存页,比如正在运行的代码通过 malloc() 申请的内存页,如果上述的内存页需要被换页时,那么这些内存页中的数据将被写入到 Swap Cache. Swap Cache 会关联一个或多个输出设备,比如裸盘或者文件。

i.bufferram 就是 free 命令倒数第二列 buffers.

而 free 的最后一列 cached 可以通过计算公式 global_page_state(NR_FILE_PAGES) – total_swapcache_pages – i.bufferram 得到。

Tip 编程技巧

啥是技巧?

Share 灵光一闪

PUA 本意是指专门通过某些「手段」搭讪女性的男性,因为这些「手段」中经常使用一些「打压」或者叫「贬低」方式来「驯化」对方,因此 PUA 在这两年逐渐成为人人喊打的一个群体。并且 PUA 这个词本身,也慢慢变得更加普适,甚至变成了网络流行语,泛指故意贬低别人的行为。甚至有时候会当做动词来用,比如「我在面试中被 PUA 了」。

最近这段时间尝试参加了几个面试。我必须承认,我在知识积累上还存在欠缺,无论是广度还是深度上。这可能导致我因为能力不足无法通过一些面试,但是我也能判断出一些面试官的「好坏」,即面试官是否对面试做了「适当」的准备。

很明显地,在有那么一两次面试中,面试官显然是没有做「适当」准备的。快速判断出这类面试官的方式就是,看他是否能对你的答案进行点评,并且是否能根据你的答案进行更深度的挖掘,找到你知识储备的边界。如果一个面试官对他所问的问题没有深入的了解,或者没有主管的认识,那么他就只能通过你的答案「内容之外」的东西来做判断。比如你是否用了一些不确定的语气词,或者你本身表达的语气等等,或者说这种面试官实在考「感觉」来做判断。

如果你也在面试中遇到了,只是否定你的能力,但是不对他的否定依据具体解释的情况。强烈建议直接反问面试官:是否可以指出具体哪个问题的答案没有达到你的要求以及为什么?当然,如果这个面试官真的是靠感觉来判断的话,他这个时候很可能会想办法拒绝正面回答这个问题。这个时候你可以选择硬刚到底,一定要面试官说出来,到底哪个问题的答案有问题。也可以选择放弃挣扎,因为无论刚还是怂,最终的结果都是浪费一个小时。

本周阅读列表

  • 极客时间 MySQL实战45讲
    09 | 普通索引和唯一索引,应该怎么选择?
  • Page Cache, the Affair Between Memory and Files
  • Go Context 曹春晖
    cancelCtx 类型都会持有一个自己的 channel 专门用来做关闭通知,并且也会持有所有 children 的 cancel 方法,用来关闭所有 children 的 done channel. 这最终会形成一种树形结构。
    这样做的好处就是,避免所有的 ctx 都是用同一个 Done() 函数,因为使用同一个 Done() 意味着大家竞争同一把锁。
  • FREE命令显示的BUFFERS与CACHED的区别
    介绍 free 命令的最后两列 bufferscached 分别代表什么。

有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:casmo澎湃哥

查看原文:ARTS 第11周 LeetCode 200 Number of Islands | Page Cache | 面试中的PUA

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

450 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传