【四火】 使用树莓派和 Plex 架设照片服务

我用手机拍了很多照片,平时都保存在一台 Windows 台式机上,这台机器硬盘空间大,主要干两个事情,一个是我打游戏,一个就是存放多媒体数据(主要是照片)。有时候我需要它提供照片服务,以方便家人使用各种媒体终端(手机、电视盒子等)阅览,因此我使用 Plex 折腾了一下,但是由于台式机噪音等等的关系,不适合长期开机,因此当时那个方案还是残缺的。

现在打算彻底解决这个问题。大致总结一下,以下是我的主要的几个需求:

  • 照片服务要能够长期保持在线,私用可以方便地查看照片。开机不能有明显的噪音和功耗问题。
  • 我的照片经常是在 Windows 下进行处理的,因此需要很方便地同步到照片服务器。当然,我也会同步几个重要文件夹以作备份只用。
  • 私用,不愿意上传公有云。

最近树莓派比较火,因此我花了几十刀买了个第四代,想用它来满足上面的需求。

安装树莓派

这一步没有什么特别的,从 4 代开始,风扇显得更为重要,但是接针脚的时候,选择 1-6,而不是 4-6,因为 1 号针脚是 3V3,电压低一些,散热能力是弱一些,但风扇噪音也小一些,适合长期开机。考虑到我们的实际需求,这个够用了。

配置树莓派

配置 SSH

打开 SSH:

sudo raspi-config

但这样还不够,需要修改 /etc/ssh/sshd_config 添加:

IPQoS cs0 cs0

之后重启一下 ssh 服务:

sudo service ssh restart

还可以按照我在这篇文章中介绍的办法配置密钥访问,不过是私用,必要性不那么强。

关闭自动休眠

既然用作服务器,肯定不能自动休眠。

sudo apt-get install vim
sudo vim /etc/lightdm/lightdm.conf

添加如下:

xserver-command=X -s 0 -dpms

重启:

sudo reboot

安装 Plex

这一篇 PiMyLifeUp 上的教程很不错,我基本是照着做的。准备工作:

sudo apt-get install apt-transport-https
curl https://downloads.plex.tv/plex-keys/PlexSign.key | sudo apt-key add -
echo deb https://downloads.plex.tv/repo/deb public main | sudo tee /etc/apt/sources.list.d/plexmediaserver.list
sudo apt-get update

安装 Plex:

sudo apt-get install plexmediaserver

配置 Windows 主机

配置同步工具

Windows 机是我的一部分媒体文件的数据源,因此需要经常从 Windows 机同步数据到树莓派服务器。

一种方法是使用 Cygwin + rsync:

安装 Cygwin,这是一个可以在 Windows 下使用常见 Linux 命令的工具。基本上,默认选项即可,但是 rsync 一定要安装:

安装完成以后,Windows 下的磁盘全部被列在/cygdrive 下面。

但是我研究到一半的时候,发现了一个更好用的工具——Acrosync

第一次可以压缩并使用 scp 来传输文件,因为这样效率会更高,但以后就要通过上面的工具来同步了。

值得一提的是,如果空间不够,可以使用 du 这样的命令来查看罪魁祸首,不过我使用的参数因为 Linux 版本的关系,和我以往熟悉的比起来有点不同:

sudo du -s * | sort -nr | head

大功告成

在树莓派机器上安装 Plex 完毕后,在 Windows 下的浏览器中访问 http://192.168.0.28:32400/web 应该能看到 Plex 界面了。

之后,在各种终端上安装 Plex 应用,就可以很舒服地浏览照片了。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/3cx7HXz

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 从链表存在环的问题说起

有这样一个经典的算法题,说是一个单向链表,它内部可能存在环,也可能不存在,用怎样的方法,可以检测出,这个链表是否存在环。下图即是这个形成环的示意,如果单向链表的尾部,指向了链表中的一个节点,而不是指向空,那就构成环了。

接着的一个问题是,怎么检测出这个链表是否有环?

看到这个问题,也许你会觉得,太简单了,但是这个问题只是一个引子。在 《求第 K 个数的问题》一文中,我从简入深,逐步展开,把这 “第 K 个数” 的一系列问题翻了个底朝天。我想关于这个链表成环问题,我也利用类似的思路,看看我是不是也能把这一个问题前前后后讲清楚。

判断单向链表是否成环

在进一步思考怎样判断这个成环的问题以前,先考虑一件事情,如果成环,有没有可能成一个以上的环?

从图示上看,似乎说得通,可事实上却是不可能的,因为 M 点需要有两个后继节点,一个用于构成该处的环,一个用于指向 N 的方向,这显然对于一般我们说的单向链表来说,是不可能做到的。

那么,怎么检测单向链表是否成环呢?

网上能见到的最普遍的解决方法就是双指针,一快一慢,从链表头部开始,快的每次走两步,慢的一次走一步,交替进行,直到二者相遇或快指针抵达链表尾部。如果相遇说明存在环。

不过,这是一个巧妙的方法,是一个时间复杂度在 O(n)、空间复杂度在 O(1) 的好方法,却不是唯一的方法。还有一个思路是,用某种方式记录下走过的节点,如果再次遇到了,就说明成环了。这种方法只需要一个指针,且不会重复遍历走过了的节点,但缺点是存在记录走过节点的开销:

  • 如果链表节点允许使用某变量标记状态(例如 visited 这样的布尔值),当然可以,且不需要额外的空间复杂度;
  • 如果不允许,可以额外使用一个 HashSet 来记录节点,如果存在过,就找到节点了,这种方式的空间复杂度是 O(n)。

再回到那个一快一慢的双指针问题上,有一些基本的问题需要搞清楚。

一快一慢的双指针,在链表成环的情况下,它们一定会遇到吗,有没有可能恰好错过呢?

不会错过,一定会相遇。我们分两种情况考虑:

  • 一种情况是快指针恰好落后慢指针一个身位,那么显然慢指针之后的那个位置,就是它们下一个回合碰面的位置;
  • 另一种情况是快指针落后更多,那么快指针会慢慢赶上来,因为每一个回合快指针走两步,而慢指针走一步,因此每一个回合二者都可以缩短长度为 1 的距离,直到前面说到的只差一个身位的情况出现。

寻找环入口

那么,下一个自然的问题是,怎样找到那个从单向链表进入环的节点(环入口)?

乍一看这个问题,可能很难找到一个高效的解决方法。我们先退一步,仔细分析一下刚才判断成环的步骤,这里面利用了一个事实,如果链表成环,那么快慢指针一定会相遇。那么一个很自然的问题是,它们会在哪里相遇?

首先,它们肯定在环上相遇,因为直线部分 SN 不可能出现 “追上” 的现象。那么,假设它们相遇的点为 P:

  • 对于快指针来说,从起点 S 走到 P 点,假如说绕了 m 圈,环周长为 p,那么一共走了 SN + mp + NP,其中 NP 为最后一圈从 N 逆时针走到 P 的距离。
  • 而对于慢指针来说,从 S 走到 P 点,一定只绕了不到一圈,也就是一共走了 SN + NP 的距离。

这里有个问题,为什么慢指针从 S 走到 P 点,一定只绕了不到一圈?

因为对于慢指针来说,在 “运气最背” 的情况下,就是它刚抵达 N 点的时候,快指针恰好已经路过 N 了,因此在 N 没有相遇。那么按照快指针两倍于慢指针速度的情况来说,慢指针一圈之内,也就是快指针两圈之内一定可以发生 “赶上并超过”,那么也就一定会发生 “相遇”(由于前面的结论,它们不会错过)。因此,这种情况下,相遇的时候,慢指针一定还没有绕足一圈。

好,由于我们知道在 P 点相遇的时候,快指针实际走了慢指针两倍的距离,于是得到:

SN + mp +NP = 2 * (SN + NP)

所以,我们得到:

mp = SN + NP

这意味着什么?这意味着因为 SN+NP 是环周长的倍数,也就意味着在快慢指针相遇在 P 点的时候,如果这个慢指针继续走 SN 的距离,不管这个 SN 实际会绕多少圈,一定会最终停到 N 点

我们虽然还是不知道这个 SN 有多长,但是我们在快慢指针相遇在 P 点的时候,把快指针撤回起点,并且给了快指针一个新指令——你和慢指针一样,每次走一步。这样,慢指针从 P 点开始,逆时针向 N 逼近;快指针从 S 点开始,也以同样的速率向 N 逼近。等它们相遇的时候,恰好就是 N 点,也就是环入口。同时,也获知了 SN 的长度。

计算环周长

如果环入口准确定位了,那么环周长也自然不成问题了。

从环入口开始计数,直到若干步后,重新回到环入口。知道了环周长,根据前面获知的 SN,也就知道了 NP(从环入口 N 逆时针遍历到快慢指针相遇点 P)的距离。

判断链表相交

链表相交,指的是两个不同的链表,链表头不同,但是链表尾部却相同。如图所示:

其中,一个链表从头部 S 开始,另一个从头部 T 开始,二者相交在节点 N,最后共同收尾于 E。

怎样判断链表是否相交,如果是,又怎样找到相交的节点 N?

根据前面寻找环入口问题的启示,如果 SN 的长度等于 TN,那么一个指针从 S 开始,另一个从 T 开始,一样的速率前进,相交的地方就是 N。

但是 SN 和 TN 并不一定相等。

不过也没关系,先对于链表 S-N-E,遍历一遍,得到长度 l1;再对于链表 T-N-E,遍历一遍,得到长度 l2,对于二者中长度较长的一个,让这个指针单独先走一段(以下图为例,从 S 走到 Q),走的这段长度恰好为 l1 和 l2 的差值,把这段差值给抹平。这样一来,QN 就等于 TN 了,这样两个指针就可以同样速率往后前进了,相遇的 N 点就是相交的节点;如果一直不相遇,那就是没有相交。

链表相交和链表成环一起出现

都很简单是不是?有了前面的铺垫,下面来讨论最复杂的问题。

假如说,链表成环和链表相交一起出现,即分别有两个链表,它们可能成环,也可能相交,还可能既成环、又相交。现在,怎样判断它们是否成环,如果成环,环入口在哪里?是否相交,如果相交,相交点又在哪里?

看起来似乎问题一下子复杂了很多,可是仔细观察一下这两个问题,它们的地位不是均等的——

  • 成环的判断,并不依赖于相交的判断。换言之,无论两个链表是否相交,都可以利用前面所述的成环判断,和环入口的计算方式求得。
  • 可是相交的判断却依赖于成环的判断。换言之,要求相交的点需要知道链表的长度,而一旦链表成环了,这个长度就不再能用通用的方法来求解了。

因此,先判断链表是否成环,并且分别求出这两个链表的环入口(如果成环的话),之后再考虑链表相交的问题。

接着,关于成环和相交,有如下的结论:

  • 如果这两个链表,一个成环,而另一个不成环,那么它们二者肯定不相交。这个结论是显然的,因为相交,意味着这个环是共用的,那么自然不可能一个成环,而另一个不成环了。
  • 如果这两个链表都不成环,那么问题退化为前面讲的相交问题。
  • 如果这两个链表都成环,那么问题就比较有意思了,下面我们按照相交点出现的位置来分别讨论。

这种情况下,我们把环入口的点视作两个链表的尾部,然后可以用前面所述的算法求得相交的点。

如果在遍历到环入口以前,找到了两个链表相交的节点,那么我们遇到了情况一,相交的节点先于成环的节点出现

反之,如果遍历到环入口时,依然没有发现相交的节点,那么存在下面所述的情况二和情况三:

情况二,成环且不相交,相当于两个独立的带环链表

情况三,环入口和相交的节点一起出现

有没有可能有情况四,即先出现环入口,再出现相交的节点?

不可能。因为前面已经介绍了,相交就意味着一旦有环,这个环就是两个链表共用的,因此这个环入口一旦出现,就意味着一个链表连上了另一个链表的环,也就意味着相交点也出现了。因此,这种情况下二者是一起出现的,不可能出现环入口早于相交节点的情况。

那么现在的问题是,怎样区分情况二和情况三?

既然两个环入口都找到了,那么以任意一个环入口作为起点,开始遍历,绕环一周,如果期间遇到了另一个环入口,说明是情况三,否则则是情况二。

好,这个问题就讨论到这里。你也可以看到,如果单独拿出最后一个问题来,这是一个有着相当复杂度的问题。不过如果逐步深入进来的话,应该就好很多。

记得在差不多快要十年前了,我 “莫名其妙” 地参加了微软的面试,而电话面试问的题目就是本文一开始的链表成环判断的问题。由于对外企面试的玩法一无所知,我被虐得体无完肤。现在看起来这实在是一个太过普通的问题,但当时的我对于算法的认识是非常浅的,也没有给出一个非常好的解决办法。但是从那一天开始,我才真正算是逐步开始接触并学习算法,因此这篇文章,也算对它小小的纪念。

最后,我想说明的是,在分析上面这些问题的时候,我没有写一点代码。我觉得,这样的纯算法问题,只要思路清楚了,代码基本不是什么问题。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/3dzZcfr

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 哎,写代码的时间真的越来越少了……

还记得在读书的时候,就对程序员有种坐在电脑前疯狂敲代码的刻板印象。工作以后,逐渐理解了软件工程师的工作到底是怎么样的,可是写代码,作为软件工程师最重要的本职工作,还是占据了相当比重的时间。在面试别人的时候,也经常被问到这样的问题——“平均你每天有多少时间花在写代码上?”,这个问题看似简单,却能反映出一个问题,软件工程师,能否有足够的时间专注在最本职工作——写代码上。毫无疑问,我完全理解这样的问题,并且,我也一直以来想保持着自己一个 “纯粹” 程序员的身份。我觉得我的职业通道也是一条纯粹的技术人的道路,因而写代码,是一个如同每天吃饭喝水一样的基本操作。

可是,随着职业生涯的进展,特别是近半年来的一系列变化,我已经明显感受到,这已经发生了变化,曾经的理所应当不再是理所应当。这个变化会带来什么,除去不断的思考,时间会告诉我更多。

团队的变化

在建立初期,OCI 更偏向于招纳更有经验的工程师,因为那个时候 “打地基”、“搭框架” 的工作潜在的影响力,和犯错的可能更为巨大,这样的工作不只是云服务本身的建设,还包括团队和流程体系的打磨。但是逐渐地,随着团队的扩张,招人的策略也发生了明显的变化:

  • 更多的初级职位,更多地吸纳经验较少的工程师,特别是毕业生;
  • 对于高级别的职位,需求量减少,要求的标准相对而言可能有所提高。

其实这也没有什么难以理解的,现在无论是技术人还是管理人,不管是 IC(Individual Contributor)岗还是 M(Manager)岗,大家都对级别和对应的能力和贡献的期望愈发清晰。换言之,就是很明确什么样的工作,交给什么样能力的人去做。这样一来,大多数团队对具备不同能力和经验的软件工程师的需求,也变成了塔状,即经验较少的工程师占较大(60% 以上)的比重。于是,在能够达成目的的基础上,使用这样的模式,可以更好地控制团队的薪酬成本,同时,不同的工程师也可以得到相对合适的挑战。

另一方面,团队负责的项目的规模还在逐渐扩大。团队重新划分过几次,如今我们也肯定是一个全栈式团队(对全栈式团队有疑惑的可以参见我在专栏中的解读),而团队拥有的产品里面,既有数据中心的数据服务,有分布式工作流引擎,还有内部使用的可视化工具网站,并且可以说是既有平台,又有业务。因此对于大部分计算机相关专业毕业的软件工程师,都可以在我们团队找到感兴趣的方向。(题外话,目前由于新冠病毒造成的影响,OCI 的招聘暂停,但是预计在数周后会逐步恢复,对我们团队感兴趣的可以和我联系,不过工作地点只有西雅图。)

这三个产品可以说每一个所对应的最大挑战都不相同,但是配合起来,大的目标是一致的,就是为数据中心,特别是新建数据中心服务,既包括流程自动化,又包括数据存取和展示。

我自己的变化

回想工作最初的几年,特性和功能开发是时间花费最主要的地方,也是最多的 “写代码” 的原因。如今,这件事情肯定已经跌出前三了。

这半年来,我自身的角色也发生了比较大的变化,现在除去一如既往地负责单个产品本身的主要项目,还需要牵线那些各个产品负责的子团队协作来完成的工作。而在项目和团队中实际做的事情,也有了明显变化。总的来说,下面这些事情,时间占用出现了大幅度的上升:

产品或特性的规划

早些年我的理解,对于产品或特性的规划,应该是 TPM 或者产品经理这样的角色来完成的,但是其实这是不准确的。事实上,一方面,有很多工作确实是需要有足够技术背景的人去完成;而另一方面,本身对于多数项目来说这样的角色已经很模糊了,一个不深入理解业务和产品的 IC?不可能的。

对于我们团队来说,TPM 能够提供这样三个方面的帮助:业务、项目和客户。但是,有许多产品或特性的规划,基本上这三个都不相关,完全是工程师的活儿。比如说分布式工作流引擎,业务线和技术线是可以分得比较清楚的:下面的平台本身是业务无关的,而在其之上跑着的的业务工作流却相反。因此,对于其中技术层面的规划设计,也包括将业务怎样落地梳理清楚,只有工程师才能完成。

技术架构

这部分其实接近于我在读书时期对于架构师狭隘的理解。

事实上,我了解到,对于很多真正参与这方面工作的人来说,真正的纯技术架构工作,占比并不会非常大。这一方面是由于,并没有那么多产品长期处于 “初创期” 或者 “转型期”,需要大量的架构工作;另一方面,则是因为一切的技术架构都是建立在业务和需求清晰的基础之上,而做到这一基础已经需要巨大的时间精力投入了。

值得一提的是,这样的工作需要一些考察和探索,比如做技术选型和快速原型。有时候也会涉及一部分编码。总的来说,这其实是我比较喜欢的事情。

管理、沟通和协调

这部分我描述得很笼统,并且有一点像管理岗的工作了。或多或少,这是一个 IC 不可避免的职责。理想状况下研发经理理应承担更多这方面的工作,但是我们的团队人手方面,这样的角色数量不足够,因而 IC 需要更多地承担这方面的工作。当然,即便能做到理想状况,沟通和协调于我而言,依然会占据相当的比重。

对于我们团队而言,偏重技术方面的需求比较多,因此需要软件工程师更多的参与。事实上,我们每一个产品/子团队都有 lead,他们都会主导或重度参与每一个 Sprint 的任务规划。这也再一次印证了,对于 IC 来说,随着职业生涯的发展,角色定位就是会越来越 “模糊”。

Mentoring

在我们团队,目前工作经验较少的工程师比较多,因此 mentoring 是一件比较重要的事情(除此之外,这个状况也是对于 dev manager 需求比较强烈的原因之一)。当然,这部分时间开销,也可以归纳到上面的 “管理、沟通和协调” 当中去。

招聘

上面说的是团队内的时间开销,而在跨团队的 OCI 层面,有这样两项内容花费了显著的时间:一个是设计评审,另一个就是招聘。而对工程师来说,这件事基本围绕面试展开。对于这个话题,鉴于之前已经说过几次了(比如这一篇这一篇),在此就不展开了。

对于角色上的变化,我依然在逐步适应中,寻找最适合自己的方式。而对于写代码这个事情,时间确实是越来越少了,不知道一个合适的解决方法是什么?当然,我并不想去狭隘和片面地追求编码时间,但是我知道,编码是一件常练常新的基本功。在工作中,到底应该怎样更有效地分配时间,平衡包括编码在内的各种各样的事情,希望我可以很快把这个问题考虑清楚……

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/358H6y4

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 那些做了一半的项目

最近有一个项目做了一半不做了,准确地说是由于某些原因,项目需要别的团队来接手了,于是我想随便聊聊这个话题。我猜想,“项目做一半撒手”,这应该是一个很常见的现象,因为这样的事情无论大厂小厂,在软件的世界里不断上演。具体来说,有这样几种典型的情况:

  • 业务变动、组织调整,工作重心变了,项目做了一半直接砍掉,或者无限期停工。这大概是最常见的一种情形。
  • 由于前期的调研、设计的严重问题,或是市场等变化过于剧烈,项目做不下去了,静悄悄地黄了。
  • 项目还做,但是转交给某个其它的团队,这是我这一次遇到的情形。项目还存在,只不过所属关系已经发生变更。

文档和隐性成本

无论哪一种,有一点是毫无疑问的,那就是资源投入的浪费,无论是软件还是硬件。即便不砍掉,暂停一段时间,再恢复的时候,要捡起曾经的项目,一样需要一定的成本。而项目要转交给其它团队,软件的交接成本也相当可观。其实这没有什么奇怪的,这是软件的本质所决定的。具体来说,软件开发,特别是上规模的软件开发,就意味着大量的 “隐性成本”。

从项目管理的角度来说,我们当然希望规范而且具体,或者说,大家都照章办事,项目设计可以纸面化,事无巨细地把 “为什么要这样做”,和 “‘这样做’ 是 ‘怎样做’ 的” 这样的信息都落地成文字交代清楚。可是你我程序员都知道,这是遗憾到不可能发生的事情。我在中国的大厂待过,也在北美的大厂待过,有个别经历的团队和项目甚至被内部外部视作典范,可是客观地说,文档依然缺失,而且不是缺失一点,而是大量地缺失,再好的项目也是如此。

其实,这并不是什么不可理喻的事情,相反,如果一个一定规模的软件项目,文档清清楚楚,把项目事项和设计细节都交代得清清楚楚,我反而觉得这个项目有着猫腻。因为代码和文档永远有着显著而不可调和的矛盾。为什么呢?因为对于软件工程师来说,一个且只有一个真正的、准确的数据来源(Single Source of Truth),是值得推崇的最佳实践。这样的指导思想是根植于他们脑海中的,一个凡是对 Engineering Excellence 有着追求的程序员,一定会把它放在相当重要的位置。而在多数情况下,文档和代码就是两个数据来源,且无法被统一,但是你我都知道,真正工作的一定是代码,代码才是真正的 source of truth,文档只能成为不断过时的那一个。

我知道一定会有声音说,难道不能及时更新文档吗?比方说,代码逻辑修改了,修改的工程师也负责更新文档。没错,但这过于理想化了,而且,就好像软件的世界里一致性和可用性经常是难以调和的矛盾一样,文档的细致程度,和保持准确性的能力,也一样是难以调和的:文档越是细致,就约难以被及时更新,也就越容易成为过时的文档。文档的更新,不但涉及到工作量的问题,它本身也不符合很多工程师基于代码的思维习惯,因为它的读者有了变化,而且叙述的方式也有了变化;再者,真正在业务中直接生效的,也是代码,文档相应地,总是显得那么间接。

对于大多数工程师来说,特别是某些踏入职场时间并不长的工程师来说,文档的地位要更低一些。就好像 “talk is cheap, show me the code” 已经被不可思议地滥用一样,他们对于代码有着过度的狂热。这原本不是什么坏事,软件工程师总是要立足的代码的,可是,软件工程所谓工程,它一定是一个复杂的结合体,代码只能是其中一部分,有时甚至只是一小部分。随着时间和阅历的增加,越发觉得合适的文档在软件工程中的价值,比方说,就在几年前,关于文档我的一点思考记录在这里,现在其实也已经有了更新。

再回到隐性成本的话题上来。已经说了,在文档缺失或过时的情况下,程序员需要去理解需求,并阅读代码来理解前前后后整个故事,这里面的时间成本和试错成本可想而知,可退一步说,哪怕真的文档齐全,要把这些东西消化掉,也依然需要大量的时间。我们都说程序员是一个终生学习的职业,而每一个项目,就是一个可观测的学习的单元。

是勇气还是荒唐?

这样的决定很多时候并不容易做出。我经历过的多数情况,都来自自上而下的决策。有时候部门调整(reorg),结果一些项目的重要性就发生变更,直接砍掉了。而甚至有时候整个部门或团队都砍掉了,我在亚马逊的时候就经历了这么一回,一个原本负责商品在欧洲内各个国家之间方便流通的团队就这样直接砍掉了,当时作为团队里的一份子,我获得了几个 “下家” 团队的选项。也就是说,工程师重新回归资源池,重新分配归属团队。

但也经历过自下而上的,做过的某个内部应用,本来也是摸着石头过河,第一个版本做出交付了,却发现可用性还是比较差,具体说就是流程还是过于苛刻和冗长,而这个问题又不是一个比较容易解决的问题,很难把它继续推广开去,因此这个项目就烂在半途中了。虽说不能说项目砍掉了,但已经低优先级、无限期搁置了,也就和砍掉没有什么太大区别了。

多数时候,这样的损失并不只有纸面上能看到的 “浪费” 那么简单。除了上面所说的隐性成本,还有对团队士气的打击。但是,这里面有一个值得玩味的话题,当一个团队全身心地、毫无保留地投身奉献于一个项目的时候,这里的风险就很容易不可控了。有一位团队经理给下属画饼的时候说过,“你要把 xxx 项目当做你自己的孩子一样”,无疑这对于传递 ownership 的精神,是一个很形象的比喻,可是项目可能会黄,到时候该怎么收场呢?因此我觉得这不是一个特别职业的表达。

最后,回想起来,这种 “做了一半的项目” 还真是挺常见的。非常遗憾,可对于一个大型的组织来说,回头是岸,及时止损,通常可不是坏事。这样的决定无疑需要勇气,更糟的结果是继续这个项目,决策下的越晚损失越大。软件工程似乎就是这样一个无完美解的难题,处处充满了看似可以避免的弯路和糟糕实践,可是换个项目重来一遍的时候,还是一样有这样那样的问题。这有点像是人生,大道理我们都懂,可还是过不好这一生。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/2VpffFj

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 写在在家办公四周之时

几年前我曾经写过一点对于 “在家办公” 的思考,后来又写了一点,但是从来都没有想到过,长期的在家办公如今已经不是一个可选项,而是一个必选项了。

应该说,我从来都不是一个频繁在家办公的支持者,我是说,在家办公这样的互联网公司特有的 “福利” 当然是好的,但是 “频繁” 在家办公对于团队、项目,甚至个人职业成长等等各方面来说,都不是一件好事。我记得在刚加入亚马逊的时候,我听说亚马逊给了一位工程师这样一个 offer——允许一个月之内四分之三的时间远程办公。当时我觉得这件事情还是挺不可思议的,因为像曾经的 37signals 这样的小公司当然容易做到,但是长期和频繁地在家办公却不是大型互联网公司能玩得转的。

现在整个情况都发生变化了,由于新冠疫情,我们被迫在家办公,或者说,全公司绝大多数人都只能选择在家办公了,而且这件事情目前为止还似乎在漆黑的隧道里,还没有看到头。

在家办公的好处

虽然一般情况下,我更希望到公司去办公,而不是在家,但是不可否认在家办公是有很多好处的。

首先,在家办公会让自己更自由。开某些会的时候,可以躺在床上说话,一边说一边闭目休息(比如某些 1 on 1 沟通会);脖子酸了可以趴一会儿;家里有需要帮助和处理的事情也可以很方便地离开一会儿去处理。

其次,在家办公省掉了通勤的时间。不用考虑通勤的时间消耗,就意味着可以把闹铃设到一个更晚的时间,每天可以用于自己支配的时间更充裕。

最后,在家办公也能减少一些打扰。没有人来直接打扰你,这可以算一个原因,但这一条是有争议的,因为既然你在工作,你需要 “在线”,那么你的 Slack 很可能就不会消停……

在家办公的挑战

对于团队来说,面对面沟通和合作所带来的的凝聚力,是在家办公所无法带来的。想象一下,和你团队里的兄弟姐妹做一次 pair coding/review,或者是坐下来喝杯咖啡,再或者打局乒乓球,在 Happy Hour 时间聊一下。现在这些基本上都没有了,有的只有生硬和冷冰冰的一个又一个工作上的会议。

对于项目来说,地理位置上的密切合作,所带来的的沟通高效率,也是在家办公所无法带来的。现在大家似乎都慢慢习惯了对这些远程沟通工具的使用,比如 Zoom 电话会议,可是依然,很多会议还会面临着诸多远程沟通才会有的问题,比如会前调试设备,会中时不时会有杂七杂八的声音,会有人掉线。直接沟通无疑是最高效的,Zoom 这样的工具可以让沟通得以进行,但是看不到手势,看不到表情,连板书也不那么自然,还是损失了很多沟通的信息。

对个人职业发展来说,在家办公也失去了很多能力锻炼的机会。比方说,英语能力本来就不够强大的情况下,面对面的沟通可以化简掉很多的问题,可是电话沟通就会对听说能力要求直接上了一个很大的台阶,保证沟通中信息的传达变成了一件很有挑战性的事情。对我个人来说,已经在西雅图工作好几年了,因此这不算是一个大问题,但是我知道身边有很多初入职场的工程师,英文能力还较为生疏,沟通就更可能成为一个问题。

在家办公的一点技巧

接着聊一点我们可以做的,能够改善在家办公之弊端的措施。

硬件方面,显然,如今的在家办公不是一个 10 分钟的事情,也不是一个一两个钟头的事情,而是长时间,比方说,一天 7、8 个小时都需要持续发生的事情,是一个不能够轻易将就的事情。因此让自己在家办公时自己的身体尽量舒适就显得很有意义。对我来说,我不需要大的显示器,也不需要 laptop 有多高端的配置,但是,人体工学桌椅是很有帮助的,我可以坐一会,站一会。脖子不容易酸,也不容易疲劳。

环境方面,尽可能保证一个安静的房间,是一个很有助益的因素。除此以外,在家的诱惑太多,干扰太多,一个降噪耳机可能能够帮助排除干扰。我有时候也会捧着笔记本电脑,临时地挪到另外的一个更加安静的房间,去开完电话会议。

沟通的技巧方面,我觉得在重要的会议前,简单地罗列一些会议的安排和要点是非常有帮助的,这可能并非特定针对于在家办公的场景,但毫无疑问在家办公让其变得更为重要。开会的时候,有了这样的提纲,就可以专注于要解决的问题,而讨论的时候,也因为有了要点和上下文,效率更高。

最后,还是希望疫情快过去吧。在家呆得已经发霉了,以往生活中喜欢做的事情,比如旅行、打球,或者是看电影,似乎这些不管什么都无法正常进行了。Social distancing 已经让本来就在疏远的人际,越来越远了。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/2JqK1YQ

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 技术面试中,什么样的问题才是好问题?

其实很久以前就想谈一谈这个话题了,但是最近才有了足够的动机。因为从最近参加的很多 debrief 来看,我认为身边大多数的软件工程师面试中,在通过技术问题来考察候选人这方面,很多都做得不够好。比方说,我看到对于一些经验丰富的软件工程师候选人的面试,一些面试官依然是草率地扔出一道算法题让做了事,并且认为能不能够比较清晰完整地将代码写出来,是工程师级别裁定的最重要的标准。而这样的做法我认为是非常不妥的。

首先,我要明确的是,这个问题,指的是技术面试中俗称的 “主要问题”,具体来说,就是面试官会拿出一个问题和候选人讨论,并通过由此开始双方的互相沟通和问题发散来达到考察的目的,因此,这个 “问题”,从某种角度说,更像一个 “话题”。这个过程通常在每轮面试中会持续几十分钟(如果你对这种面试方式感兴趣,你可以看一下这个简单的介绍)。下面的讨论,都是建立在这种面试风格和方式之上的。

其次,作为一个 disclaimer,我想说,以下内容来自于我的认识,并且是针对于技术面试这一个狭窄范围内的认识,自然带有主观的倾向性和认知的局限性,它并不是来自任何公司或组织的标准。

好,下面我就来尝试把这个问题讲清楚、讲透彻。我认为这并不是一件容易的事情,因此如果你对其有不同的看法,欢迎和我一起讨论。

典型案例

我先来举这样一个典型的例子,这里面包含了若干个值得商榷的方面,你可以看看是不是似曾相识:

在和候选人谈论完项目和经历以后,面试还有 40 分钟,于是面试官问:你能否实现一个 LRU 队列?

于是候选人想了一下,就开始做题了,也就是在白板上大写特写,于是面试官也就开始忙自己的事儿了。等到 40 分钟后,候选人写了一白板,但是显然,他在这过程中遇到了一些困难,最后虽然实现了,但是代码写得有些复杂,也遗漏了两、三个重要的 corner case。

于是面试之后,面试官在评语中写道,“候选人能力一般,算法题实现起来磕磕绊绊,最后的代码偏臃肿,而且有明显的 bug”。

在往下阅读以前,请你想一想,这样的面试形式有哪些值得商榷的地方?

技术面试的目的

好,我先卖个关子,先不回答上面的问题,而是先谈一谈,对于软件工程师候选人来说,我们为什么要进行这样的技术面试。事实上,有很多考察项,完全不需要技术面试这样麻烦的途径,就可以很容易、很高效地实现;而下面我说的这些方面,这些对于软件工程师来说至关重要的方面,技术面试却是合理考察的唯一可行途径。

技术能力方面

通常不同轮次的面试,会考察不同的技术点,这个对于不同的团队和职位,是不一样的。

举例来说,对于某业务平台团队的一个高级工程师的职位,五轮面试中,一轮考察项目和经验,一轮考察系统设计,两轮考察具体问题的解决,特别包括算法和数据结构,还有一轮考察面向对象设计等其它内容,这其中,后三轮都包括白板编码的考察。

对于一个有经验的工程师候选人来说,我认为这就是一个比较立体、综合,也是一种比较合理的技术考察点的划分方式。并且,这五轮中有四轮都会花费大量的时间,通过我今天将谈到的技术问题,来对候选人进行技术能力方面的评估。这里,有这样几个非常常见的技术方面的考察项:

  1. 分析问题,整理需求的能力。问题在一开始可能很模糊,但是优秀的且有经验的工程师可以识别出核心的诉求来,这个 “识别” 的能力,下文我还会详述。这里的诉求可能有多个,但是考虑到时间的关系,面试过程中往往只会从某个角度覆盖其中一两个。
  2. 根据需求来设计系统的能力。这里既包括功能性需求,又包括非功能性需求,前者是必须要涉及到的,但是后者也经常也放在一起考量。其实这一点可大可小,它未必一定指系统设计中,功能是否得到实现,并且这个过程中,可能会涉及到系统的扩展性、可用性、一致性等等方面。
  3. 将核心逻辑实现的能力。如今,考察比重容易被高估的算法和数据结构就大体上属于这一部分。它也有功能和非功能的两个角度——功能上算法能否实现需求,非功能上算法是否具备足够的性能,编码是否遵循最佳实践,代码是否具备良好的可扩展性等等。而编码能力,指的是在思路达成一致以后,核心逻辑能不能落到纸面(代码)上。毕竟,“空谈误国,实战兴邦”。
  4. 经验和其它工程能力。这部分相对更为灵活。比如对测试能力的考察,即可以做怎样的测试来实现对于功能需求和非功能需求正确性的保证。对于特定的团队和项目来说,有时候会特别专注于特定的技术能力,比如前端的团队,是需要考察前端的基础技能的。

考虑到时间和覆盖面、覆盖深度的权衡,上面这四点有时候不能在一轮面试中完全覆盖,往往也会包括三点。比如,系统设计的面试可以着重覆盖 1、2、4 点,而编码为主的面试可以着重覆盖 1、3、4 点。

非技术能力方面

和技术能力考察所不同的是,非技术能力考察在不同面试官中的特异性更大,换言之,每个人的角度和标准都可能不相同。但我觉得下面这几条是特别重要,因而必须要覆盖到的:

  1. 沟通合作的能力。如果不计时间成本,最理想的面试是什么?其实就是一起工作。工作中才会有足够多必要的沟通,无论是正面的品质还是负面的问题都会无所遁形。可是面试的时间有限,我们没有办法实现真正的工作氛围,但依然可以模拟工作中一起考察、分析和解决问题的过程,而这个过程,就是要通过 “沟通” 串起来的。沟通是一个大的话题,具体的考察项有很多,比如,能不能接受建议?能不能讨论想法?有些候选人一旦进入自己的思考模式就听不进别的话了,于是一个点要反复强调几遍;而有的则是缺少 backbone,稍微追问一下,也不思考,就立马改变主意。
  2. 热情和兴趣。热情和兴趣的影响是巨大的,都说兴趣是最好的老师,这部分是很难 “教出来” 的。对于初级工程师来说更是如此。热情和兴趣不但会影响到他/她自己的未来发展,也会影响到整个团队的氛围。
  3. 学习能力。学习能力很大程度决定了候选人在新的岗位上进步的潜力。同样的基础和基本的问题解决能力,有的候选人能够 “一点就透”,触类旁通,这在一定程度上就反映了学习的能力。毫无疑问,软件工程师每天都在面对新问题,入职以后就会发现,不止问题是新的,代码是新的,类库是新的,工具是新的,在成熟到能够有一定产出之前,这一步一定是学习。

技术能力和非技术能力,哪个更占主导?事实上,这二者都很重要,并且二者各自又具备不同的特点。当然相对来说,非技术能力更加难以提高,因而这方面的问题要更加引起重视。比方说,要让一个对于软件领域缺乏热情和兴趣的候选人,在入职以后改头换面,是几乎不可能的一件事情。

其它方面

上面说的是技术面试中对于 “能力” 的考察。其实,还有一些考察项,严格来说并不能算是 “能力”,因此我就没有归类在上面,也不是本文的重点,但这并不是说它们不重要。

比如,候选人是否具备正直的品格。在 OCI,debrief 的结果,通常有 hire 和 no hire 两种,但是有一种情况,可以归结到一个特殊的 “never hire” 里面去,这样的候选人没有面试冷冻期,不会有职位和级别的讨论,就是一个 “永不考虑” 聘用——这就是品格问题。品格问题会导致 never hire 的出现,比如候选人对当前的所在职位说谎了。

再比如,和团队的契合程度。不同的团队,接纳候选人的程度和要求都是不一样的。一个典型的例子是,有时候我们发现,有的候选人在投票的边界线上,即本身是具备相当的潜力的,但是由于相对缺乏领域经验,且某些方面显示出方法明显不得要领。如果团队中有成熟、有经验的工程师可以带着,且团队有一定的空间允许他花更长的时间学习和成长,那么最后的结论就是 hire,否则就是 no hire。你也可以看出,很多时候这样的决定都不是非黑即白的,影响的因素是多方面的。

再再比如,性格不兼容导致的风险。我遇到过一例,候选人在面试过程中,在多轮面试中都表现出高傲和自满的个性来。于是这成为了一个担心招聘进来以后,风险过高的重要方面。于是最后我们放弃了这个候选人,尽管这个候选人的技术方面是没有问题的。有人可能会说,聪明人都是有个性的。但其实 “有个性” 和 “难相处” 却有着微妙的差别,而且再包容的团队,也有自己的底线。我们当然不希望错过优秀的人才,但是这并不是不计代价的。

从这几个方面也能看出,这些 “非能力” 的考察项,往往具备着或 0 或 1 的 “red flag” 的特点。面试官一般不会花心思在这部分的考察上,但如果发现这方面的问题,且经过了明确。那结果往往就会是一个明确的否决票,而这个否决票是和级别、职位无关的。

回看那个案例

讲完了技术面试的目的,再来回看那个案例。那个案例中,所记叙的面试过程,对于技术面试的技术能力和非技术能力的考察,是否有覆盖呢?我们不妨一条一条看吧:

技术能力方面:

  1. 分析问题,整理需求的能力。这一条考察的程度明显是不够的,给出的问题,是一个明确的、具体的算法题,也就是要实现一个 LRU 队列。也许这其中存在着问题分析和需求整理的空间,但对于具体算法题来说,这个空间显然并不大,而且候选人闷头就写了,这方面无从考察。对于一个初级工程师的面试来说可能还好一些,我通常没有微词;可对于一个要去面试一个经验丰富的工程师,我是很不赞成纯算法题面试的,而这就是其中的一个重要原因。
  2. 根据需求来设计系统的能力。这一点的覆盖基本为 0。上来就写代码了,不清楚思考的过程,也更谈不上什么系统设计了。
  3. 将核心逻辑实现的能力。这条确实是这种面试方式能够覆盖的部分,因为整个过程,就是候选人思考并编码实现的过程,只不过,面试官能得到的只有一个 “结果”,而非整个 “过程”。这样的数据,能反映出来在核心逻辑实现方面的价值,就要大打折扣了。
  4. 经验和其它工程能力。也许能够从代码的实现上获知一部分,但这一条考察的程度也显然是很不够的。

再来看非技术能力方面:

  1. 沟通合作的能力。这是最大的问题,因为这方面是远远不足的,整个过程没有沟通,没有合作,只有默默地做题。
  2. 热情和兴趣。这个过程很难从这个角度获取足够的候选人在热情和兴趣方面展示出来的信息。
  3. 学习能力。同上。

也就是说,除了 “将核心逻辑实现的能力” 可能还勉强过得去,这样的面试方式,并无法全面、合理地考察候选人作为软件工程师的综合素质。

事实上,如果你联想实际工作。如果你的团队中有这样一个工程师,拿到一句简单的需求,不确认问题,不沟通设计,不讨论方案,直接就开始埋头苦干,就算能写出可以工作的代码来,这是不是依然是一件无比恐怖的事情?显然,我们的面试要尽可能避免这样的事情在真实世界中发生。我们要找的是软件工程师,不是只会刷题编码者。

这也是我把这个案例,放在开头,作为反面案例的原因之一。

等等,“之一”!难道还有别的原因?

是的,这还没完,这个案例还有着其它弊端,我想再卖个关子——而现在,你可以想一想,再往下看。

怎样的问题才是 “好” 问题?

终于要正面回答标题中的问题了,到底怎样的问题才能真正称得上 “好” 问题呢?下面是我认为最重要的几条衡量标准。

从模糊到清晰

首先,这个问题在一开始要足够模糊,以便让候选人可以逐层递进,逐步细化,寻根究底。这个过程,其实就是将 “具体问题” 经过分析、归纳、思考、抽象并将其映射成为一个 “软件问题” 的过程。在问题变得清晰的过程中,理想的情况是,候选人可以表现出主动性,即候选人可以在多数情况下引领讨论的思路,而不是面试官。面试官需要顺着候选人的思路,逐步框定下问题的讨论范畴,并明确到其核心实现是确实可以用软件的办法实现的。

在这样的状态下,候选人可以以自然的状态,具备相当自由度地发挥自己的能力。从这个过程中,可以观察得到太多候选人的不同角度的特质了。通过这种方式,也可以很大程度避免了已经知道 “标准答案” 的面试官,由于思路的局限性,而给面试施加的源自于主观偏好的影响。

这就好像是开放世界的 RPG 游戏,有多个不同的路径都可以完成任务,玩家可以决策并决定主角的走向,但是这一切始终还要在游戏设计者的掌控之内。这当然是说的理想状态,有时候会有偏差,但我们朝着这个方向努力。这也对面试官驾驭不同的状况有着很高的要求,毕竟,面试官要对这个问题前前后后足够的熟悉,以便应对各种不同的细化场景。有一个常见的方式,是可以从一个自己已经足够熟悉的问题开始,比如自己曾经多年工作涉及的某类系统。

我来举一个具体例子。比如,有这样一个问题:

怎样设计一个流量控制系统?

这就是一个模糊到没法再模糊的问题了。不知你会不会产生下面这样的问题:

  • 什么系统需要流量控制?
  • 现在的流量是多少?
  • 需要支持到什么时间精度?
  • 流量控制的规则怎么定义?
  • 超过流量的请求怎么处理?
  • ……

其实,这些都或多或少是需要面试官和候选人一起逐步思考、分析和明确的。在这个过程中,可以考察的内容太多太多了。

事实上,针对不同程度的候选人,上述这个问题给出的最原始的模糊程度是不一样的,问题越是模糊,这部分对于候选人的要求也就越高。对于一个工作十多年的,有着多年系统设计经验的工程师来说,上面这些问题大致都应该是他/她能够主动提问,或是主动引领明确的。

值得一提的是,理想的问题最好还有一些隐藏的 “坑”,能否把这些坑识别出来,也是对于工程能力方面,一个很好的小的考察点。比方说,优秀的候选人应该想到,流量控制可以基于绝对时间窗口,或是相对时间窗口来进行的,但是要真正保护系统,相对时间窗口才是最理想的。当然在实现难度上,相对时间窗口,往往会更难一些。

而对于一个没有工作经验,并将要研究生毕业的候选人来说,问这样一个模糊的问题,往往带来了过大的难度,不但不容易推进面试的进程,还可能给候选人带来沮丧的心理。我们不希望看到,候选人拿到问题以后就懵了,如果发现候选人推进有困难,面试官需要介入并帮助。

因此根据候选人的程度,这需要面试官主动回答这些问题,或是直接缩小或明确问题的范畴,当这个问题的范畴缩到最小时,这可以是一个直接存在多种解法的算法题。极端地说,这个问题可以一直缩小到这样的程度:

假定说有这样一个 API,名字叫做 isAllowed,这个 API 在系统每次收到请求的时候就调用,传入的是请求对象,传出 boolean 值表示是否允许这次调用——如果最近一分钟内调用次数小于 10000 次就允许,反之则不允许。你能否将这个 API 实现出来?

如果候选人还一脸迷茫,可以提供这样的参考 API:

class RateLimiter {
    public boolean isAllowed(Request req) {
        // TODO
    }
}

你看,这只是一个将问题明确、细化和分解的过程,并没有涉及到实际实现代码该用的算法。但是,上面提的那些问题,要么都通过这个例子明确了,要么都给出具体数字了,这本身,就将一个模糊的问题,降低难度明确为一个具体的算法问题了。

不止一个解

前面一步已经谈到了有不同的方式可将模糊的 “实际问题” 映射到了一个可解的 “软件问题”,那么现在,这个 “软件问题” 依然没有标准答案。可能有几个参考答案,它们互相比较起来各有优劣。大多数情况下,候选人的思路,都在这几个参考答案的思路之中,但有时也能看到特立独行的新奇思路。

如同前一步所说的那样,对于不同级别的软件工程师职位来说,需求分析、系统设计等等这些方面的要求可能有着很大的差别;但是在这一步,对于数据结构和算法这样的基础能力,却是接近的。

对于这里谈到的流量控的算法来说,实现方式是有很多种的,代码复杂程度,控制精度,时间复杂度和空间复杂度等等都有着非常大的区别。当然此时涉及到的,已经基本只是算法层面的话题了,就算法本身而言,我在极客时间专栏中对其中的几个典型方法做了一些介绍,感兴趣的话可以阅读。

我可以再举一个我曾经经常在面试中拿来使用的例子:

某社交网站有两百万的注册用户,每个用户都有积分属性,且积分根据用户在社交网站上的行为而不断有小幅度的频繁变更(比如登陆一次就+1 分,评论一次就+2 分等等),怎样设计一种算法,能够高效、准确地实时获取指定用户在所有用户中基于积分的排名?

上面的问题从模糊逐步落实到实现上的时候,异步、定时地排序,是最容易想到的方案,而题目表述中的 “高效” 和 “实时” 这两个修饰词让这个问题变得困难。这个过程中,我见到的不错的办法就至少有七、八种,比方说,下面这个推进问题解决的例子:

  1. 候选人:在需要的时候进行排序,方案是……
  2. 面试官:好,这样的方式下,时间、空间复杂度是多少?
  3. 候选人:……(说着说着自己意识到时间消耗可能巨大)
  4. 面试官:对,不仅时间、空间都消耗巨大,CPU 也是,你能否优化?
  5. 候选人:……(提出了一些优化思路,但是他自己对它们的实时性也不满意)
  6. 面试官:好,有换个角度更进一步优化的方式吗?
  7. 候选人:对了,可以让数据一直是排好序的!
  8. 面试官:好主意,那你怎么设计数据结构呢?
  9. 候选人:我可以使用一个 map 来保存用户 id 到积分的映射,再把积分从小到大按序放在数组中,这样二分查找就可以找到对应积分所处的排名。
  10. 面试官:听起来不错,那么这时候获取排名的复杂度是多少?
  11. 候选人:……
  12. 面试官:对,每当用户的积分小幅变化的时候,你怎么维持这个数组依然有序?
  13. 候选人:从数组中拿掉一个老的积分,再放入一个新的积分……
  14. 面试官:这个变更影响的数据量有多少,时间复杂度又是如何?
  15. 候选人:……
  16. 面试官:不错,可这个方法有什么问题吗?
  17. 候选人:(恍然大悟)如果新添加一个用户,新的积分会出现在数组头部,数组内的所有数据都要向后移动一个单位!
  18. 面试官:没错,那你打算怎么优化?
  19. 候选人:可以把数组内的积分从大到小排序,这样新添加的用户所对应的积分总在尾部。
  20. 面试官:很好,这个方法还有什么问题吗?
  21. 候选人:……(意识到在某些情况下,有很多用户拥有相同的积分,这时时间复杂度会退化)
  22. 面试官:那样的话,你怎么优化?
  23. 候选人:数组的元素除了记录当前积分,还记录有多少个用户具有这个积分,从而消除相同积分的重复元素……
  24. 面试官:很好,可这个方法会带来一个问题,你能想到吗?
  25. 候选人:对了,如果积分变化以后,新的积分是没有出现过的,那么添加到数组里,就是一个新元素,于是所有比它小的积分全部都要向后移动一个单位。
  26. 面试官:非常好,那么你怎么优化?
  27. 候选人:如果使用链表来代替数组就可以避免这个问题,(突然意识到)可是链表我就没法二分查找了……
  28. 面试官:没错,那什么样的数据结构和链表在这方面具有一定相似性,又能够具备二分查找相似的时间复杂度?
  29. 候选人:……(这一步能回答出来答案就很多了,很多都是很不错的思路,比如有用跳表的,有用二叉搜索树的等等)

这只是一个简化了的片段,实际的沟通的内容远比这部分内容多,但是从中也依然可以管中窥豹,看出问题解决的过程是怎样逐步推进的。

从这里也可以看出,无论是从实际问题细化到软件问题,还是求解这个软件问题,都存在着多条通往罗马的道路,看起来很美好,但这样的问题设计和面试把控并不容易。但既然大家都是软件工程师,是未来有可能一起工作的工程师,面试官的能力和可能就和候选人接近,于是,为了保证面试的效果,就一定要精心准备这样的问题,而不能指望随机和临场想出来一个 “好” 的问题提问。

围绕问题的解决要完整

这个问题的分析、讨论和解答过程要完整。对,其实这一点说的已经不是问题本身了,而是攻克这个问题的过程了。

这指的是整个过程要努力让候选人能够抵达 “踮踮脚能够到” 的难度,并且能够完成从确认、分析、讨论、编码、验证和改进等一个过程。这让整个面试显得完整,同时带来了这样两大好处:

  • 对于面试官来讲,这样一个完整的过程,可以更全面地考察候选人,避免陷入视角过窄和一叶障目的情境。同时,“踮踮脚能够到” 的难度,又可以给整个考察的进程具备较为合理的预期。
  • 对于候选人来讲,心态可以得到一定程度的平复,不沮丧,能够 “完整地” 面试完一轮,能够收获信心。别忘了,面试是双向的,给候选人一个良好的印象是很重要的。

前文我举的这个将问题从模糊到逐步清晰化的这个例子,就是一个需要面试官根据候选人情况动态调整的例子。在候选人能够经过思考而快速推进问题解决进展的时候,要让出主动权,以被动回答和鼓励为主;但在候选人卡壳的时候,要夺回主动权,及时给出提示和引导。

在落到数据结构和算法上面的时候,极少有候选人能够在叙述思路的时候直接给出最优解的。这时候,如果时间充裕,特别是在候选人进展非常顺利的时候,可以不断提示、追问以要求 “代码前优化”,一步一步优化到他/她的问题解决的能力边界,这就是其中的一个探寻其 “踮踮脚能够到” 的这个问题的解决能力的一个办法。但这个过程的前提,是一定要给编码留足时间。当然,如果候选人不能在限定时间内给出清晰的优化后思路,那不妨就退一步到原先那个算法角度不那么 “好”,但是思路清晰的解法上,并落实到代码。

比方说,对于前文所述的那个流量控制的问题,候选人在还有半个小时的时候就想到了使用一个时间复杂度为 O(N) 的解,而面试官认为时间还比较充裕,那就可以尝试挑战一下候选人 “能否再优化一下复杂度?”。

有些时候,由于前面的过程磕磕绊绊,时间剩下不多了,依然只有时间复杂度较高的 brute force 的解法,那么将这个解法实现了,其实也是一个不错的选择。有时候时间实在比较紧张,可以要求实现一部分核心代码,这些都比由于时间太短而代码写了一半匆匆收尾要好得多。我的经验是,在讨论充分,思路清晰的情况下,代码完成的时间,一般只需要 10 到 15 分钟,这样的代码量对于面试来说是比较合理的。

当然,相较而言,一种更为糟糕的结果是,一直到最后,讨论的深度依然离编码尚远,甚至依然停留在一个很高的泛泛而谈的层面。

如果在编码完成之后,尚有时间,优秀的候选人会拿实际的例子去验证代码的正确性。而面试官也可以和候选人讨论 “代码后优化”,比如以下的问题:

  • 你能否进一步优化算法以提高时间/空间复杂度?
  • 如果是工业级别的代码,你觉得代码还有哪些问题?
  • 你该怎样去设计测试,来保证这段代码的正确性 ?

对考察项的覆盖兼有深度和广度

这个问题要能够考察前文所述的技术能力和非技术能力。

这里说的覆盖,不一定要全部覆盖,但是要覆盖其中的大部分,并且对于每一个考察项要具备一定的考察深度。我见到过不少其它的面试风格,但我认为这样就着一个模糊的主要问题(话题)逐步展开的方式是最好的。因为它可以兼具广度和深度的平衡。具体来说:

面试很容易走向的一个极端就是考虑广度,但缺乏深度。比如一种风格是绝大部分的面试时间用来询问候选人的项目和经验,让候选人自己介绍,而面试官跟进追问。这原本是一种很好的方式,但是由于候选人对自己的项目通常远比面试官熟悉得多,除非明确的同一领域,否则面试官较难对于其中的内容挖掘到足够的深度,从而识别出候选人是真正做事的人,还是夸夸其谈的人。这也是这种方式理论可行,但实际开展难度较大的原因之一。

另一个极端,自然就是考虑深度,但缺乏广度。比如给出一个过于具体的问题,缺乏发挥和迂回的空间,对这个问题所涉及的很小一部分深度挖掘,甚至纠缠于某个特殊而单一的 case 很长时间,但是却只能覆盖很少的考察角度。

由于深度和广度都是可控的,那么这样的可以拿来问不同经验和不同技术背景的工程师候选人。这样对于面试官来说,可以获得足够的数据,便于在遇到新的候选人的时候,能够进行横向比较,做出更准确的评估。比方说,过去某级别的候选人能够在面对这个问题的时候,能够达到什么样的级别,而如今这个候选人有着类似表现,这就可以以过去的那个例子来作为参考比较了。

“不好” 的问题

现在,让我们再次回到文章开头那个例子问题,除了已经提到的考察项的覆盖不够,它还有哪些问题呢?参考上文已经提到了 “好” 问题的标准,我觉得其中的这样两条是违背的:

从模糊到清晰。显然,问题给出的时候就已经相对比较清晰了,这样的方式并不能模拟软件工程师日常面对的许多模糊而困难的实际问题。我已经提到,对于经验丰富的候选人来说,这样的问题无法重现将实际问题映射到软件问题这样的一个重要思考过程。

另一个是,围绕问题的解决要完整。示例问题的考察过程中,只有缺乏互动的编码环节,没有其它过程,没有编码前的分析、思考和优化,也没有编码后的测试、改进和优化。考虑到 LRU 完整算法是一个实现代码量偏大的问题,拿来放到面试中做一个完整实现,由于会消耗过多的时间,挤压其它时间,因此显得有些过了。

其它 “不好” 的问题

前面说了过于清晰的纯算法题的 “不好” 之处,也说了 “好” 问题的例子,最后我想再来说几类其它的且典型的 “不好” 的例子。

依赖于语言或框架

而这里说的依赖不好,是因为考虑到候选人不同的技术背景,如果没有特殊的需要,避免这样的依赖,以避免产生不应有的错误的衡量数据。

比方说,问一个关于 JVM 的问题,这个问题可以问,特别是在候选人强调其具备一定 Java 背景的前提下。但是这样的问题不能成为 “主菜”,尤其是候选人不一定具备很强的 Java 背景,这样的方式会导致考察的偏颇。

过于复杂的规则或背景知识

这主要是基于面试的有限时间考虑的,过于复杂的规则或背景知识,容易把时间消耗到澄清它们上面;另外,有些背景知识并非是所有人都熟知的,这就会引起考察标准的非预期。我给一个经典的反面例子:

设计一个算法,把一个小于一百万的正整数,使用罗马数字来表示。

这个问题描述简洁,但是拿来做技术面试中的主要问题,其中一个不妥之处就是,不是所有人都很清楚一百万内的罗马数字表示法的。对于不清楚的人来说,要搞清楚这个表示法的规则,就已经是一件有些复杂和耗时的事情了。显然,这个罗马数字表示法的知识点,不应该成为考察和衡量的标准。

当然,有时候有些问题的背景知识是冷门的,但是表述简洁,那么这样的话只要 面试官能够主动、迅速地说清楚,拿来使用是没问题的。

知识性问题

我想特别谈一谈,对于知识性问题的提问。在讨论问题的过程中,如果涉及到关联的具体知识,那么提问一些基础知识是一个不错的选择,这是考察候选人 CS 基础是否牢靠的方式。比如候选人提到使用 HashMap,而他/她最熟悉的编程语言是 C++,那么询问在 C++中 HashMap 是怎样实现的就是一个可行的问题。而且,由于这样的问题是嵌套在前述的这个大流量控制问题的解决过程中的,更显得自然而不突兀。

反之,如果这样的知识性问题较为冷门或浅表,和当前的讨论中的问题无关,或是不在候选人的知识体系内,这样的问题就值得商榷了。比如,仅仅因为自己的项目组使用 Spring,面试官就询问候选人 Spring 的 bean 的单例和多例分别是怎样配置的,而恰巧候选人又是 C++背景,对于这部分并不熟悉,这样的问题除了给候选人造成困扰以外,意义就不太大了。

如果把知识性问题作为主要问题来提问,我认为是不适合的。因为一方面它不具备普适性,另一方面它又具备太强的随机性。

这里不具备普适性这一条,指的是不同技术背景的软件工程师候选人都要能够适合参与这个问题的解答。举例来说,如果问 “Tomcat 的线程池的配置策略?”,这就是一个不具备普适性的问题,这是一个偏重 “知识性” 的问题,如果候选人没有使用过 Tomcat,或是只是略有了解,很可能就栽了。

而具备太强的随机性这一条,指的是一旦待考察的问题具体以后,这个问题就容易从对 “能力” 的考察变成了对 “知识” 的考察,而这个知识,又恰恰是比较容易随机的。也就是说,我们不希望候选人 “恰巧” 知道或不知道某一个细小的知识点,来决定他/她是否通过这项考察。

无论如何,知识性的问题作为考察的辅助方式可以,但不应成为主角。我还是觉得我们应当能把更多的时间,留给主要问题的解决过程本身。

关于 “技术面试中,什么样的问题才是好问题?”,我就说这么多吧。也欢迎你分享你的看法,我们一起讨论。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/38fQVuV

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 RSA 背后的算法

RSA这篇文章我本来是想写了放到极客时间上我写的专栏里面的,但是专栏的内容是需要仔细斟酌的。这篇文章我认为还是偏难,不适合整个专栏的内容和难度的定位,因此我把它稍微加工了一下,放到我这个博客上。

在专栏中的第 36 讲的选修课堂(该讲预计在 12 月初发布)中,我介绍了 Diffie–Hellman 密钥交换这一算法,它可以说是质数在加密技术中的一个应用,并且是通过其中的 “模幂运算” 来实现的。今天,我来介绍质数的另一个应用,RSA 背后的算法。我在互联网上搜索了一下,我发现基本没有能把它背后的实现原理用浅显的中文叙述讲清楚的,但我还是想试一试,看看能不能尽可能避开那些难懂的术语,用尽量形象和易于理解的方式,把 RSA 背后的原理讲清楚。

在专栏的第 02 讲,我们讲了非对称性加密,比如通过公钥加密的数据,能且只能通过私钥来解密,可是这是怎样实现的呢?这就要讲 RSA 加密技术的原理了。现在,假定我们要通过 RSA 来进行安全的通信,于是你要使用我发布的公钥来对数据加密,加密以后发给我,我拿到加密数据以后使用对应的私钥解密,而攻击者截获了这个加密数据并尝试破解。

模幂等式

我们在介绍 Diffie–Hellman 密钥交换的时候讲到了这个模幂等式:

gᵃ mod p = A

从难度上看它具有如下三个特性:

  • 特性 ①:已知 g、a 和 p,求 A 容易;
  • 特性 ②:已知 g、p 和 A,求 a 困难;
  • 特性 ③:已知 a、p 和 A,求 g 也困难。

再看看上面我们介绍的模幂公式关于离散对数求解的三种难易程度不同的情况吧,我们在 Diffie–Hellman 密钥交换中应用了特性 ① 和特性 ②,而在 RSA 中,我们还要应用特性 ① 和特性 ③

观察特性 ①,我们可以利用它来设计 RSA 加密,即让 g 代表需要被加密的实际值,而 a、p 可以公开。于是你就求出它的 a 次幂,并取 p 模,得到了 “密文” A,把它发给我。这个过程中,如果 A 被截获,那么根据特性 ③,已知 A、p 和 a,攻击者是很难求解出 g 来的。我们已经说过了,这符合 “正向计算简单,逆向求解困难” 这一特性,这一点很适合用来加密。

但是和前面的 Diffie–Hellman 密钥交换不同的是,我们并不是要让所有人都求解这个 g 困难,因为密文是发给我的,我得很容易求解这个 g 才行啊,要不然就像是用一把没人拥有钥匙的锁来加密,这把锁就失去意义了。

我们再来观察一下这个模幂等式:

gᵃ mod p = A

藉由 Diffie–Hellman 密钥交换带来的灵感,如果我们构造这样一个和上式形式一致,但变量具有一定对称性的等式:

Aᵈ mod p = g

这其实是什么?这不就是将加密的数据 A,经过模幂运算以后,得到了原始的未加密数据 g 了吗?也就是说,既然 a 是公钥,那么这里的 d 就是所谓的 “私钥” 啊

好,我们把后面这个公式的 A 通过前面那个公式来带入,得到:(gᵃ mod p)ᵈ mod p = g,根据我们前面介绍模幂运算时提到的联等公式,它就可以化简为:

gᵃᵈ mod p = g

因此这个式子,就表示出了公钥、私钥,以及被加密数之间的关系。

接下去,我们来思考怎样生成这个私钥 d。

欧拉函数

为了继续进行后面的分析,我们需要一点知识储备,首先是欧拉函数。欧拉函数 φ(x) 表示,有多少不大于 x 的正整数中,与 x 互质的数目(即公因数只有 1)。

举例来说,要计算 φ(4),你看不大于 4 的正整数包括 1、2、3、4,其中:

  • 1 和 4 互质;
  • 2 不和 4 互质,因为它们有公因数 2;
  • 3 和 4 互质;
  • 4 不和 4 互质,因为它们有公因数 4。

所以 φ(4) = 2。

欧拉函数 φ(x) 一般很难计算,但是如果 x 是质数,情况就不同了,因为质数和任何比它小的正整数互质,比如 φ(5) = 4,这四个数分别是 1、2、3、4,因此,在 x 是质数的情况下:

φ(x) = x – 1

同时,如果 x 是一个可以因式分解的合数,比如 x = m*n,欧拉函数还具备这样的特性:

φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)

这个公式我们后面还会用到。

欧拉定理

有了欧拉函数的知识,我们进一步了解欧拉定理。欧拉定理指的是,对于正整数且互质的 g 和 x,有如下性质:

gᵠ⁽ᴾ⁾ ≡ 1 (mod p)

其中的三横线不是表示 “恒等”,而是表示 “同余”,上面的意思是,g 的 φ(p) 次幂,除以 p 所得的余数,和 1 除以 p 所得的余数,二者相同。

举例来说,当 g=3,p=5,根据前面学的欧拉函数有 φ(5)=4,那么 gᵠ⁽ᴾ⁾=81,81 除以 5 余 1;1 除以 5 也余 1,同余关系成立。

密钥生成

由于 1ᵏ ≡ 1 (mod p),我们可以给指数上的欧拉函数赋予正整数系数 k,gᵏᵠ⁽ᴾ⁾ ≡ 1 (mod p),我们再给两边乘以 g,得到 gᵏᵠ⁽ᴾ⁾⁺¹ ≡ g (mod p)。当 g 小于 p 的时候,g 除以 p 的余数就是 g,因此这个同余式可以写成:

gᵏᵠ⁽ᴾ⁾⁺¹ mod p = g

再联想前面的:

gᵃᵈ mod p = g

你看,这两个式子的形式是一样的,这就意味着,kφ(p)+1 = ad。因此,这个私钥就是:

d = (kφ(p)+1)/a

这意味着什么?这意味着如果能够求得 φ(p) 的值,那么这个私钥就求解出来了。但是,怎样求解 φ(p) 呢?这里,我希望:

  • 密钥是我生成的,因此我求解这个 φ(p) 要非常容易,这样我就可以很容易计算出密钥来;
  • p 是公开的,攻击者仅仅知道 p,求解 φ(p) 要非常困难才行,那样才能保证加密的安全性。

你看,这是不是又一个需要 “正向计算简单,逆向求解困难” 特性的问题?

回想一下前面我们学习欧拉函数的时候,我讲到了,如果 m、n 是质数,那么欧拉函数可以这样求得:

φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)

这正是我需要的!

你想,如果我选取两个非常非常大的质数 m 和 n,选择 p 的时候,就让它等于 m 和 n 的乘积,那么 φ(p) = φ(m*n) = (m-1) * (n-1),这个正向计算是很简单的,也就是说,因为我知道 m、n,密钥的生成是很容易的一件事情。

可是,攻击者拿不到 m、n,就只能硬生生地尝试去给 p 因式分解才能得到 m、n,而对于一个超大质数的因式分解,这个过程是极其困难的。纵观整个 RSA 的原理,其中涉及到了两个和质数相关的 “正向计算简单,逆向求解困难” 的特性:

  • 一个是前面介绍的模幂等式逆向求底数;
  • 另一个就是这里介绍的超大质数的因式分解。

这也就是 RSA 安全性的基本原理。

当然,随着科技发展,计算能力越来越强,特别是量子计算的兴起,我们对超大质数的位数要求也越来越高,512 bit 的 RSA 已经被破解,而 1024 bit 也已经摇摇欲坠,现阶段 2048 bit 长度还是安全的,可是未来,谁又知道呢?

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/3585sa8

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 你真的理解什么是全栈开发吗?

抱歉近几个月博客文章更新不够频繁,也有朋友问过,现在我想告诉大家,那是因为我写专栏去了。今天,专栏 《全栈工程师修炼指南》 终于上线了,下面的内容,就是我将这些年来,关于全栈开发,自己的一些经验、心得、感悟,总结起来,并且酝酿思考了很久,撰写的这个专栏。我想,目前市面上某一项具体技术的教程通常好找,但是系统的全栈技术关系树,包含这些技术之间的演进、权衡和本质介绍,并引发思考的学习材料却并不好找。 值得一提的是,这个专栏中我将 全程朗读所有的技术文章 ,为的就是能够尽可能地把原汁原味的技术内容传达给读者,希望你可以从中享受技术单纯原始的快乐。

下面的内容就是关于这个专栏的宣传介绍,你也可以直接拖动到文章底部,查看目录,点击 链接进入极客时间 购买,或扫描微信二维码购买。

 

提起“全栈工程师”,你最先想到的是什么?大神?全能?还是无用?

许多人对全栈的评价褒贬不一,不同人的理解也天差地别。有些人以为全栈是中小公司鼓吹的,有些人觉得大厂才招全栈,那么全栈究竟是做什么的?对于工程师而言,是全栈好,还是专注一个领域好?

我们先来看一个数据。下图来自 2018 Developer Skills Report,在开发者评价自己角色的时候,多数人投给了“全栈开发者”。

该如何学习成为一名全栈工程师?

很多人膜拜“全栈”,却在面对大量的技术栈时没有有效的学习路径和方法,尤其基于 Web 的全栈技术五花八门,涉及面广,迭代迅猛等等,我经常听到这样的困惑:

  • 想学 Web 全栈技术,期待能独立交付产品,但真的很迷茫;
  • 具体某项技术还好说,可全栈包含了那么多技术,怎么选?
  • 我该从哪里开始,遵循哪些原则,学习哪些技术?

为了帮大家解决这些问题,我在极客时间开了专栏 《全栈工程师修炼指南》,希望给你一条从碎片化到整体把握、清晰高效的学习路径,帮你系统掌握 Web 全栈的关键技术,真正从入门到技能实践。

我是谁?

我是熊燚,网上大家都叫我四火,现在在西雅图甲骨文(Oracle)的云计算部门就职,职位是首席软件工程师,负责云基础设施的分布式工作流引擎设计与开发,曾就职于华为、亚马逊(Amazon)。

最早我曾是华为某大型视频门户和视频平台的初创人员。后来加入了亚马逊,负责过数千万商品销量预测系统和成本利润计算平台的研发,重新设计并开发了数据分析和可视化系统,还维护和优化过数据分发的高可用服务,也改进过核算平台的分布式计算架构和工作流引擎。这些多领域的工作让我快速成长,并积累了大量的宝贵经验。

作为全栈工程的实践者,为了帮你更好的理解我所讲解的内容,特此给大家整理了一张「全栈开发核心知识框架图」,让你清晰地了解我们应该掌握的关键技术是什么。

我会如何讲解这个专栏?学完后能收获什么?

在专栏中,我会聚焦基于 Web 的全栈技术, 围绕“网络协议、MVC 架构、前端技术、持久层技术“等核心领域 ,梳理学习路径,对比剖析代表性技术,立足最佳实践、实战专题,带你从技术本质上理解、全面掌握全栈技能,培养“全栈高手思维”。

我在专栏中案例所用语言主要是 Java 和 JavaScript,由于全栈本身技术种类多、同类技术多的特点,专栏着重于讲原理、技术之间的演进、权衡和对本质的分析,并辅以非常多的实际项目和技术应用的案例。

  • 内容广度:我会选择每个核心领域的代表性技术来介绍,它们一定典型、常用,且深刻;
  • 内容深度:控制在合适的位置,让入门到进阶的工程师都有收获,我设计的“选修课堂”和“扩展阅读”,可以帮助你快速提升,一定不能略过。
  • 注重实践:我会引入最佳实践及自恰性强的专题,比如网站的性能优化、分页技术等,带你边学边做强化收获。

学习完后,希望你可以收获:

  1. 系统掌握 Web 全栈技能树
  2. 网络、前后端、持久化等核心技术解析
  3. 全栈开发的技术比较和选型
  4. 拓宽技术视野,培养全栈思维

1 分钟看看目录,你会发现你想要的

限时订阅福利

早鸟优惠¥68,原价¥99,你可以微信扫码购买,或者 点击此链接 进入极客时间购买。

这个世界需要专家,但更需要通晓各个层面知识,能够独立、快速解决问题的人。希望“全栈工程师”能成为你职业上升通道上的一个驿站,成为你的一个人生选择。

如果想领取高清版「全栈开发核心知识框架图 + 100 本架构师文集」,可以在「极客时间」公众号后台回复「全栈」领取。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/2ZQxYPd

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 分析运行中的 Python 进程

在 Java 中打印当前线程的方法栈,可以用 kill -3 命令向 JVM 发送一个 OS 信号,JVM 捕捉以后会自动 dump 出来;当然,也可以直接使用 jstack 工具完成,这些方法好几年前我在 这篇性能分析的文章 中介绍过。这样的需求可以说很常见,比如定位死锁,定位一个不工作的线程到底卡在哪里,或者定位为什么 CPU 居高不下等等问题。

现在工作中我用的是 Python,需要线上问题定位的缘故,也有了类似的需求——想要知道当前的 Python 进程“在干什么”。但是没有了 JVM 的加持,原有的命令或者工具都不再适用。传统的 gdb 的 debug 大法在线上也不好操作。于是我寻找了一些别的方法,来帮助定位问题,我把它们记录在这里。

signal

在代码中,我们可以使用 signal 为进程预先注册一个信号接收器,在进程接收到特定信号的时候,可以打印方法栈:

import traceback, signal

class Debugger():
    def __init__(self, logger):
        self._logger = logger
    
    def log_stack_trace(self, sig, frame):
        d={'_frame':frame}
        d.update(frame.f_globals)
        d.update(frame.f_locals)
    
        messages  = "Signal received. Stack trace:\n"
        messages += ''.join(traceback.format_stack(frame))
        self._logger.warn(messages)
    
    def listen(self):
        signal.signal(signal.SIGUSR1, self.log_stack_trace)

通过调用上面的 listen 方法(比如 new Debug(logger).listen()),就将一个可以接收 SIGUSR1 并打印方法栈的接收器注册到当前进程了。

那么怎么向进程发送信号呢?和 JVM 的方法类似,可以通过操作系统命令来发送:

kill -30 pid

这里的信号为什么是 30?这是因为 SIGUSR1 被当前操作系统定义成 30(请注意不同的操作系统这个映射表是可能不同的),这点可以通过 man signal 查看:

No Name Default Action Description
1 SIGHUP terminate process terminal line hangup
2 SIGINT terminate process interrupt program
3 SIGQUIT create core image quit program
4 SIGILL create core image illegal instruction
5 SIGTRAP create core image trace trap
6 SIGABRT create core image abort program (formerly SIGIOT)
7 SIGEMT create core image emulate instruction executed
8 SIGFPE create core image floating-point exception
9 SIGKILL terminate process kill program
10 SIGBUS create core image bus error
11 SIGSEGV create core image segmentation violation
12 SIGSYS create core image non-existent system call invoked
13 SIGPIPE terminate process write on a pipe with no reader
14 SIGALRM terminate process real-time timer expired
15 SIGTERM terminate process software termination signal
16 SIGURG discard signal urgent condition present on socket
17 SIGSTOP stop process stop (cannot be caught or ignored)
18 SIGTSTP stop process stop signal generated from keyboard
19 SIGCONT discard signal continue after stop
20 SIGCHLD discard signal child status has changed
21 SIGTTIN stop process background read attempted from control terminal
22 SIGTTOU stop process background write attempted to control terminal
23 SIGIO discard signal I/O is possible on a descriptor (see fcntl(2))
24 SIGXCPU terminate process cpu time limit exceeded (see setrlimit(2))
25 SIGXFSZ terminate process file size limit exceeded (see setrlimit(2))
26 SIGVTALRM terminate process virtual time alarm (see setitimer(2))
27 SIGPROF terminate process profiling timer alarm (see setitimer(2))
28 SIGWINCH discard signal Window size change
29 SIGINFO discard signal status request from keyboard
30 SIGUSR1 terminate process User defined signal 1
31 SIGUSR2 terminate process User defined signal 2

当然,也可以写一点点 python 脚本来发送这个信号:

import os, signal
os.kill($PID, signal.SIGUSR1)

原理是一样的。

strace

如果进程已经无响应了,或者上面的信号接收器没有注册,那么就要考虑别的方法来或者“进程在干什么”这件事情了。其中,一个有用的命令是 strace:

strace -p pid

比如,我自己写了一个测试脚本 t.py,使用 python 执行,然后调用 sleep,再给它发送一个 SIGUSR1 的消息,它打印方法栈并退出。这整个过程,我使用 strace 可以得到这样的结果:

strace -p 9157
strace: Process 9157 attached
select(0, NULL, NULL, NULL, {9999943, 62231}) = ? ERESTARTNOHAND (To be restarted if no handler)
--- SIGUSR1 {si_signo=SIGUSR1, si_code=SI_USER, si_pid=9273, si_uid=9007} ---
rt_sigreturn({mask=[]})                 = -1 EINTR (Interrupted system call)
stat("t.py", {st_mode=S_IFREG|0644, st_size=1281, ...}) = 0
open("t.py", O_RDONLY)                  = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=1281, ...}) = 0
fstat(3, {st_mode=S_IFREG|0644, st_size=1281, ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f631e866000
read(3, "import traceback, signal, time\n "..., 8192) = 1281
read(3, "", 4096)                       = 0
close(3)                                = 0
munmap(0x7f631e866000, 4096)            = 0
stat("t.py", {st_mode=S_IFREG|0644, st_size=1281, ...}) = 0
write(1, "Signal received. Stack trace:\n  "..., 134) = 134
write(1, "\n", 1)                       = 1
rt_sigaction(SIGINT, {SIG_DFL, [], SA_RESTORER, 0x7f631e06f5d0}, {0x7f631e392680, [], SA_RESTORER, 0x7f631e06f5d0}, 8) = 0
rt_sigaction(SIGUSR1, {SIG_DFL, [], SA_RESTORER, 0x7f631e06f5d0}, {0x7f631e392680, [], SA_RESTORER, 0x7f631e06f5d0}, 8) = 0
exit_group(0)                           = ?
+++ exited with 0 +++

可以看到从 strace attached 开始,到进程退出,所有重要的调用都被打印出来了。

在 iOS 下,没有 strace,但是可以使用类似的(更好的)命令 dtruss。

lsof

lsof 可以打印某进程打开的文件,而 Linux 下面一切都是文件,因此查看打开的文件列表有时可以获取很多额外的信息。比如,打开前面提到的这个测试进程:

lsof -p 16872
COMMAND   PID  USER   FD   TYPE DEVICE   SIZE/OFF     NODE NAME
Python  16872 xxx  cwd    DIR    1,5       2688  1113586 /Users/xxx
Python  16872 xxx  txt    REG    1,5      51744 10627527 /System/Library/Frameworks/Python.framework/Versions/2.7/Resources/Python.app/Contents/MacOS/Python
Python  16872 xxx  txt    REG    1,5      52768 10631046 /System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/lib-dynload/_locale.so
Python  16872 xxx  txt    REG    1,5      65952 10631134 /System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/lib-dynload/time.so
Python  16872 xxx  txt    REG    1,5     841440 10690598 /usr/lib/dyld
Python  16872 xxx  txt    REG    1,5 1170079744 10705794 /private/var/db/dyld/dyld_shared_cache_x86_64h
Python  16872 xxx    0u   CHR   16,2    0t39990      649 /dev/ttys002
Python  16872 xxx    1u   CHR   16,2    0t39990      649 /dev/ttys002
Python  16872 xxx    2u   CHR   16,2    0t39990      649 /dev/ttys002

它有几个参数很常用,比如-i,用来指定网络文件(如果是“-i: 端口号”这样的形式还可以指定端口)。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 http://bit.ly/2Xpz0zB

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 谈谈 Ops(最终篇):工具和实践

除了主要内容——工具和实践,这篇文章也对“谈谈 Ops”系列做一个汇总,提供一个访问入口。之前几篇,从一个纯粹 dev 狭窄的视角,谈了谈自己对 Ops 的一些认识:

在往下继续以前,如果没有看过前面的文字,不妨移步阅读,因为上面的内容对下面的内容做了一定程度的铺垫。

现在在写的这一篇文字,我准备是最后一篇,主要谈论这样几个事情:一个是工具,另一个是实践。我依然还是从 dev 的视角,而不是从一个专业运维的视角来记叙。

工欲善其事,必先利其器。我在主要且通用的工具中挑了几个,和最佳实践放在一起介绍,并且按照功能和阶段来划分,而不执着于列出具体的工具名称。 其中最主要的阶段,包括开发阶段,集成测试阶段,以及线上部署维护阶段。 顺便也再强调一次,Ops 远不只有线上系统的维护。

Pipeline

把 Pipeline 放在最先讲,是因为它是集成下面各路神仙(工具)的核心,通过 pipeline,可以把一系列自动化的工具结合起来,而这一系列工具,往往从编译过程就开始,到部署后的验证执行结束。

Pipeline 最大的作用是对劳动力的解放,程序来控制代码从版本库到线上的行进流程,而非人。因此,对于那些一个 pipeline 上面设置了数个需要人工审批的暂停点,使得这样的事情失去了意义。这样的罪过往往来自于那些缺少技术背景的负责人,其下反映的是对流程的崇拜(前面关于流程和人的文章已经提到),而更进一步的原因是不懂技术,就无法相信代码,进而无法信任程序员,他们觉得,只有把生杀大权掌握在自己手里,才能得到对质量最好的控制。这样的问题从二十多年前的软件流程中就出现了,到现在愈演愈烈。我只能说,这无疑是一种悲哀。

我见过懂技术的老板,也见过不怎么懂技术的老板,还见过完全不懂技术的老板。但是最可怕的,是那种不太懂或完全不懂,却又非常想要插一手,对程序员在软件流程方面指手画脚的老板。为什么是流程?因为技术方面他们不懂,没法插手,却又觉得失去了掌控,只好搞流程了。

我曾经遇到过这样一件事情:程序有一个 bug,因为在一个判断中,状态集合中少放了一个枚举值,导致了一个严重的线上问题。后来,程序员修正了问题,老板和程序员有了这样的对话:

老板:“你怎么保证未来的发布不会有这样的问题?”

程序员:“我修正了啊。”

老板:“我怎么知道你修正了?”

程序员:“我发布了代码改动,我使用单元测试覆盖了改动。”

老板:“好,我相信你开发机的代码改动做了。可我怎么知道你发布到线上的版本没有问题?”

程序员:“……发布的代码就是我提交的啊。”

老板:“你怎么能保证代码从你提交到线上发布的过程中没有改动?”

程序员:“……(心中一千头草泥马奔腾而过)我可以到线上发布的 Python 包里面查看一下该行是不是已经得到修改。”

老板:“好。我们能不能在 pipeline 里面,添加这样一个步骤——执行部署的人到发布包里面去检查该行代码是不是正确的。”

程序员:“……(现在变成一万头了)不要把,这样一个额外的检查会浪费时间啊。”

老板:“检查一下需要多少时间?”

程序员:“5 分钟吧”

老板:“花费 5 分钟,避免一个严重的问题,难道不值得吗?”

程序员:“……(现在数不清多少头了)如果这一行要校对的话,为什么其它几十万行代码不用肉眼校对?”

老板:“就这一行需要。因为这一行代码曾经引发过严重问题,所以需要。”

程序员:“……”

如果你也见过这样的情形,不妨告诉我你的应对办法是什么。

依赖管理

以 Java 为例,有个搞笑的说法是“没有痛不欲生地处理过 Jar 包冲突的 Java 程序员不是真正的 Java 程序员”,一定程度上说明了依赖管理有多重要。尤其是茁壮发展的 Java 社区,副作用就是版本多如牛毛,质量良莠不齐,包和类的命名冲突简直是家常便饭。我用过几个依赖管理的工具,比如 Python 的 pip,比如 Java 的 Maven,但是最好的还是 Amazon 内部的那一个,很可惜没有开源。注意这里说的依赖,即便对于 Java 来说,也不一定是 Jar 包,可以是任何文件夹和文件。一个好的依赖管理的工具,有这么几点核心特性需要具备:

  1. 支持基于包和包组的依赖配置。目标软件可以依赖于配置的 Jar 包,而若干个 Jar 包也可以配置成一个组来简化依赖配置。
  2. 支持基于版本的递归依赖。比如 A 依赖于 B,B 依赖于 C,那么只需要在 A 的依赖文件中配置 B,C 就会被自动引入。
  3. 支持版本冲突的选择。比如 A 依赖于 B 和 C,B 依赖于 D 1.0,C 依赖于 D 2.0,那么通过配置可以选择在最终引入依赖的时候引入 D 1.0 还是 2.0。
  4. 支持不同环境的不同依赖配置,比如编译期的依赖,测试期的依赖和运行期的依赖都可能不一样。

当然,还有许许多多别的特性,比如支持冲突包的删除等等,只是没有那么核心。

自动化测试

代码检查、编译和单元测试(Unit Test)。这一步还属于代码层面的行为活动,代码库特定分支上的变动,触发这一行为,只有在这样的执行成功以后,后面的步骤才能得到机会运行。单元测试通常都是是 dev 写的,即便是在有独立的测试团队的环境中。因为单元测试重要的一个因素就是要保证它能够做到白盒覆盖。单元测试要求易于执行,由于需要反复执行和根据结果修改代码,快速的反馈是非常重要的,几十秒内必须得到结果。我见过有一些团队的单元测试跑一遍要十分钟以上,那么这种情况就要保证能够跑增量的测试,换言之,改动了什么内容,能够重跑改动的那一部分,而不是所有的测试集合。

集成测试(Integration Test)。这一步最主要的事情,就是自动部署代码到一个拟真的环境,之行端到端的测试。比如说,发布的产品是远程的 API,UT 关注的是功能单元,测试的对象是具体的类和方法;而在 IT 中,更关心暴露的远程接口,既包括功能,也包括性能。集成测试的成熟程度,往往是一个项目质量的一个非常好的体现。在某些团队中,集成测试通过几个不同的环境来完成,比如α环境、β环境、γ环境等等,依次递进,越来越接近生产环境。比如α环境是部署在开发机上的,而γ环境则是线上环境的拷贝,连数据库的数据都是从线上定期同步而来的。

冒烟测试(Smoke Testing)。冒烟测试最关心的不是功能的覆盖,而是对重要功能,或者核心功能的保障。到了这一步,通常在线上部署完成后,为了进一步确保它是一次成功的部署,需要有快速而易于执行的测试来覆盖核心测试用例。这就像每年的常规体检,不可能事无巨细地做各种各样侵入性强的检查,而是通过快速的几项,比如血常规、心跳、血压等等来执行核心的几项检查。在某些公司,冒烟测试还被称作“Sanity Test”,从字面意思也可以得知,测试的目的仅仅是保证系统“没有发疯”。除了功能上的快速冒烟覆盖,在某些系统中,性能是一个尤其重要的关注点,那么还会划分出 Soak Testing 这样的针对性能的测试来,当然,它对系统的影响可能较大,有时候不会部署在生产环境,而是在前面提到的镜像环境中。

部署工具

曾经使用过各种用于部署的工具,有开源的,也有内部开发的。这方面以前写过 Ant 脚本,在华为有内部工具;在 Amazon 也有一个内部工具,它几乎是我见过的这些个中,最强大,而且自动化程度最高的。部署工具我认为必须具备的功能包括:

  • 自动下载并同步指定版本的文件系统到环境中。这是最最基本的功能,没有这个谈不上部署工具。
  • 开发、测试、线上环境同质化。这指的是通过一定程度的抽象,无论软件部署到哪里,对程序员来说都是一样的,可以部署在开发机(本地)用于开发调试,可以部署到测试环境,也可以部署到线上环境。
  • 快速的本地覆盖和还原。这个功能非常有用。对于一个软件环境来说,可能 1000 个文件都不需要修改,但是又 3 个文件是当前我正在开发的文件,这些文件的修改需要及时同步到环境中去,以便得到快速验证。这个同步可能是本地的,也可能是远程的。比如我曾经把开发环境部署在云上,因为云机器的性能好,但是由于是远程,使用 GUI 起来并不友好,于是我采用的办法是在本地写代码,但是代码通过工具自动同步到云机器上。我也尝试过一些其他的同步场景,比如把代码 自动同步到本地虚拟机上
  • 环境差异 diff。这个功能也非常有用。开发人员很喜欢说的一句话是,“在本地没问题啊?”,因此如果这个工具可以快速比较两个环境中文件的不同,可以帮助找到环境差异,从而定位问题。

当然,还有其它很有用的功能,我这里只谈了一些印象深刻的。

监控工具

我工作过的三家公司,华为、Amazon,还是 Oracle,它们的监控工具各有特点,但做得都非常出色。且看如下的功能:

  • 多维度、分级别、可视化的数据统计和监控。核心性能的统计信息既包括应用的统计信息,包括存储,比如数据库的统计信息,还包括容器(比如 docker)或者是 host 机器本身的统计信息。监控信息的分级在数据量巨大的时候显得至关重要,信息量大而缺乏组织就是没有信息。通常,有一个主 dashboard,可以快速获知核心组件的健康信息,这个要求在一屏以内,以便可以一眼就得到。其它信息可以在不同的子 dashboard 中展开。
  • 基于监控信息的自动化操作。最常见的例子就是告警。CPU 过高了要告警、IO 过高了要告警、失败次数超过阈值要告警。使用监控工具根据这些信息可以很容易地配置合理的告警规则,要做一个完备的告警系统,规则可以非常复杂。告警和上面说的监控一样,也要分级。小问题自动创建低优先级的问题单,大问题创建高优先级的问题单,紧急问题电话、短信 page oncall。
  • 告警模块的系统化定义和重用。在上面说到这些复杂的需求的时候,如果一切都从头开始做无疑是非常耗时费力的。因而和软件代码需要组织和重构一样,告警的配置和规则也是。

对于其它的工具,比如日志工具,安全工具,审计工具,我这里不多叙述了。这并非是说它们不必须。

糟糕的实践

上面是我的理解,但是结合这些工具,我相信每个有追求的程序员,都对 Ops 的最佳实践有着自己的理解。于是,有一些实践在我看来,是非常糟糕的,它们包括:

  • SSH+命令/脚本。这大概是最糟糕的了,尤其是线上的运维,在实际操作中,一定是最好更相信工具,而不是人。如果没有工具,只能手工操作,只能使用命令+脚本来解决问题,于是各种吓人的误操作就成了催命符。你可以看看 《手滑的故事》,我相信很多人都经历过。最好的避免这样事情发生的方式是什么?限制权限?层层审批?都不是,最好的方式是自动化。人工命令和脚本的依赖程度和 Ops 的成熟度成逆相关。
  • 流程至上。这里我不是否认流程的作用,我的观点在 这篇文章 中已经说过了。其中一个最典型的操作就是堆人,发现问题了,就靠加人,增加一环审批来企图避免问题。
  • 英雄主义。这是很多公司的通病,一个写优质代码的工程师不会起眼,只有埋 bug 造灾难,再挺身而出力挽狂澜,从而拯救线上产品的“英雄”才受人景仰。正所谓,没有困难制造困难也要上。
  • 背锅侠。这和上面的英雄主义正好相反,却又相辅相成。找运维不规范操作背锅(可事实呢,考虑到复杂性、枯燥性等原因,几乎没法“规范”操作,人都是有偷懒和走捷径的本性的),找开发埋地雷,测试漏覆盖背锅。当场批评,事后追责。
  • 用户投诉驱动开发,线上事故驱动开发。这一系列通过糟糕的结果来反向推动的运维反馈开发的方式(其它各种奇葩的驱动开发方式,看 这里)。
  • 把研发的时间精力投入 ops。这是恶性循环最本质的一条, 没时间做好需求分析,没时间做好设计,没时间做好测试,没时间写好代码,什么都没时间,因为全都去 Ops 解线上问题去了 。结果呢,糟糕的上游造就了更糟糕的下游,问题频出,于是更多的人花更多的人去 ops。如此恶性循环……

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 http://bit.ly/2Zv5beC

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 HTTPS 升级

昨晚花了几个钟头,把 blog 的 HTTP 升级成 HTTPS 了,虽然这件事做的晚了一点。为什么要升级,不是我说明的重点,想了解的朋友可以阅读 这篇文章 。我记录的是我升级的过程,踩到的坑。

备份

首先,文章中有许多以 http://www.raychase.net 开头的 URL,比如某些图片和链接,可以把它们改成 https 的,也可以全部改成相对路径,这样的适用性更广。

UPDATE xx_posts SET post_content = REPLACE(post-content, 'http://www.raychase.net', '/');

到浏览器里面访问看看,似乎没有什么问题。

安装

WordPress 管理台

在 Wordress 管理台的设置里面,把本站 URL 中的 http 替换成 https。

证书申请安装

certbot 申请证书,选好了代理和操作系统一个,照着 guide 操作。

wget https://dl.eff.org/certbot-auto
sudo mv certbot-auto /usr/local/bin/certbot-auto
sudo chown root /usr/local/bin/certbot-auto
sudo chmod 0755 /usr/local/bin/certbot-auto

接着自动安装,中途退出了:

sudo /usr/local/bin/certbot-auto --nginx
...
To use Certbot, packages from the EPEL repository need to be installed.
Enable the EPEL repository and try running Certbot again.

EPEL

既然是没有 EPEL,那就安装一个:

sudo yum install epel-release
Loaded plugins: fastestmirror
Setting up Install Process
Loading mirror speeds from cached hostfile
Error: Cannot retrieve metalink for repository: epel. Please verify its path and try again

失败了,从错误中看是 mirror 地址上没法访问到,于是研究了一下,修改 /etc/yum.repos.d/epel.repo 和 /etc/yum.repos.d/epel-testing.repo ,注释掉全部以 mirrorlist= 开始的行,再还原全部以 baseurl= 开始的行。这样就去原始地址,而不是镜像地址下载了。

果然就安装成功了。

Nginx 配置

于是继续刚才失败的操作:

sudo /usr/local/bin/certbot-auto --nginx

挂在了真正安装配置的过程中:

Error while running nginx -c /etc/nginx/nginx.conf -t.
nginx: [emerg] open() "/etc/nginx/nginx.conf" failed (2: No such file or directory)
nginx: configuration file /etc/nginx/nginx.conf test failed

原来是找不到 nginx 的配置文件,因为 nginx 安装的路径并非/etc 下面。于是就干脆建立一个软链接:

ln -s /usr/local/nginx/conf /etc/nginx

这一步过了,结果又挂在了证书 challenge 的过程(challenge 是域名验证的一环,在 这里 有介绍):

Performing the following challenges:
http-01 challenge for www.raychase.net
Waiting for verification...
Challenge failed for domain www.raychase.net

研究一下发现,它需要占用 80 端口,因为这个 challenge 的路径是 http://www.raychase.net/.well-known/acme-challenge/xxxxx,而网站应用已经占了 80,于是把 lnmp 先停掉,再操作。

终于提示成功了,注意到它在 nginx 的配置文件目录下的子目录 vhost 下面生成了一个增量配置文件:www.raychase.net.conf,里面配置了一些 ssl_cewrtificate 之类的 key 的路径,把它放到 nginx 的配置目录里面。

验证

命令行验证

尝试了一下 curl http://bit.ly/2YN6zZB 可以访问,于是就在 SSL Labs 可以验证证书的情况,结果提示失败。

接着在外网使用上述的 curl HTTPS 命令,但是却 timeout,可是 curl http://www.raychase.net,得到了正确的 301 重定向的响应。

首先怀疑 nginx,仔细研究了 nginx 的配置,没发现有什么问题。接着就怀疑防火墙,查看 /etc/sysconfig/iptables 发现可能是防火墙的问题。于是命令行添加规则:

iptables -A INPUT -p tcp -m tcp --dport 443 -j ACCEPT

果然,可以访问了。

再 curl http://www.raychase.net,得到了 301 重定向的响应。

浏览器验证

接着再到浏览器里面访问验证,大致没问题,可是,我注意到访问网站首页的时候,URL 左侧的小图标不是一般 HTTPS 的“锁”的图标,而是一个圈“i”的图标,点击以后可以看到“Your connection to this site is not fully secure”这样的文字。

原来是因为网页上包含了“mixed content”,即有指向当前站的 http 的链接。查看源代码,原来在网站中还有一些其它配置包含有当前站的 http 链接,逐一修复,果然,小锁图标出来了,而文字变成了“Connection is secure”。

改进

HTTP2

在 nginx 中配置打开 http2:

listen 443 ssl http2;

可是在修改完毕,重新加载 nginx 的时候,它提示 http2 不认识,于是就检查了,发现是 nginx 版本太老的原因。

于是使用 yum 来升级,之后提示已经是最新版本了,还是不支持。

原来 yum 的默认 repo 版本还是太老,必须要使用 nginx 自己的 repo。于是增加文件:

/etc/yum.repos.d/nginx.repo

写入:

[nginx]
name=nginx repo
baseurl=http://nginx.org/packages/centos/$releasever/$basearch/
gpgcheck=0
enabled=1

再重启 nginx 就好了。

证书 renew 自动化

证书每几个月就会过期,因此必须自动续上,而不是手动登上服务器来操作。我尝试了一下 renew 证书的过程:

/usr/local/bin/certbot-auto renew

发现又出现了前面 challenge 的过程。当时我停掉了 lnmp,可是我总不能为了续个证书停掉网站吧?于是考虑解决 challenge 的端口冲突问题。发现其实可以用 HTTP 的 80 端口,但是 challenge 的 URI 冲突才是问题的核心。这样问题就好解决了,把导致冲突的 URI 放进来就好了,在 nginx 里面配置:

location /.well-known/acme-challenge/.* {
    proxy_pass http://127.0.0.1:80;
}

接着配置 cron task,使得这个过程自动化:

crontab -e

加入:

0 0 25 * * /usr/local/bin/certbot-auto renew
10 0 25 * * /sbin/service nginx restart

昨天是 25 号,因此我设置成每天的 25 号来尝试 renew。如果证书还远没到期,它会提示“Cert not yet due for renewal”并会退出这个过程,因此这个命令可以安全地运行。

可是我并不知道运行结果啊,总不能每次都登陆上来,跑到/var/log/cron 去看日志吧?

其中一个解决办法是发 email,把运行输出发 email 给我。

Email 通知结果

于是先要配置 ssmtp,编辑/etc/ssmtp/ssmtp.conf:

root=xxx@gmail.com
mailhub=smtp.gmail.com:587
RewriteDomain=gmail.com
Hostname=xxx
FromLineOverride=YES
UseTLS=Yes
UseSTARTTLS=Yes
TLS_CA_File=/etc/pki/tls/certs/ca-bundle.crt
AuthUser=xxx@gmail.com
AuthPass=yyy
AuthMethod=LOGIN

接着把地址信息添加到/etc/ssmtp/revaliases。

我使用的是 Gmail 的 SMTP,为了让 gmail 允许这样的操作,还必须在账户选项的 security 里面,开启 less secure app access 的设置。

搞定以后尝试发一封邮件试试:

echo -n 'test' | sendmail -v raychase1986@gmail.com

没问题!那就可以配置 cron task 让它发邮件了,加上:

MAILTO=RayChase1986@gmail.com

这个变量加上以后,应该就可以自动发邮件了。

crontab 没有立即执行,从而验证的功能,于是为了立即验证,加了一行(每分钟都会执行一次):

* * * * * echo "test"

验证以后把这行删掉就好了。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 http://bit.ly/2HBt6CJ

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 不要让业务牵着鼻子走

这篇文章算是要和之前写的 《程序员懂业务有多重要?》“唱反调”了。

从工作开始,我就不断被灌输着一种业务至上的观点,无论在中国的公司,还是美国的公司,衡量一个决定或者一个需求的价值,都是在业务上有多大的帮助,都说 business impact 是什么。我从不怀疑单纯这样做的初衷,但是我质疑单纯这样做的结果。我觉得,即便是一个业务驱动为主的团队,在决策的时候,技术的占比,应当占据显著的地位。因而我说,不要被业务牵着鼻子走。继续把这一点发扬光大,我认为它对团队发展,对个人发展,都是如此。

曾经认为,这样的观点应该是公认的,但是我越来越发现,事实并不是这样。应该说几乎所有程序员都看到了业务上面的价值,都明白所谓“用技术创造业务价值”的意义,但是其中却有 很多人忘掉了技术的根基,技术是程序员吃饭和安家立命之本,它不只是在实施过程中的一门工具和一种途径,它本身就有着决定项目和产品走向的能力。

自己的经历

我把做的项目,或者写的代码,非常粗略地,可以分为两类:

  • 一种是基于现有代码设施,来写基于业务逻辑的实现,包括新的接口、新的条件分支等等,这种代码被称为“业务代码”;
  • 另一种则是拓展基础设施,实现新的可复用特性,本身不混入业务概念,不直接“变现”,这种代码被称为“非业务代码”。

看起来前者更偏向于业务,而后者更偏向于技术,但是话说回来,在许多场景中,这二者是很难彻底分离开的。有时,要用非业务代码实现某种可被不同业务重用的基础特性,却是由业务驱动的。应该说,硬要分类的话,通常我们遇到的大多数情况,都属于前者。

我在业务和技术的团队中都呆过。在 2008 年的时候,我首先加入的是华为的彩铃团队,写的是彩铃服务端的业务代码,扩展 SOAP 接口和存储过程算是业务为主的代码,但是重新实现的定时任务功能算是用实现业务无关的基础设施。后来在连续几年的和视频平台有关的项目中,做过一个比较小的 service,也做过一个比较大的 portal,专职做过性能优化,由于基本都是重头来做,因此业务和非业务代码都必须涉及,而考虑到我所在的基线团队,以为定制团队提供基础设施为主,因而非业务代码写得更多一点。

在 Amazon 呆的时间比较久,做的东西也比较宽泛,做过 data visualization,big data 的采集和处理,分布式计算,以及分布式的 workflow,还维护过一个 service(更多内容我 在这里 写过)。这些代码一半属于技术代码,而业务的部分主要由团队中的 scientists 和 data analysts 们精通并持续研究,工程师在多数情况下只负责提供好用的工具。(其实这一点分工很难做好,Amazon 是做得相对不错的, 介绍过分工 ,也 吐槽过工具

在 Oracle,所在的大 team 下我也算参与过三个小团队了,一个前端的团队,一个后端 service 的团队,再到现在稳定在这个 distributed workflow 的团队。前两者都属于业务代码远大过非业务代码的团队。事实上,在 OCI(Oracle Cloud Infrastructure)多数团队都是如此,几乎都是业务驱动,所谓的纯技术团队(比如做出 lib 或者 service 这样的基础设施来给其它业务团队使用)比较少。很荣幸的是,目前我在的团队就是如此,我们维护一个 distributed workflow 的 software stack,也维护基于它最主要的 service。

总体来看,最近几年和以前比,所在的团队和参与的项目要更加偏重技术一点,日常工作也相对更有趣一点。

项目的角度

业务驱动可以让你赚钱,但是技术支撑不足的业务驱动,也足以毁掉这个项目,甚至它所属的产品。专注于业务和技术的人眼光是很不同的。 专注于业务的人可以让项目的工作围绕着核心价值和“挣钱”这样直接的目标而工作,但是专注于技术的人才可以让项目踏实并具备长远的可持续发展性。

业务驱动可以让用户得到引导,需求得到满足,但是技术驱动才可以让产品具备稳定性和扩展性这些软件工程层面的要素,从而真正发展起来,而不是三天两头地救火。这也是一个项目,最好具备 TPM 和 Dev 这样两种不同角色的其中一个原因。

在被质问道 business impact 的时候,程序员们一定在心里对技术上的优劣有杆公平的秤。毕竟,有那么多人从业务的角度帮你思考价值的问题,却只有你们自己能从技术的角度考虑和评估。下次再有人质疑有什么业务影响的时候,程序员也可以说,无论 xxx 有没有业务影响,它有着 yyy 的技术影响。

团队的角度

我记得以前说过, 技术并不一定只体现在产品本身,时髦的、有趣的的技术带来的影响力,还能帮助吸引人才。这是技术对团队的影响之一,也恰恰是很多人忽视的一点。 听起来很功利是不是?但是现实就是如此,我记得当时在北京 office 的时候,我们给新员工做宣传说,来我们组吧,我们做大数据,我们做分布式计算,我们做机器学习。我看到有的人眼睛就亮了。事实上,对于这些新员工来说,他们可能并不了解,这些事情并不好做,很多情况下都是苦差事,并且,业务影响可能还不如老老实实做传统业务的团队。

但,那又如何?我知道很多程序员的想法是,不只是完成工作,还想要学到东西,并且向学到那些技术前沿的东西。你不能责怪他们不能立足根本,不能责怪他们好高骛远,这是一个技术人自然而然的追求。最起码,我能看到对方敢于打破舒适区的勇气。

反之,如果一个程序员说,我做什么都可以,我不在乎我加入的团队使用什么技术,做什么不是挣钱吃饭?我反而会觉得这样百适的风格可能意味着没有方向上的品鉴和偏好,没有技术上的追求,也没有学习的动力。我对这样的程序员加入团队,反而感到担忧。

我希望看到团队在技术上的追求和氛围,考虑扩展性、复用性和稳定性等各个方面,争论各种工程层面的解决方案,而不是用业务价值衡量一切。

个人的角度

技术上,需要精进,但是在技术上的投资,总体来说是不容易跑偏的。技术需要持续积累的过程。如果你发现自己每天写的代码无非就是加个接口,写一堆一堆的 if-else 面条式的代码,天天折腾在复杂的业务逻辑里面,而没有什么设计,没有什么技术问题的分析,那我觉得你大概应该需要寻求改变了。如果能在自己的组里面找适合自己的项目可以,如果不行,去寻求外部的团队,甚至其他公司,也是一个选择。

要明确的是,这些业务上的知识,只有少数能够积累下来,积累下来的部分,叫做领域知识。而绝大多数,都没有长期的价值,换言之,到了一个新环境,只有技术的东西是自己的,其他的多数都用不着了。这里不是说业务知识没有用,而是说,多数业务知识,对个人的发展,并不能提供持续的价值。有少部分,或者在确定了领域的基础上,当然是有用的。比如我有长期做 billing 的同事,就有着相当的业务积累,但是,这样的人才也会面临跳槽选择面过窄的问题。

有人说,技术上也一样啊,比如几年前的技术,到现在就淘汰了。MFC 淘汰了,CGI 淘汰了,WAP 淘汰了,我们现在用的技术,很快也要淘汰了,而体力跟不上年轻人,学习速度跟不上刚毕业的年轻人,是不是程序员也要被淘汰了?

我认为,技术是个复杂的事情,不是几个知识点,学会了就搞定一切了。这里有积累,并且技术在变化的过程中,绝大多数内容都是相通的,如果一个老程序员,学习某一项相关新技术的时间,或者掌握的深度,和新程序员一样,那么我会怀疑这个老程序员是不是靠谱。

技术上的积累,并不只是在解决实际问题的时候带来有价值的思路,更能够在学习新技术的时候,可以类比。 在和更年轻的程序员竞争的过程中,老程序员的优势,应当是经验、眼界,而不是体力、反应。这也是为什么不要只写那些纯业务代码的原因 ,同样是写码拿钱,还是很不一样的,写纯业务代码,技术上积累的经验和眼界会偏少,并且照猫画虎实现就可以了,容易废弃掉了人思考的习惯,并且,招个年轻人就可以替代掉你。

如果程序员的你发现自己一直在忙于填充业务代码,不做设计,不做架构,如果自己还不对技术世界那么敏感的话,那么要小心了。如果这都不算“搬砖”,那还有什么是“搬砖”?这样长久的工作,会把自己对于技术的热情慢慢消磨掉。

我们都知道要懂得业务变现的重要性,不要变成迂腐的 nerd,就仿佛那“回字有三种写法”一般,而且似乎这个社会都在这样思考;可是我却说,我们更要看到,只有技术,才是程序员继续充满价值存在的最重要的理由。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 http://bit.ly/2X3pr6d

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 LeetCode 题目解答—— 第 416 到 460 题

从第 416 到第 460 题,跳过了需要付费的题目。付费的题目会单独放在一篇里面。

416 Partition Equal Subset Sum 40.0% Medium
417 Pacific Atlantic Water Flow 36.9% Medium
419 Battleships in a Board 65.2% Medium
420 Strong Password Checker 17.9% Hard
421 Maximum XOR of Two Numbers in an Array 50.5% Medium
423 Reconstruct Original Digits from English 45.4% Medium
424 Longest Repeating Character Replacement 43.8% Medium
427 Construct Quad Tree 55.0% Easy
429 N-ary Tree Level Order Traversal 58.5% Easy
430 Flatten a Multilevel Doubly Linked List 40.9% Medium
432 All O`one Data Structure 29.0% Hard
433 Minimum Genetic Mutation 37.5% Medium
434 Number of Segments in a String 36.7% Easy
435 Non-overlapping Intervals 41.4% Medium
436 Find Right Interval 42.4% Medium
437 Path Sum III 42.1% Easy
438 Find All Anagrams in a String 36.7% Easy
440 K-th Smallest in Lexicographical Order 26.3% Hard
441 Arranging Coins 37.6% Easy
442 Find All Duplicates in an Array 60.1% Medium
443 String Compression 37.0% Easy
445 Add Two Numbers II 49.5% Medium
446 Arithmetic Slices II – Subsequence 29.9% Hard
447 Number of Boomerangs 49.4% Easy
448 Find All Numbers Disappeared in an Array 52.9% Easy
449 Serialize and Deserialize BST 46.1% Medium
450 Delete Node in a BST 39.4% Medium
451 Sort Characters By Frequency 55.8% Medium
452 Minimum Number of Arrows to Burst Balloons 46.2% Medium
453 Minimum Moves to Equal Array Elements 49.1% Easy
454 4Sum II 50.4% Medium
455 Assign Cookies 48.3% Easy
456 132 Pattern 27.4% Medium
457 Circular Array Loop 27.5% Medium
458 Poor Pigs 45.3% Hard
459 Repeated Substring Pattern 39.7% Easy
460 LFU Cache 28.6% Hard

Partition Equal Subset Sum
【题目】Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  1. Each of the array element will not exceed 100.
  2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

【解答】要划分数组成两个部分,这两个部分各自的和相等。
其实这道题可以问 k 个部分,两个部分是一个强化了的条件。整个数组的和(sum)是可以很容易得到的,那么分成两个部分,每个部分的和(sum/2)也就可以很容易得到了。于是这道题就变成了,能不能从数组中找出一些数,使之和为 sum/2?搜索求解即可。

求解期间做一点小优化,创建一个<index, <target, partitionable>> 这样的结构,表示源数组的下标 index 开始往后到底的这一段,能否存在一个子数组,使得和为 target。

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0)
            throw new IllegalArgumentException();
        
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        
        if (total % 2 == 1)
            return false;
        
        int target = total / 2;
        // <index, <target, partitionable>>
        Map<Integer, Map<Integer, Boolean>> cache = new HashMap<>();
        
        return canPartition(nums, cache, target, 0);
    }
    
    private boolean canPartition(int[] nums, Map<Integer, Map<Integer, Boolean>> cache, int target, int index) {
        if (index == nums.length)
            return target == 0;
        
        if (!cache.containsKey(index)) {
            cache.put(index, new HashMap<>());
        }
        Map<Integer, Boolean> subMap = cache.get(index);
        if (subMap.containsKey(target))
            return subMap.get(target);
        
        // current is not selected
        boolean partitionable = canPartition(nums, cache, target, index + 1);
        subMap.put(target, partitionable);
        if (partitionable) {
            subMap.put(target, true);
            return true;
        }
        
        // current is selected
        if (nums[index] <= target) {
            partitionable = canPartition(nums, cache, target - nums[index], index + 1);
        }

        return partitionable;
    }
}

Pacific Atlantic Water Flow
【题目】Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

  1. The order of returned grid coordinates does not matter.
  2. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

【解答】太平洋在左上方,大西洋在右下方,要寻找二者的分界线。

太平洋从最左侧和最上方开始,认为数值不断变大就是可达的,寻找并标记所有可达区域。大西洋则是从最右侧和最下方开始,类似的标记。标记完毕以后找到二者重叠的部分,就是分界线。

class Solution {
    public List<int[]> pacificAtlantic(int[][] matrix) {
        if (matrix == null)
            throw new IllegalArgumentException();
        
        List<int[]> result = new ArrayList<>();
        if (matrix.length==0 || matrix[0].length==0)
            return result;
        
        // null: undetermined, true: reachable, false: unreachable
        Boolean[][] pacificReachable = new Boolean[matrix.length][matrix[0].length];
        Queue pacificQueue = new LinkedList<>();
        // top row
        for (int j=0; j<matrix[0].length; j++) {
            pacificReachable[0][j] = true;
            pacificQueue.offer(new Point(0, j));
        }
        // left column
        for (int i=0; i<matrix.length; i++) {
            pacificReachable[i][0] = true;
            pacificQueue.offer(new Point(i, 0));
        }
        // find all the nodes pacific water flow can reach
        iterate(matrix, pacificQueue, pacificReachable);
        
        Boolean[][] atlanticReachable = new Boolean[matrix.length][matrix[0].length];
        Queue atlanticQueue = new LinkedList<>();
        // bottom row
        for (int j=0; j<matrix[0].length; j++) {
            atlanticReachable[matrix.length-1][j] = true;
            atlanticQueue.offer(new Point(matrix.length-1, j));
        }
        // right column
        for (int i=0; i<matrix.length; i++) {
            atlanticReachable[i][matrix[0].length-1] = true;
            atlanticQueue.offer(new Point(i, matrix[0].length-1));
        }
        iterate(matrix, atlanticQueue, atlanticReachable);
        
        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[0].length; j++) {
                if (pacificReachable[i][j] == Boolean.TRUE && atlanticReachable[i][j] == Boolean.TRUE) {
                    result.add(new int[] {i, j});
                }
            }
        }
        
        return result;
    }
    
    private void iterate(int[][] matrix, Queue queue, Boolean[][] reachable) {
        while (!queue.isEmpty()) {
            Point p = queue.poll();
            
            if (this.mark(matrix, p.x, p.y, p.x-1, p.y, reachable))
                queue.add(new Point(p.x-1, p.y));
            if (this.mark(matrix, p.x, p.y, p.x, p.y-1, reachable))
                queue.add(new Point(p.x, p.y-1));
            if (this.mark(matrix, p.x, p.y, p.x+1, p.y, reachable))
                queue.add(new Point(p.x+1, p.y));
            if (this.mark(matrix, p.x, p.y, p.x, p.y+1, reachable))
                queue.add(new Point(p.x, p.y+1));
        }
    }
    
    private boolean mark(int[][] matrix, int x, int y, int nx, int ny, Boolean[][] reachable) {
        if (nx<0 || ny<0 || nx>=matrix.length || ny>=matrix[0].length || reachable[nx][ny] != null)
            return false;
        
        if (matrix[x][y] <= matrix[nx][ny]) {
            reachable[nx][ny] = true;
            return true;
        }
        
        return false;
    }
}

class Point {
    public int x;
    public int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

Battleships in a Board
【题目】Given an 2D board, count how many battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:

  • You receive a valid board, made of only battleships or empty slots.
  • Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
  • At least one horizontal or vertical cell separates between two battleships – there are no adjacent battleships.

Example:

X..X
...X
...X

In the above board there are 2 battleships.

Invalid Example:

...X
XXXX
...X

This is an invalid board that you will not receive – as battleships will always have a cell separating between them.

Follow up:
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?

【解答】要数有多少 battleship,并且要求使用 O(1) 的空间复杂度,还不能修改 board 上的数值。

一行一行遍历,每一行中从左往右遍历。对于每一个点,如果左侧和上方都不是 X,那就认为这是一艘新的 battleship。

class Solution {
    public int countBattleships(char[][] board) {
        int count = 0;
        
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[0].length; j++) { if (board[i][j]=='.') continue; if (j>0 && board[i][j-1]=='X') continue;
                if (i>0 && board[i-1][j]=='X') continue;
                count++;
            }
        }
        
        return count;
    }
}

Strong Password Checker
【题目】A password is considered strong if below conditions are all met:

  1. It has at least 6 characters and at most 20 characters.
  2. It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
  3. It must NOT contain three repeating characters in a row (“…aaa…” is weak, but “…aa…a…” is strong, assuming other conditions are met).

Write a function strongPasswordChecker(s), that takes a string s as input, and return the MINIMUM change required to make s a strong password. If s is already strong, return 0.

Insertion, deletion or replace of any one character are all considered as one change.

【解答】规则很容易理解:

  1. 6~20 个字符;
  2. 必须包含小写字符、大写字符和数字;
  3. 不能包含连续三个相同字符。

但是困难的地方在于,题目不是问一个字符串是否符合条件,而是要求怎样通过最少的增删改来使得密码符合规则。题目类似于求编辑距离,只不过编辑距离只有一头(源字符串)确定,另一头是不确定的。如果只有一个规则,也会简单一些,三个规则混到一起,互相影响,使得题目非常困难。

挣扎了一段时间,就去讨论区 看解答 去了:

class Solution {
    public int strongPasswordChecker(String s) {
        int res = 0, a = 1, A = 1, d = 1;
        char[] carr = s.toCharArray();
        int[] arr = new int[carr.length];

        for (int i = 0; i < arr.length;) {
            if (Character.isLowerCase(carr[i])) a = 0;
            if (Character.isUpperCase(carr[i])) A = 0;
            if (Character.isDigit(carr[i])) d = 0;

            int j = i;
            while (i < carr.length && carr[i] == carr[j]) i++;
            arr[j] = i - j;
        }

        int total_missing = (a + A + d);

        if (arr.length < 6) {
            res += total_missing + Math.max(0, 6 - (arr.length + total_missing));

        } else {
            int over_len = Math.max(arr.length - 20, 0), left_over = 0;
            res += over_len;

            for (int k = 1; k < 3; k++) {
                for (int i = 0; i < arr.length && over_len > 0; i++) {
                    if (arr[i] < 3 || arr[i] % 3 != (k - 1)) continue;
                    arr[i] -= Math.min(over_len, k);
                    over_len -= k;
                }
            }

            for (int i = 0; i < arr.length; i++) { if (arr[i] >= 3 && over_len > 0) {
                    int need = arr[i] - 2;
                    arr[i] -= over_len;
                    over_len -= need;
                }

                if (arr[i] >= 3) left_over += arr[i] / 3;
            }

            res += Math.max(total_missing, left_over);
        }

        return res;
    }
}

Maximum XOR of Two Numbers in an Array
【题目】Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ ij < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

【解答】要在 O(n) 时间内找两个数 XOR 的最大值。

既然是 O(n) 时间,排序什么的就别想了。拿到手感觉没有什么思路,要去找全部的 XOR 结果暴力解法需要 n 平方的复杂度。再有一点,我觉得可以从高位往低位一位一位去分析,而每一位都是独立的,且优先级有着明确的区别。比如数值部分的最高位在 XOR 能得到 1,总共有 x 种组合,那么在分析次高位的时候,只需要考虑这 x 种中,寻找能够得到 XOR 结果为 1 的即可。但是思路再往下,又不太好继续了。

下面的思路借鉴自 讨论区 的一个解法。现在 Medium 的题目居然也需要看解答了,叹气。

class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for (int i = 31; i >= 0; i--){
            // part 1:
            // prefix mask
            mask = mask | (1 << i);
            // prefix set
            Set set = new HashSet<>();
            for (int num : nums){
                set.add(num & mask);
            }
            
            // part 2:
            int tmp = max | (1 << i);
            for (int prefix : set){
                if(set.contains(tmp ^ prefix)) {
                    max = tmp;
                    break;
                }
            }
        }
        return max;
    }
}

我把思路整理了一下来说明上述代码。求解需要利用一个特性:若 a ^ b = c, a ^ c = b。循环体内的代码说明:

  • part 1:利用 mask 来取所有数的 prefix,第一次一个最高位,第二次为两个最高位,第三次为三个最高位…… 这些 prefix 组成一个 set。
  • part 2:现在假设第 n 次迭代所得到的最大值是 max,那么考虑第 n+1 次迭代:假设新确定的那一位是 1,那么设这个数为 tmp,然后把 tmp 和所有 prefix 进行 XOR 操作,如果得到的数还在这个 prefix set 里面,根据前面提到的特性,说明有两个 prefix 进行 XOR 以后可以得到这个 tmp,那么这个 tmp 就是新的最大值 max,否则这一位只能是 0,那么 max 不变。

Reconstruct Original Digits from English
【题目】Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

  1. Input contains only lowercase English letters.
  2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.
  3. Input length is less than 50,000.

Example 1:

Input: "owoztneoer"

Output: "012"

Example 2:

Input: "fviefuro"

Output: "45"

【解答】要从无序的英文字母串还原到数字。

考虑个数字的英文所包含字母的特性。比如说字母 z,就只可能在 zero 中出现,因此很容易就找到了 zero 的个数。有一些并不是 unique 的,比如 seven,每个字母都可能在别的英文数中出现,但是 s 只能再 six 和 seven 中出现,因此一旦知道了 six,把 s 的次数减去 six 的次数,就可以得到 seven 的次数了。

class Solution {
    public String originalDigits(String s) {
        // unique:
        // zero
        // 'z' => 0
        // two
        // 'w' => 2
        // four
        // 'u' => 4
        // six
        // 'x' => 6
        // eight
        // 'g' => 8
        
        // not unique:
        // seven = 's' - '6'
        // 's' => 7
        // five = 'v' - '7'
        // 'v' => 5
        // one = 'o' - '0' - '2' - '4'
        // 'o' => 1
        // three = 'h' - 8
        // 'h' => 3
        // nine = 'i' - '6' - '8' - '5'
        // 'i' => 9
        
        Map<Character, Integer> countMap = new HashMap<>();
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (!countMap.containsKey(ch))
                countMap.put(ch, 0);
            countMap.put(ch, countMap.get(ch) + 1);
        }
        
        int[] digits = new int[10];
        Integer count = countMap.get('z');
        if (count != null) {
            digits[0] = count;
        }
        count = countMap.get('w');
        if (count != null) {
            digits[2] = count;
        }
        count = countMap.get('u');
        if (count != null) {
            digits[4] = count;
        }
        count = countMap.get('x');
        if (count != null) {
            digits[6] = count;
        }
        count = countMap.get('g');
        if (count != null) {
            digits[8] = count;
        }
        
        count = countMap.get('s');
        if (count != null) {
            digits[7] = count - digits[6];
        }
        count = countMap.get('v');
        if (count != null) {
            digits[5] = count - digits[7];
        }
        count = countMap.get('o');
        if (count != null) {
            digits[1] = count - digits[0] - digits[2] - digits[4];
        }
        count = countMap.get('h');
        if (count != null) {
            digits[3] = count - digits[8];
        }
        count = countMap.get('i');
        if (count != null) {
            digits[9] = count - digits[6] - digits[8] - digits[5];
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<digits.length; i++) {
            for (int j=0; j<digits[i]; j++)
                sb.append(i);
        }
        return sb.toString();
    }
}

Longest Repeating Character Replacement
【题目】Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most ktimes. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string’s length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

【解答】要求在字符串 s 中替换字符 k 次,得到最长的连续字符子串。

如果用回溯法或者动态规划复杂度比较高,而且不好优化。但是,把这个问题转化为一个 sliding window 的问题,一下就豁然开朗了:

  • 假设说有一个 sliding window,从左慢慢往右划,不断调整左右边界:左边吐出 char,右边吃进 char;
  • 这个 window 里面的不同 char 各有多少个,通过一个 map 来记录;
  • 这个 window 的左边界所对应的 char 作为所考察的 repeating char,在左边界固定的基础上不断右移右边界,记录 window 的最大值,如果其他 char 的数量超过了 k,那么需要右移左边界,吐出一个之前的 repeating char。

这类字符串寻找连续子串的问题,都可以考虑 sliding window 的方法。使用 sliding window 的一个好处有这么两个:

  1. 窗口内字符排列或数量增量变化。无论移动左侧还是右侧窗口边沿,都只变化一个字符。
  2. 窗口的左侧或者右侧固定,从而简化问题。像这道题就是总是考虑窗口左侧的 char 为 repeating char。
class Solution {
    public int characterReplacement(String s, int k) {
        if (s==null || k<0)
            throw new IllegalArgumentException();
        if (s.length()==0)
            return 0;
        
        int left=0, right=0;
        int max = 1;
        
        char[] counters = new char[26];
        counters[s.charAt(0) - 'A']++;
        
        while (right<s.length()) {
            int base = s.charAt(left) - 'A';
            int replacementCount = 0;
            for (int i=0; i<26; i++) {
                if (i!=base) {
                    replacementCount += counters[i];
                }
            }
            
            if (replacementCount>k) {
                counters[base]--;
                left++;
            } else {
                int newSize = right-left+1;
                max = Math.max(max, newSize);
                right++;
                if (right<s.length()) {
                    counters[s.charAt(right) - 'A']++;
                } else {
                    // special case: there are still change chances left
                    max = Math.max(max, newSize + k - replacementCount);
                }
            }
        }
        
        // never exceeds the length of s
        return Math.min(max, s.length());
    }
}

Construct Quad Tree
【题目】We want to use quad trees to store an N x N boolean grid. Each cell in the grid can only be true or false. The root node represents the whole grid. For each node, it will be subdivided into four children nodes until the values in the region it represents are all the same.

Each node has another two boolean attributes : isLeaf and valisLeaf is true if and only if the node is a leaf node. The val attribute for a leaf node contains the value of the region it represents.

Your task is to use a quad tree to represent a given grid. The following example may help you understand the problem better:

Given the 8 x 8 grid below, we want to construct the corresponding quad tree:

It can be divided according to the definition above:

 

The corresponding quad tree should be as following, where each node is represented as a (isLeaf, val) pair.

For the non-leaf nodes, val can be arbitrary, so it is represented as *.

Note:

  1. N is less than 1000 and guaranteened to be a power of 2.
  2. If you want to know more about the quad tree, you can refer to its wiki.

【解答】构造 Quad Tree。

没有太多可以说的。递归判断并合并节点,形成 quad tree。

class Solution {
    public Node construct(int[][] grid) {
        if (grid==null || grid.length==0 || grid.length!=grid[0].length)
            throw new IllegalArgumentException();
        
        return this.construct(grid, 0, 0, grid.length);
    }
    
    private Node construct(int[][] grid, int x, int y, int w) {
        if (w==1) {
            return new Node(grid[x][y]!=0, true, null, null, null, null);
        }
        
        Node topLeft = this.construct(grid, x, y, w/2);
        Node topRight = this.construct(grid, x, y+w/2, w/2);
        Node bottomLeft = this.construct(grid, x+w/2, y, w/2);
        Node bottomRight = this.construct(grid, x+w/2, y+w/2, w/2);
        
        // all leaves and equal, merge
        if (topLeft.isLeaf &&
            topRight.isLeaf &&
            bottomLeft.isLeaf &&
            bottomRight.isLeaf &&
            topLeft.val == topRight.val &&
            topLeft.val == bottomLeft.val &&
            topLeft.val == bottomRight.val
        ) {
            return new Node(topLeft.val, true, null, null, null, null);
        }
        
        // otherwise create a sub tree
        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}

N-ary Tree Level Order Traversal
【题目】

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example, given a 3-ary tree:

We should return its level order traversal:

[
     [1],
     [3,2,4],
     [5,6]
]

Note:

  1. The depth of the tree is at most 1000.
  2. The total number of nodes is at most 5000.

【解答】没有太多可以说的。循环内按层遍历就好。

class Solution {
    public List<List> levelOrder(Node root) {
        List<List> result = new ArrayList<>();
        if (root==null)
            return result;
        
        Queue level = new LinkedList<>();
        level.add(root);
        while (!level.isEmpty()) {
            Queue nextLevel = new LinkedList<>();
            List list = new ArrayList<>();
            for (Node node : level) {
                list.add(node.val);
                if (node.children != null)
                    nextLevel.addAll(node.children);
            }
            result.add(list);
            level = nextLevel;
        }
        
        return result;
    }
}

Flatten a Multilevel Doubly Linked List
【题目】You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example:

Input:
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL
Output:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

Explanation for the above example:

Given the following multilevel doubly linked list:

We should return the following flattened doubly linked list:

【解答】要把多层的双向链表压平。
大致思路上应该说没有什么难的,但是细节处理的坑比较多。源链表节点的 next 始终要放到 stack 里面去,然后再看 child,如果 child 不为空,直接从 stack 里面取下一个节点;如果为空,则优先使用 child 为下一个节点。
在选中下一个节点之后,再重新链接的过程中,注意覆盖节点的所有 field,包括 next、prev、child。

class Solution {
    public Node flatten(Node head) {
        if (head==null)
            return null;
        
        Stack stack = new Stack<>();
        Node cur = head;
        while (true) {
            // always push the next node to stack
            if (cur.next != null)
                stack.push(cur.next);

            Node next = cur.child;
            if (next == null) {
                // make child as the next, but if child is null, pop the next from stack
                if (!stack.isEmpty()) {
                    next = stack.pop();
                } else {
                    cur.child = null;
                    cur.next = null;
                    break;
                }
            }
            
            // link current to next
            cur.child = null;
            next.prev = cur;
            cur.next = next;
            
            cur = next;
        }
        
        return head;
    }
}

All O`one Data Structure
【题目】Implement a data structure supporting the following operations:

  1. Inc(Key) – Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
  2. Dec(Key) – If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
  3. GetMaxKey() – Returns one of the keys with maximal value. If no element exists, return an empty string "".
  4. GetMinKey() – Returns one of the keys with minimal value. If no element exists, return an empty string "".

Challenge: Perform all these in O(1) time complexity.

【解答】实现一个数据结构,加一、减一,获取最大值的 key 和最小值的 key,都是 O(1) 的时间复杂度。

这类题目可以说遇到多次了,有一些通用思路:

  • 要 O(1),根据 key 去取 value 的,无非就两种数据结构,一个是 HashMap,一个是数组(下标访问)。
  • 如果有根据 key 取 value,那就需要从 key 到 value 的映射;如果有根据 value 取 key,那就需要 value 到 key 的映射。
  • 这道题看起来需要两者:
    • 根据 key 要获取 value 对象,从而进行 inc 和 dec 的操作;
    • 根据 value 的大小情况,来找到对象并返回相应的 key。
  • 要能 O(1) 得到最大值和最小值,肯定不能在需要的时候去现找,那就需要在平时维护一个有序列表,一头最大,一头最小。这个列表的大小比较实际只靠 value,具体这个 value 有多少个 key 对应并不重要。因而这个序号并不是 key 根据 value 的值实际的序号,而是互不重复的 value 进行比较得到的序号。
  • 在 inc 和 dec 的时候,由于变化只有 1,位置调整于是也只有 1。这就是为什么要根据互不重复的 value 来排序的原因,这样的情况一定能保证调整的幅度不超过 1。

有了这样的思路以后,建立一个 Item 元素,作为 value,里面需要存放前一个节点、后一个节点,实际取值,以及 key set。这里的前一个、后一个节点是用来保序用的。建立的 head 和 tail 是用于包住 value 形成的有序串,简化计算用的。

class Item {
    public int value;
    public Item next;
    public Item prev;
    public Set keys = new HashSet<>();;
}
class AllOne {
    
    private Map<String, Item> map = new HashMap<>();
    private Item head = new Item();
    private Item tail = new Item();
    

    /** Initialize your data structure here. */
    public AllOne() {
        this.head.next = this.tail;
        this.tail.prev = this.head;
        // dummy head and dummy tail
        this.head.value = Integer.MIN_VALUE;
        this.tail.value = Integer.MAX_VALUE;
    }
    
    private void link(Item left, Item right) {
        left.next = right;
        right.prev = left;
    } 
    
    /** Inserts a new key  with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        Item currentItem = this.map.get(key);
        if (currentItem != null) { // it's an existing key
            currentItem.keys.remove(key);
            int newValue = currentItem.value + 1;
            Item next = currentItem.next;
            if (next.value == newValue) {
                // the item for the newValue is already existed
                map.put(key, next);
                next.keys.add(key);
            } else {
                // there is no item for newValue, create one
                Item newItem = new Item();
                newItem.value = newValue;
                newItem.keys.add(key);
                
                this.link(currentItem, newItem);
                this.link(newItem, next);
                
                map.put(key, newItem);
            }
            
            // remove the node if there's no key mapped to its value
            if (currentItem.keys.isEmpty()) {
                this.link(currentItem.prev, currentItem.next);
            }
        } else { // it's a new key
            if (this.head.next.value == 1) {
                // the item for new key (value==1) is already existed
                this.head.next.keys.add(key);
                map.put(key, this.head.next);
            } else {
                // new item needed
                Item next = this.head.next;
                Item newItem = new Item();
                newItem.value = 1;
                newItem.keys.add(key);
                
                this.link(this.head, newItem);
                this.link(newItem, next);
                
                map.put(key, newItem);
            }
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        Item currentItem = this.map.get(key);
        if (currentItem == null)
            return;
        
        Item prev = currentItem.prev;
        currentItem.keys.remove(key);
        // remove the item if no key mapped to it
        if (currentItem.keys.isEmpty()) {
            this.link(prev, currentItem.next);
        }

        if (currentItem.value == 1) {
            this.map.remove(key);
            return;
        }
        
        int newValue = currentItem.value - 1;
        // there's already an item existed for newValue
        if (prev.value == newValue) {
            prev.keys.add(key);
            this.map.put(key, prev);
            return;
        }
        
        // there is no item for newValue, create one
        Item newItem = new Item();
        newItem.value = newValue;
        newItem.keys.add(key);

        Item next = prev.next;
        this.link(prev, newItem);
        this.link(newItem, next);

        map.put(key, newItem);    
    }
    
    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        if (this.head.next == this.tail)
            return "";
        return this.tail.prev.keys.iterator().next();
    }
    
    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        if (this.head.next == this.tail)
            return "";
        return this.head.next.keys.iterator().next();
    }
}

Minimum Genetic Mutation
【题目】A gene string can be represented by an 8-character long string, with choices from "A""C""G""T".

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things – start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

  1. Starting point is assumed to be valid, so it might not be included in the bank.
  2. If multiple mutations are needed, all mutations during in the sequence must be valid.
  3. You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3

【解答】维护一个当前考察的字符串集合和一个字典,每次都拿当前字符串去和字典里的所有候选字符串比较,如果只差 1,就把候选从字典里面拿出来,更新到当前考察的字符串集合中。直到发现解,或者字典为空,或者在最近一次比较中没有发现任何匹配,就表示算法已经结束。

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        if (start==null || end==null || bank==null)
            throw new IllegalArgumentException();
        if (start.equals(end))
            return 0;
        if (start.length() != end.length() || bank.length==0)
            return -1;
        
        Set bankSet = new HashSet<>(Arrays.asList(bank));
        Set current = new HashSet<>();
        current.add(start);
        
        int count = 0;
        while (!current.isEmpty() && !bankSet.isEmpty()) {
            count++;
            Set newCurrent = new HashSet<>();
            for (String cur : current) {
                Set newBank = new HashSet<>();
                for (String b : bankSet) {
                    if (this.diffOne(cur, b)) {
                        if (b.equals(end))
                            return count;
                        else
                            newCurrent.add(b);
                    } else {
                        newBank.add(b);
                    }
                }
                bankSet = newBank;
            }
            current = newCurrent;
        }
        
        return -1;
    }
    
    private boolean diffOne(String left, String right) {
        if (left.length() != right.length())
            return false;
        
        boolean changed = false;
        for (int i=0; i<left.length(); i++) {
            if (left.charAt(i) != right.charAt(i)) {
                if (changed)
                    return false;
                else
                    changed = true;
            }
        }
        
        return true;
    }
}

Number of Segments in a String
【题目】Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

Input: "Hello, my name is John"
Output: 5

【解答】常规题。没有太多可说的,注意一些特殊 case 是否被覆盖到,比如首尾空格。

class Solution {
    public int countSegments(String s) {
        boolean isSpace = true;
        int count = 0;
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (ch!=' ' && isSpace) {
                isSpace = false;
            } else if (ch==' ' && !isSpace) {
                count++;
                isSpace = true;
            }
        }
        
        if (!isSpace)
            count++;
        
        return count;
    }
}

Non-overlapping Intervals
【题目】Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

  1. You may assume the interval’s end point is always bigger than its start point.
  2. Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

【解答】要求去掉最少的 interval 使得剩余的 interval 无重叠。

一开始,觉得这道题应该比较简单,扫描线问题嘛。上来先排序,完毕之后从左往右扫一遍——这也算是常规思路了。于是我把 intervals 按照 start 排序,然后尝试从中拿掉某些。结果超时了,于是使用一个二维数组优化,内存使用又超了:

class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator(){
            @Override
            public int compare(Interval left, Interval right) {
                if (left.start != right.start)
                    return left.start - right.start;
                // this is to make sure when start is same, we can always remove the left one and keep the right one as the right one is shorter
                return right.end - left.end;
            }
        });
        
        Integer[][] cache = new Integer[intervals.length][intervals.length];
        return this.cal(intervals, 0, -1, cache);
    }
    
    private int cal(Interval[] intervals, int index, int last, Integer[][] cache) {
        if (index >= intervals.length)
            return 0;
        
        if (last!=-1 && cache[index][last] != null)
            return cache[index][last];
        
        int count = 0;
        for (int i=index; i<intervals.length; i++) {
            Interval interval = intervals[i];
            
            if (last==-1) {
                last = i;
            } else if (intervals[last].start == interval.start) {
                count++;
                last = i;
            } else if (intervals[last].end <= interval.start) {
                // no overlapping
                last = i;
            } else {
                // it's the most complicated case as we don't know which should be removed: "last" or "i"
                int c1 = this.cal(intervals, i+1, last, cache);
                int c2 = this.cal(intervals, i+1, i, cache);
                count++;
                count += Math.min(c1, c2);
                break;
            }
        }
        
        cache[index][last] = count;
        return count;
    }
}

现在换一个角度,反过来想,如果是从零开始,找尽量多的无重叠 interval 呢?把搜索问题变成构造问题。

考虑排序,可根据什么排呢?二者是很不一样的。用 end 来排序,而不是 start:

  • 如果按照 start 排序,从左到右扫描的过程中,start 大或者小并不代表该 interval 是否应该被选中,因为需要考虑几个重叠 interval 之间覆盖的竞争关系。对右侧的 interval 来说,和不同的左侧 interval 产生重叠,但 start 更大不代表这个重叠范围更大或者更小。因此单纯按照 start 排序没有意义。
  • 而如果按照 end 排序,从小到大扫描的时候,只要发现重叠就只需要忽略后扫描到的,而根本不需要考虑 start 在哪里。因为对于右侧的 interval 来说,左侧元素的 start 在哪里不重要,重要的是 end 在哪里,end 才是决定了重叠部分右边界位置的因素。我们当然希望这个右边界越靠左越好,因此我们在扫描的过程中,尽可能留下先遇到的 end。
class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator(){
            @Override
            public int compare(Interval left, Interval right) {
                return left.end - right.end;
            }
        });
        
        int count = 0;
        Interval last = null;
        for (Interval interval : intervals) {
            // intervals are sorted by "end"
            if (last==null || interval.start >= last.end) {
                last = interval;
                count++;
            }
        }
        
        return intervals.length - count;
    }
}

Find Right Interval
【题目】Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

  1. You may assume the interval’s end point is always bigger than its start point.
  2. You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

【解答】对于每个 interval,要找有多少 interval 在它的右边。

肯定不能死算。仔细想一下,其实对每个 interval 我只关心它的右边界,和剩余所有 interval 的左边界。

如果它的右边界确定的时候,要找所有比它小的左边界,这就是一个典型的使用 TreeMap 的问题——key 是所有 interval 的左边界;value 是源数组中的 index。

class Solution {
    public int[] findRightInterval(Interval[] intervals) {
        if (intervals == null)
            throw new IllegalArgumentException();
        
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i=0; i<intervals.length; i++) {
            Interval interval = intervals[i];
            map.put(interval.start, i);
        }
        
        int[] result = new int[intervals.length];
        for (int i=0; i<intervals.length; i++) {
            Interval interval = intervals[i];
            Map.Entry<Integer, Integer> entry = map.ceilingEntry(interval.end);
            if (entry==null)
                result[i] = -1;
            else
                result[i] = entry.getValue();
        }
        
        return result;
    }
}

Path Sum III
【题目】You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

【解答】递归求解。但是在递归的过程中,不需要记录每个解分别是由那几个数累加起来的,但是需要记录都可以得到哪些和,不需要去重。因为不同的节点加起来可以得到同样的和,但是实际是算作不同的解。

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root==null) return 0;
        return travel(root, new ArrayList<>(), sum);
    }
    
    private int travel(TreeNode root, List list, int sum) {
        if (root==null) return 0;
        
        int total = 0;
        if (root.val == sum) total++;
        
        List newList = new ArrayList<>();
        newList.add(root.val);
        for (int num : list) {
            int added = num + root.val;
            newList.add(added);
            if (added==sum) total++;
        }
        
        int left = travel(root.left, newList, sum);
        int right = travel(root.right, newList, sum);
        
        total += left;
        total += right;
        
        return total;
    }
}

Find All Anagrams in a String
【题目】Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

【解答】要找成为 anagram 的子串,基本上最直接的方法就是使用滑动窗口了。而且是个固定大小的滑动窗口。我当时的做法不是特别好,虽然也解出来了,但没有充分利用固定大小这个特性,于是代码写得有些啰嗦。

class Solution {
    private void updateMap(Map<Character, Integer> charMap, char ch, int count) {
        if (count==0)
            charMap.remove(ch);
        else
            charMap.put(ch, count);
    }
    
    public List findAnagrams(String s, String p) {
        if (s==null || p==null || p.length()==0)
            throw new IllegalArgumentException();
        
        List result = new ArrayList<>();
        if (s.length()==0)
            return result;
        
        Map<Character, Integer> charMap = new HashMap<>();
        for (int i=0; i<p.length(); i++) {
            char ch = p.charAt(i);
            int count = charMap.getOrDefault(ch, 0);
            charMap.put(ch, ++count);
        }
        
        int left=0, right=0;
        while (right<s.length()) {
            // always load s[right] at the beginning of each iteration
            char cr = s.charAt(right);
            int count = charMap.getOrDefault(cr, 0) - 1;
            this.updateMap(charMap, cr, count);
            
            // anagram found
            if (charMap.isEmpty()) {
                result.add(left);
                // move both boundaries
                charMap.put(s.charAt(left), 1);
                left++;
                right++;
                continue;
            }
            
            // now try moving left only, and break the loop when:
            // the amount of cr is matched, or left moves beyond right (no matches found)
            while (charMap.getOrDefault(cr, 0)==-1 && left<=right) {
                char cl = s.charAt(left++);
                count = charMap.getOrDefault(cl, 0) + 1;
                this.updateMap(charMap, cl, count);
            }
            
            right++;
        }
        
        return result;
    }
}

K-th Smallest in Lexicographical Order
【题目】Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.

Note: 1 ≤ k ≤ n ≤ 109.

Example:

Input:
n: 13   k: 2

Output:
10

Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

【解答】要找从 1 到 n 这连续的数中,第 k 小的那一个。

老实说,这一类题我是不太擅长做的。尝试了几种思路都没有发现特别好的解法。在讨论区我找到了我认为 最清晰的解法 ,而且这种解法对于类似的这种问题有一定启发意义。大致思路是使用引入十叉数,因为每一个数字的后面,最多可能有从 0 到 9 这十个可能。于是从根往叶子方向一层一层遍历,直到找到第 k 个数为止。

class Solution {
    public int findKthNumber(int n, int k) {
        int curr = 1;
        k = k - 1;
        while (k > 0) {
            int steps = calSteps(n, curr, curr + 1);
            if (steps <= k) {
                curr += 1;
                k -= steps;
            } else {
                curr *= 10;
                k -= 1;
            }
        }
        return curr;
    }
    
    /**
     * how many steps from n1 to n2
     */
    public int calSteps(int n, long n1, long n2) {
        int steps = 0;
        while (n1 <= n) {
            steps += Math.min(n + 1, n2) - n1;
            n1 *= 10;
            n2 *= 10;
        }
        return steps;
    }
}

说明,从根节点开始往下一层一次统计,curr 指向当前节点,如果 curr 和 curr+1 之间的 steps 小于 k,那 curr 就在当前层前进;否则,curr 下潜到下一层去,这种情况下 k 需要-1 因为原节点已经遍历过了。

关于 steps 的计算(calSteps):考虑边界情况,n2 和 n+1 二者中小的那个区减掉 n1,这里的+1 主要是考虑要把 n 这个数也算进去。

Arranging Coins
【题目】You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

【解答】要求硬币组成的楼梯形状的层数,不完整的层要舍弃。

我觉得是一个数学问题。第一层是有 1 枚硬币,第 x 层最多有 x 枚,等差数列,那么最多一共有 (1+x)*x/2 枚,这个数必须要大于等于 n,这是个一元二次方程,拿求根公式解一下就好。

class Solution {
    public int arrangeCoins(int n) {
        // (1 + x) * x / 2 >= n
        // so x^2 + x - 2n >= 0
        // [-b±(b^2-4ac)^(1/2)]/(2a)
        // avoid overflow
        double result = (-1 + Math.sqrt(1 - 4*(-2*(double)n))) / 2;
        return (int) result;
    }
}

Find All Duplicates in an Array
【题目】Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

【解答】要从大小为 1~n 的长度为 n 数组中找出出现了两次的数,而且要 O(1) 的空间和 O(n) 的时间复杂度,这就意味着一般的搜索和排序之类方法的都可以靠边站了 。
利用这些数范围的特性,在找一个数的时候,把这个数 x 减去 1 作为一个 index,让数组在该 index 上的数取负数,如果发现该数已经是负数了,那就说明这个数 x 就是重复的数。

class Solution {
    public List findDuplicates(int[] nums) {
        if (null==nums)
            throw new IllegalArgumentException();
        
        // to save as much space as possible LinkedList is used, not ArrayList
        List result = new LinkedList<>();
        for (int i=0; i<nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index]<0) { // if it's already <0 this is the second time to be hit
                result.add(index + 1);
            } else {
                nums[index] = -nums[index];
            }
        }
        
        return result;
    }
}

String Compression
【题目】Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:

  1. All characters have an ASCII value in [35, 126].
  2. 1 <= len(chars) <= 1000.

【解答】字符串压缩。快慢双指针方式求解。

class Solution {
    public int compress(char[] chars) {
        if (chars==null)
            throw new IllegalArgumentException();
        if (chars.length==0)
            return 0;
        
        // slow / fast: the star/end of the consecutive sub char array
        // recording: the pointer recording char + number
        int slow=0, fast=0, recording=0;
        while (slow<chars.length) {
            if (fast==chars.length || chars[fast]!=chars[slow]) {
                // recording always starts with the char
                chars[recording++] = chars[slow];
                
                if (fast-slow > 1) {
                    String num = "" + (fast-slow);
                    for (char n : num.toCharArray())
                        chars[recording++] = n;
                }
                slow = fast;
            }
            
            fast++;
        }
        
        return recording;
    }
}

Add Two Numbers II
【题目】You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

【解答】两个用链表表示的数相加。常规操作,包括 fake/dummy head,进位符号的处理等等。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1==null || l2==null)
            throw new IllegalArgumentException();
        
        Stack s1 = new Stack<>();
        Stack s2 = new Stack<>();
        
        ListNode cur = l1;
        while (cur!=null) {
            s1.push(cur);
            cur = cur.next;
        }
        cur = l2;
        while (cur!=null) {
            s2.push(cur);
            cur = cur.next;
        }
        
        Stack res = new Stack<>();
        boolean carry = false;
        while (!s1.isEmpty() || !s2.isEmpty()) {
            ListNode l = s1.isEmpty() ? null : s1.pop();
            ListNode r = s2.isEmpty() ? null : s2.pop();
            int lv = l==null ? 0 : l.val;
            int rv = r==null ? 0 : r.val;
            int sum = lv + rv;
            if (carry)
                sum++;
            
            if (sum>=10) {
                sum -= 10;
                carry = true;
            } else {
                carry = false;
            }
            
            res.push(new ListNode(sum));
        }
        if (carry)
            res.push(new ListNode(1));
        
        ListNode dummyHead = new ListNode(0);
        cur = dummyHead;
        while (!res.isEmpty()) {
            cur.next = res.pop();
            cur = cur.next;
        }
        
        return dummyHead.next;
    }
}

Arithmetic Slices II – Subsequence
【题目】A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, …, Pk) such that 0 ≤ P0 < P1 < … < Pk < N.

subsequence slice (P0, P1, …, Pk) of array A is called arithmetic if the sequence A[P0], A[P1], …, A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.

Example:

Input: [2, 4, 6, 8, 10]

Output: 7

Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

【解答】我最开始的思路是动态规划,划分成子问题。每个子问题是:

对于所有从 index 为 i 开始的 subsequence,在 interval 是 k 的情况下,解集用 c[i][k] 来表示,这个解集合我不需要知道具体内容,但我需要知道每个 subsequence 在包含特定个元素个数 p 的情况下个有多少种可能。那么对于一个新的 index j 且 j<i,考察 A[j] 和 A[i]:
A[j]-A[i] 为新的 interval,寻求解集 c[j][A[j]-A[i]]。看起来这个方法似乎是可以走得通的,但是明显无论从实现层面还是时间复杂度层面都过高了。为了缓存已得到的结果,我需要建立一个这样的数据结构来避开重复计算:Map<Integer, Map<Integer, Map<Integer, Integer>>>,含义是:<start_index, <interval, <sub_seq_len, count>>。因此这是一个三维的动态规划,我们一般只做一维到二维,而三维的话一般有更好的解决办法。[后记:其实第三维 sub_seq_len 应该是不需要的,当时的想法有点问题。]

下面的解答来自 讨论区 。简单思路:

  • 对于任意 0<=j<i<A.length, A[j] 和 A[i] 之间的差是 d,那么:map[i][d] 表示:以 A[i] 结尾的这些 subsequence 且元素两两差值为 d 的情况下,这样的这些 subsequence 有多少个。
  • 这样在每次迭代中,先对于当前的元素 A[i] 拿到当前的值 c1=map[i][d],再看它前面的元素 A[j],拿到它的值 c2=map[j][d],对于 map[i][d] 来说,新的值就是 c1+c2+1,这里面的“+1”是因为这个新的这些 subsequence:A[j],A[i];
  • 在考虑总数的时候,每次都把 c2 加进去,因为 c2 来自于前一个元素 A[j] 的统计,这些 subsequence 们最少也有两个元素,现在各自再加上一个 A[i] 就都成为了合法的结果(至少三个元素)。
class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        if (A==null)
            throw new IllegalArgumentException();
        
        int res = 0;
        Map<Integer, Integer>[] map = new Map[A.length];

        for (int i = 0; i < A.length; i++) {
            map[i] = new HashMap<>(i);

            for (int j = 0; j < i; j++) {
                long diff = (long)A[i] - A[j];
                if (diff <= Integer.MIN_VALUE || diff > Integer.MAX_VALUE) continue;

                int d = (int)diff;
                int c1 = map[i].getOrDefault(d, 0);
                int c2 = map[j].getOrDefault(d, 0);
                res += c2;
                map[i].put(d, c1 + c2 + 1);
            }
        }

        return res;
    }
}

Number of Boomerangs
【题目】Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

【解答】i 到 j 的距离必须等于 i 到 k 的距离。

基本思路很简单,遍历每一个点,并以之为 i,再以它到所有其他点距离的平方为 key,放到 map 里面去,value 为统计该距离出现的次数。

之后对于 map 中的每组 entry,value 的个数就表示了在选定 i 的情况下,有多少组距离相等,如果它是 x 的话,那么 x*(x-1) 就意味着有多少种组合。(我在注释里面列出了排列组合的两个基本公式,也是它的本质由来)

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if (points==null)
            throw new IllegalArgumentException();
        
        int total = 0;
        for (int i=0; i<points.length; i++) {
            int[] point = points[i];
            // point is chosen as the center (first element of the tri-tuple)
            // key: distance^2, value: count
            Map<Integer, Integer> map = new HashMap<>();
            for (int j=0; j<points.length; j++) {
                int[] p = points[j];
                if (point==p)
                    continue;
                
                int distance = (int) (Math.pow(point[0]-p[0], 2) + Math.pow(point[1]-p[1], 2));
                int count = map.getOrDefault(distance, 0);
                map.put(distance, ++count);
            }
            
            for (int count : map.values())
                total += this.perm(count);
        }
        
        return total;
    }
    
    // Permutation: P(m, n) = n! / (n-m)!
    // Combination: C(m, n) = P(m, n) / m! = n! / ((n-m)!*m!)
    private int perm(int count) {
        // here m=2, so C(m, n) = n * (n-1);
        return count * (count-1);
    }
}

Find All Numbers Disappeared in an Array
【题目】Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

【解答】应该算是常规题了。把每个数都尝试换到它应该去的位置,完毕之后,扫一遍看哪些位置上的数和 index 不匹配(index 应当等于 n-1)。

class Solution {
    public List findDisappearedNumbers(int[] nums) {
        if (nums==null)
            throw new IllegalArgumentException();
        
        int i=0;
        while (i<nums.length) {
            int currentVal = nums[i];
            int indexShouldBe = nums[i]-1;
            if (indexShouldBe != i) {
                if (nums[indexShouldBe] != currentVal) {
                    swap(nums, i, indexShouldBe);
                    continue;
                }
            }
            
            i++;
        }
        
        List result = new ArrayList<>();
        for (i=0; i<nums.length; i++) {
            if (nums[i]-1 != i)
                result.add(i+1);
        }
        
        return result;
    }
    
    private void swap(int[] nums, int i, int j) {
        if (i==j)
            return;
        
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Serialize and Deserialize BST
【题目】Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

【解答】要把一棵 BST 序列化和反序列化。

应该说有很多做法。我的做法是把根放在序列化后字符串的头部,然后是递归得到的左子树串,再是右子树串。这样一来,反序列化的时候,字符串的第一个字符总是根,后面的字符只要比它小就是左子树,再往后就是右子树。

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root==null)
            return "";
        
        // pre-order traversal
        String result = "" + root.val;
        if (root.left!=null)
            result += "," + serialize(root.left);
        if (root.right!=null)
            result += "," + serialize(root.right);
        
        return result;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.length()==0)
            return null;
        
        String[] arr = data.split(",");
        int[] tokens = new int[arr.length];
        for (int i=0; i<arr.length; i++)
            tokens[i] = Integer.parseInt(arr[i]);
        return deserialize(tokens, 0, tokens.length-1);
    }
    
    private TreeNode deserialize(int[] tokens, int start, int end) {
        TreeNode root = new TreeNode(tokens[start]);
        Integer left = null;
        Integer right = null;
        for (int i=start+1; i<=end; i++) {
            if (tokens[i]root.val && right==null) {
                right = i;
                break;
            }
        }
        
        if (left!=null)
            root.left = right==null ? deserialize(tokens, left, end) : deserialize(tokens, left, right-1);
        if (right!=null)
            root.right = deserialize(tokens, right, end);
        
        return root;
    }
}

Delete Node in a BST
【题目】Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.
  2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

【解答】要从一棵 BST 上面删除一个节点。分成几种情况考虑:

如果要删除的节点在左子树,递归调用左子树;

右子树同理;

最麻烦的是删除根节点,删掉了之后,如果原本有左子树,那就从左子树取最大的节点放到根上;反之,从右子树取最小的节点放到根上(不需要实际的节点替换,替换节点的数值即可)。

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root==null) return null;
        if (key<root.val) {
            root.left = this.deleteNode(root.left, key);
            return root;
        }
        if (key>root.val) {
            root.right = this.deleteNode(root.right, key);
            return root;
        }
        if (root.left==null && root.right==null) return null;
        if (root.left==null) return root.right;
        if (root.right==null) return root.left;
        
        TreeNode smallest = this.getSmallest(root.right);
        root.val = smallest.val;
        root.right = deleteNode(root.right, smallest.val);
        return root;
    }
    
    private TreeNode getSmallest(TreeNode node){
        while(node.left != null){
            node = node.left;
        }
        return node;
    }
}

Sort Characters By Frequency
【题目】Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

【解答】按照字符的出现频率排序。常规题目,使用一个 map 来统计次数,然后实现比较接口来排序。

class Solution {
    public String frequencySort(String s) {
        if (s==null) throw new IllegalArgumentException();
        
        Map<Character, Item> map = new HashMap<>();
        List list = new ArrayList<>();
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (!map.containsKey(ch)) {
                Item item = new Item(ch, 1);
                map.put(ch, item);
                list.add(item);
            } else {
                Item item = map.get(ch);
                item.count = item.count + 1;
            }
        }
        
        Collections.sort(list);
        StringBuilder sb = new StringBuilder();
        for (Item item : list) {
            for (int i=1; i<=item.count; i++) {
                sb.append(item.ch);
            }
        }
        return sb.toString();
    }
}

class Item implements Comparable {
    public char ch;
    public int count;
    
    public Item(char ch, int count) {
        this.ch = ch;
        this.count = count;
    }
    
    @Override
    public int compareTo(Item that) {
        return that.count - this.count;
    }
}

Minimum Number of Arrows to Burst Balloons
【题目】There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

【解答】要寻找看起来还是某种扫描线问题。在从左往右扫描的过程中,既然要尽量使得射出的箭少,那就要尽量到不得不射箭的时候再出手,即到最先出现的未打爆气球右边沿再射出箭,而这一箭要打爆其中所有碰到的气球。反复如此操作。(既然要考察右边沿,因此排序的时候必须按照 end,而不是 start 来排序。)

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points==null)
            throw new IllegalArgumentException();
        
        List<Point> el = new ArrayList<>(points.length);
        for (int[] point : points) {
            Point p = new Point(point[0], point[1]);
            el.add(p);
        }
        
        Collections.sort(el, new Comparator<Point>() {
            @Override
            public int compare(Point left, Point right) {
                return left.end - right.end;
            }
        });
        
        int index = 0;
        int count = 0;
        Integer rangeStart = null;
        while (index<el.size()) {
            Point point = el.get(index);
            
            if (rangeStart==null || point.start>rangeStart) {
                rangeStart = point.end; // keep the range start as far as possible
                count++;
            }
            
            index++;
        }
        
        return count;
    }
}

class Point {
    public int start;
    public int end;
    public Point(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

Minimum Moves to Equal Array Elements
【题目】Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n – 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

【解答】每次只能移动 n-1 个元素且移动的方法是+1,要尽量让所有元素靠拢,那本质上其实意味着每次只能移动一个元素且移动方法是-1。这样,只需要找到其中的最小数,然后累加所有其他数和最小值的差值即可。顺便提一句,如果题目修改一下,移动的方法可以是+1 也可以是-1,那就不是找最小数,而是找中位数了。

class Solution {
    public int minMoves(int[] nums) {
        Integer min = null;
        for (int num : nums) {
            if (min==null || num<min)
                min = num;
        }
        
        int total = 0;
        for (int num : nums)
            total += (num-min);
        
        return total;
    }
}

4Sum II
【题目】Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 – 1 and the result is guaranteed to be at most 231 – 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

【解答】四个数组,各取一个数,要求加起来为 0。似乎没有特别好的办法,死算肯定嵌套层数太多,时间复杂度可以到 n 的四次方。于是,折中的方法是,A 和 B 嵌套,找出两两配对所有的和的出现次数;再拿 C 和 D 嵌套,找出两两配对所有和的出现次数。再把这两个结果合并考察,找到加起来结果为 0 的组合。整体时间复杂度为 n 的平方,空间复杂度也为 n 的平方。

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        if (A==null || B==null || C==null || D==null)
            throw new IllegalArgumentException();
        
        Map<Integer, Integer> sumMap = new HashMap<>();
        for (int a : A) {
            for (int b : B) {
                int count = sumMap.getOrDefault(a+b, 0);
                count++;
                sumMap.put(a+b, count);
            }
        }
        
        int total = 0;
        for (int c : C) {
            for (int d : D) {
                total += sumMap.getOrDefault(-(c+d), 0);
            }
        }
        
        return total;
    }
}

Assign Cookies
【题目】Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

【解答】分饼干问题。

本质上还是一个贪心问题,把饼干根据大小排序,孩子根据贪心程度排序。两个指针分别从这两个数组的左侧开始往右扫描。只要能满足孩子,两个指针都分别往后移动,否则只移动指向饼干的指针。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if (g==null || s==null)
            throw new IllegalArgumentException();
        if (g.length==0 || s.length==0)
            return 0;
        
        Arrays.sort(g);
        Arrays.sort(s);
        
        int gi = 0, si = 0;
        int count = 0;
        while (gi<g.length && si<s.length) {
            if (g[gi]<=s[si]) {
                count++;
                gi++;
                si++;
            } else {
                si++;
            }
        }
        
        return count;
    }
}

132 Pattern
【题目】Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

【解答】要寻找一串数中是否存在“小-大-中”这样的模式。

这道题看起来似乎不难,却让我思考了很长时间。最开始的想法是,看起来是一道引入双指针,创建几个 O(1) 的变量,从左到右简单扫描一遍,就可以得到结果的题目。后来越想越发现不是这样的,并且如果只使用 O(1) 的变量,似乎是无法解答的。因为对于这道题中 ai、aj、ak 三个变量的寻找,在拿到候选的 aj 的时候,ai 和 ak 使用不同的组合,aj 有可行和不可行这样不同的可能,因此为了遍历 ai 和 ak 不同的组合而形成的可能性,需要使用至少 O(n) 的空间来创建一个类似数组的结构。

这个空间就是使用 stack 来实现,而这个 stack 存放的是 ak 的候选。从右往左扫描,考虑到 i、j、k 三个变数,ai 在 aj 的左侧,aj 在 ak 的左侧,因此扫描遍历到的数:

  • 首先考虑能不能成为 ai,如果能,那就返回结果,因为 ai<ak,而 ak<aj 是已经存在了的;
  • 如果不能,那把它列为 aj 的候选,要求 aj 必须>ak;
  • 如果再不能,那就把它列为 ak 的候选,此处没有要求。
class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums==null) throw new IllegalArgumentException();
        if (nums.length<3) return false;
        
        Integer num2 = null;
        Stack stack = new Stack<>();
        for (int i=nums.length-1; i>=0; i--) {
            int num1 = nums[i];
            // check the case if num1 can be ai -
            // if num1 is smaller than num2 we find the result
            if (num2!=null && num1<num2)
                return true;
            
            // so num1 can't be ai, let's check if num1 can be aj -
            // if so the numbers in the stack must be smaller than num1 because ak < aj
            // if there are multiple we only keep the last one because:
            // to match ai<ak<aj, since ak is smaller than aj, we want ak to be as largest as possible
            while (!stack.isEmpty() && stack.peek()<num1)
                num2 = stack.pop();
            
            // so num1 can't be aj either, let num1 be an ak candidate -
            stack.push(num1);
        }
        
        return false;
    }
}

Circular Array Loop
【题目】

You are given a circular array nums of positive and negative integers. If a number k at an index is positive, then move forward k steps. Conversely, if it’s negative (-k), move backward k steps. Since the array is circular, you may assume that the last element’s next element is the first element, and the first element’s previous element is the last element.

Determine if there is a loop (or a cycle) in nums. A cycle must start and end at the same index and the cycle’s length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.

 

Example 1:

Input: [2,-1,1,2,2]
Output: true
Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.

Example 2:

Input: [-1,2]
Output: false
Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.

Example 3:

Input: [-2,1,-1,-2,-2]
Output: false
Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.

Note:

  1. -1000 ≤ nums[i] ≤ 1000
  2. nums[i] ≠ 0
  3. 1 ≤ nums.length ≤ 5000

Follow up:

Could you solve it in O(n) time complexity and O(1) extra space complexity?

【解答】我解是解出来了,但是属于基础解法,并没有做到上面 Follow Up 中要求的复杂度。思路是,每一个元素都尝试作为循环的开头,使用 set 来标记运行轨迹,同时也建立一个 boolean 型的变量来标记当前尝试是正向还是逆向。一旦发现遇到遍历过的元素,表示这次尝试失败;如果遇到起始元素,返回 true。

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        if (nums==null) throw new IllegalArgumentException();
        if (nums.length==0 || nums.length==1) return false;
        
        for (int i=0; i<nums.length; i++) {
            Set<Integer> forwardIndices = new HashSet<>();
            Set<Integer> backwardIndices = new HashSet<>();
            Integer originalItem = i;
            boolean forward = nums[originalItem] > 0;
            if (nums[originalItem] == 0)
                continue;
            if (forward && forwardIndices.contains(originalItem))
                continue;
            if (!forward && backwardIndices.contains(originalItem))
                continue;
            
            if (this.getNextIndex(nums, i)==i) {
                forwardIndices.add(originalItem);
                backwardIndices.add(originalItem);
                continue;
            }
            
            Integer item = originalItem;
            if (forward)
                forwardIndices.add(originalItem);
            else
                backwardIndices.add(originalItem);
            
            while (true) {
                item = this.getNextIndex(nums, item);
                if (item.equals(originalItem))
                    return true;
                
                if (forward) {
                    if (nums[item]<=0 || forwardIndices.contains(item))
                        break;
                    forwardIndices.add(item);
                } else {
                    if (nums[item]>=0 || backwardIndices.contains(item))
                        break;
                    backwardIndices.add(item);
                }
            }
        }
        
        return false;
    }
    
    private int getNextIndex(int[] nums, int index) {
        index = nums[index] + index;
        while (index >= nums.length) {
            index -= nums.length;
        }
        while (index < 0) {
            index += nums.length;
        }
        return index;
    }
}

Poor Pigs
【题目】There are 1000 buckets, one and only one of them is poisonous, while the rest are filled with water. They all look identical. If a pig drinks the poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket is poisonous within one hour?

Answer this question, and write an algorithm for the general case.

General case:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the poisonous bucket within p minutes? There is exactly one bucket with poison.

Note:

  1. A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.
  2. After a pig has instantly finished drinking buckets, there has to be a cool down time of minutes. During this time, only observation is allowed and no feedings at all.
  3. Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).

【解答】1000 个桶,只有一个桶里面有毒。如果猪喝了毒药,15 分钟内死掉。问要在 1 小时内找到哪个桶,最少需要多少头猪。

这道题貌似是一道数学题,也许在很久以前在一本数学有关的书上见过。一个小时,如果把喝的水分成 5 部分,每部分都混合起来让猪喝,可以喝+观察 4 次,但是可以得出 5 部分的结果,因为 4 次如果死了分别可以代表该次喝的水有毒,如果没死则按照排除法,得知剩下那一部分有毒。一头猪的存活情况,代表了 5 种可能,这就像是 5 进制,那么两头猪就可以表示 5^5=25 种,所以题中例子要求的是 5^x >= 1000,求 x 的最小值。用这样的算法推广可以得到:

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        long rounds = minutesToTest / minutesToDie + 1;
        // rounds ^ pigs >= buckets
        long pigs = 0;
        while (Math.pow(rounds, pigs)<buckets) {
            pigs++;
        }
        
        return (int) pigs;
    }
}

Repeated Substring Pattern
【题目】Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"
Output: False

Example 3:

Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

【解答】要判断一个字符串是否有多个子字符串拼接而成。使用最直白的做法,考虑每一个字符为重复串开始的位置进行递归,如果字符串全部遍历完毕,而又没有多余的字符,就返回 true。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s==null)
            throw new IllegalArgumentException();
        
        if (s.length()<2)
            return false;
        
        for (int len=1; len<=s.length()-len; len++) {
            if (s.length() % len == 0) {
                int start = len;
                boolean matched = true;
                while (start<s.length()) {
                    if (!this.check(s, len, start)) {
                        matched = false;
                        break;
                    }
                    start += len;
                }
                if (matched)
                    return true;
            }
        }
        
        return false;
    }
    
    private boolean check(String s, int len, int start) {
        int i=0;
        while (i<len) {
            if (s.charAt(i) != s.charAt(start + i))
                return false;
            i++;
        }
        return true;
    }
}

LFU Cache
【题目】Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

【解答】LFU 的缓存设计。

和 LRU 类似,思路是使用一个普通 map 来处理 key-value 映射的问题,但是为了能够根据使用频率来淘汰元素,就引入了有序的链表,这样在访问的时候位置可能会发生邻近的移动。思路基本上没有什么特殊的,但是实现起来比较啰嗦。很遗憾下面这个解停在巨长的一个 test case,还不是超时,而是结果错误,这个 case 的步骤是如此之长,1000+的操作步骤,大概前 2/3 这段代码的执行是没问题的,之后不一致,我很难去分析原因了。

class LFUCache2 {
    private Map<Integer, Item> map = new HashMap<>();
    private Item dummyHead = new Item(0, 0, -1); // the list is sorted ascendingly
    private Item dummyTail = new Item(0, 0, Integer.MAX_VALUE);
    private int size = 0;
    private int capacity;
    
    public LFUCache2(int capacity) {
        if (capacity<0) throw new IllegalArgumentException();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        
        Item item = map.get(key);
        int returnValue = item.value;
        item.frequence = item.frequence + 1;
        while (item.next != null && item.next.frequence<=item.frequence) {
            this.swapWithNext(item);
            item = item.next;
        }
        
        return returnValue;
    }
    
    public void put(int key, int value) {
        if (capacity==0)
            return;
        
        if (map.containsKey(key)) {
            Item item = map.get(key);
            item.value = value;
            item.frequence = item.frequence + 1;
            
            this.moveForwardForSameFrequence(item);

            return;
        }
        
        if (size == this.capacity) {
            Item item = dummyHead.next;
            map.remove(item.key);
            
            item.key = key;
            item.value = value;
            item.frequence = 1;
            
            map.put(key, item);
            
            this.moveForwardForSameFrequence(item);
        } else {
            Item current = dummyHead.next;
            Item item = new Item(key, value, 1);
            
            dummyHead.next = item;
            current.prev = item;
            
            item.prev = dummyHead;
            item.next = current;
            
            this.moveForwardForSameFrequence(item);
            
            map.put(key, item);
            size++;
        }
    }
    
    private void moveForwardForSameFrequence(Item item) {
        while (item.next.frequence<=item.frequence) {
            this.swapWithNext(item);
        }
    }
    
    private void swapWithNext(Item l) {
        Item r = l.next;
        Item prev = l.prev;
        Item next = r.next;
        
        prev.next = r;
        next.prev = l;
        
        l.next = next;
        l.prev = r;
        
        r.next = l;
        r.prev = prev;
    }
}

class Item {
    public Integer key;
    public Integer value;
    public Integer frequence;
    public Item next;
    public Item prev;
    public Item(Integer key, Integer value, Integer frequence) {
        this.key = key;
        this.value = value;
        this.frequence = frequence;
        this.next = null;
        this.prev = null;
    }
}

我也看了 讨论区高票 的解法,对 LinkedHashSet 使用很合适,把根据访问频率挪位置等等操作都简化了。主要思路:

三个 HashMap:

  • 第一个是最常规的,存放 LFUCache 的 key 和 value;
  • 第二个存放 key 和频率(出现次数);
  • 那么余下的问题是怎么实现淘汰机制,即在有 map 以外的 key 到来的时候,找到最近最不使用的 key 来,于是第三个使用的是一个值为 LinkedHashSet 的 map,这个 map 的 key 是前面提到的出现次数,而把实际的外部看起来的 LFUCache 的 key 放到了这个 LinkedHashSet 里面。

在淘汰机制触发的时候,就看到 LinkedHashSet 优于普通 HashSet 的好处了——数据是存放在它内部的一个 LinkedList 里面的,因而是严格有序的。这个 list 上面所有的数,对应的 count 都是一致的,添加的时候总是在尾部添加,而淘汰的时候总是从头部淘汰,这就像是一个队列。那为什么不直接使用 LinkedList,而要使用 LinkedHashSet 呢?这就要用到 Set 的机制,当添加的元素已经在 Set 内存在了,就要把它挪到队尾,而不是添加重复元素。

除了以上三个 map,还需要一个 int min,用来记录最小的 count,因为淘汰首先要找到当前最小的 count,其次才在属于同一个 count 的 LinkedHashSet 里面找出需要淘汰的那个 key。

class LFUCache {
    HashMap<Integer, Integer> vals;
    HashMap<Integer, Integer> counts;
    HashMap<Integer, LinkedHashSet<Integer>> lists;
    int cap;
    int min = -1;
    public LFUCache(int capacity) {
        cap = capacity;
        vals = new HashMap<>();
        counts = new HashMap<>();
        lists = new HashMap<>();
        lists.put(1, new LinkedHashSet<>());
    }
    
    public int get(int key) {
        if(!vals.containsKey(key))
            return -1;
        int count = counts.get(key);
        counts.put(key, count+1);
        lists.get(count).remove(key);
        if(count==min && lists.get(count).size()==0)
            min++;
        if(!lists.containsKey(count+1))
            lists.put(count+1, new LinkedHashSet<>());
        lists.get(count+1).add(key);
        return vals.get(key);
    }
    
    public void put(int key, int value) {
        if(cap<=0)
            return;
        if(vals.containsKey(key)) {
            vals.put(key, value);
            get(key);
            return;
        } 
        if(vals.size() >= cap) {
            int evit = lists.get(min).iterator().next();
            lists.get(min).remove(evit);
            vals.remove(evit);
        }
        vals.put(key, value);
        counts.put(key, 1);
        min = 1;
        lists.get(1).add(key);
    }
}

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 http://bit.ly/2VWLVZj

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 谈谈 Ops(二):流程和人

第二部分,我想谈一谈流程,依然来源于我的理解。Ops 的实践上面,有两部分内容紧密结合,不但共同显示了 Ops 的生产力,也在相当程度上体现了 Ops 的技术水平。这第一部分就是流程,也是今天要说的内容,另一部分是工具(也包括和使用工具相关的技能),下一次再说。

我认为 Ops 可以分为几个层次,最次的的一层,其特点是重度依赖于的人的直接“操作”。风险管理、因果行为,都通过流程来统一把控,并且遗憾的是只有流程——除了它基本没有可靠有效的工具,或是其他办法。

其实,流程本是个好东西。有时候 某些工程师被散漫和自由主义惯坏了,听到流程就反感。事实上,流程在很多情况下都有着举足轻重的作用。它们很容易控制,也很容易实施,基本是立竿见影 ,在不想要深入,不想要挖掘原因和研究对策的时候,流程上做一点改进,很快就能看到效果。

举个例子来说,多数的公司和团队,在线上代码发生变更的时候,都需要进行风险管理,这里面几乎一定会有流程。比如或最有名的叫做“变更管理”(change management)的请求,一般由开发人员撰写这样的请求,然后由项目经理和 Ops 的责任人审批。这样的请求中,需要包括诸如变更内容、必要性、风险、部署步骤、验证方法、回滚方式等等内容。这样的目的,在于尽量把变化的因素变成预期内的、可控的因素,尽早发现可能存在的问题,降低风险。

但是, 流程这样的方式,也有着负面效应。最大的效应就是,它单纯地固化行为,而拒绝人主动的思考。 就像几年前国内热炒的“敏捷”一样,流程不应该是本质,工具也不应该是本质,只有人才是本质。

在我曾经的一个团队中,在项目发布以前的最后阶段,有限的时间里面(一般都是一个晚上),需要把最重要和最核心功能过一遍,这个功能清单叫做 checklist。为什么不把所有的测试案例都覆盖了?因为时间有限。这就是一个很简单也很容易执行的流程。但是,随着时间推演,问题变得很多。比如产品发布了以后,发现有一个比较大的问题,于是研发团队就要回溯问题,发现问题以后,为了杜绝问题的再次发生,就打算采取某些措施。(到目前为止做法上面都没有什么问题,可接下去就有争议了。)于是一条用于检测这个问题的识别项被加到这个 checklist 当中。这里面有很多检查项事实上在问题修复以后是不会再出现的了,也有一些检查项明显是用于覆盖位于边角的 corner case,而不是主要的 case,但是既然出过问题,为了保险起见,还是都加进去了。就这样,随着时间和版本的演进,这个 checklist 变得越来越长,某些验证项的执行难度颇为复杂,在几年以后,已经到了几个小时都无法过完这个 checklist 的地步,于是这个流程就变成了一个越来越难以执行的累赘。

造成这一问题的原因是什么,就是 流程太简便了,太有效了,以至于这些聪明人不再思考应该采用什么样的方式来从根本上彻底地解决问题

现在我不想进一步分析上面的问题,而是来看看这样一个争议。这个“古老”的争议和流程关系密切,到底应该保留单独的测试团队,还是应该让开发来做测试?

无论你对这个争议的观点如何,无论二者取舍的利弊如何,无论这两种结论的场景适用性如何,这个争议本质上反映了一件事——我们是应该用更多流程加上多个单一职责的团队来解决问题,还是用更少流程加上单个承担多种职责的团队来解决问题?

在回到上面 checklist 的那个问题上,这个问题恰恰出在开发和测试团队单独运作的体系之中。有人问,这些新增加的问题中,既然有一些检查项是不会再出现的,既然有一些检查项覆盖的是边角非主要用例,为什么大家还要同意加上去?这就和上面说的测试和开发团队分离的情况有密切关系。因为测试团队多数都做不到白盒,不知道实现,只想用输入输出覆盖黑盒用例的方法来保证正确性,因而所谓的问题“不再出现”就无从谈起;而团队和人一样,一朝被蛇咬,十年怕井绳,出过问题,不知道实现,也自然没有人愿意承担这个再出问题的风险,哪怕它曾经说一个边角的 case。

事实上,这个争议的观点可以扩展到更多角色。不要以为只有测试团队遇到这样的困惑。Ops 也是如此——到底应该保留单独的运维团队,还是应该让开发来做运维?

于是,我听过 Ops 团队的朋友说过这样的话,听起来很有意思:

如果线上问题少,boss 说,要你们何用?

如果线上问题多,boss 说,要你们何用?

当然,这些争议,最终都需要达成某种平衡,没有一种方法是放在所有场景下的万全之策。比方说,一些 AWS 服务中,Ops 的比重居然占到了 85% 以上。且不说其最终的合理性,市场和人才等方面的策略永远制约着团队去寻找最优雅的解决方案,而是选择最“合理”的解决方案,即便如此,和其庞大的基础设施业务相比,其 Ops 团队依然是小而优秀的。这些单独的 Ops 可能在整个服务的漫长生命周期中始终无可替代,没有他们,开发团队也无法专注于核心功能,而要被大量的 Ops 事务困扰。这也是为什么许多互联网大公司在推行小团队和综合型团队,强调工程师职责需要覆盖 Development、QA 和 Ops 三部分的同时,依然保留少量的独立 QA 团队和独立 Ops 团队。

再从公司和团队发展壮大的角度观察流程在 Ops 中的变化。

在一家公司还小的时候,团队更为原始,但是 Ops 却更容易聚焦在核心问题上面。用户有困难?解决困难。产品有问题?解决问题。没有繁荣缛节,也没有太多可以复制的模式和需要遵循的流程。慢慢地流程多了起来,人做的事情也更加专业,这里可能会达到一个最佳的平衡点。因为再往后,因为那些流程的过度复杂性和开销,使得效率和质量的平衡被打破,一切向着低效和臃肿慢慢滑落。

从这个角度说,互联网公司在这方面要比传统企业更懂得简化和合理化流程的重要性。即便在公司壮大以后,依然有一些自下而上的反馈行为帮助这件事情发生。

总的来说,Ops 和 Dev 一样,兼具影响力、效率,以及风险。和 Dev 比起来,Ops 往往更为枯燥,不可控性更多,有时候不得不响应一些紧急的事情。对于从这三者的角度看来, 流程更多地,是用来在效率损失可以接受的情况下,控制风险,从而导向正向的影响力 。对于一些服务更 critical 的团队来说,风险控制相对地,更为重要,因而流程的比重可以适当增加;反之,流程需要简化,保证效率在一个高标准之上。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 http://bit.ly/2SaoXvD

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 谈谈 Ops(一):我的运维经历

偶然地,在会看这些年写的文章的时候,发现涉及到软件工程方方面面的内容,但是关于 Ops 的内容却非常少。我觉得这是不太合适的,因为在实际工作中,Ops 显而易见地占据了一大块比重。于是我调整了分类目录,增加了这个单独的分类,并且这一次,我想零零散散地讲一讲我关于 Ops 的一些经历,以及关于 Ops 的一些观点。

所谓 Ops,指的就是 Operations,在中文翻译上看,我觉得“运维”这个词可能是最恰当的。作为一个软件工程师,Ops 有时会特指 DevOps,关于它的定义,在维基百科上有这样一张图片,我觉得基本正确地描述了 DevOps 涵盖的内容(见右侧图)。

可以看到三方面的内容,可是,由于我们会把 Development 单独拿出来讲,会把 QA 单独拿出来讲,因此当我们讲起 Ops 的时候,我们更多的指的就是上图中下面那个紫色的环。

我们都希望代码可以一蹴而就,测试可以面面俱到,软件和产品都可以顺利而愉快地跑起来,可这些都是一厢情愿。我们需要把新版本软件安全快速地部署上去,在出了问题之后需要采取措施减小影响,分析问题,并修复问题……这些问题都需要 Ops 这样不可替代的环节。由于我个人认识的局限性,在以往,Ops 显然是被我轻视的环节。当然,这可能也和我工作以前接受的教育也有关。读书的时候,我们学开发,我们学测试,可是我们从来都不学运维。可以说,上面这三个环的于我而言的重视程度,显然 Development > QA > Operations,这是不可否认的。我猜测着对于许多人来说也是如此。但是,随着工作经验的增加,我越来越意识到 Ops 本身的重要性。于是这些内容,打算分为几篇来讲,来自一个并不喜欢运维的软件工程师之手。

我在华为的经历

我工作的第一家公司是华为,这是一家对于 Ops 有着深刻理解和丰富经验的通讯软件公司。有意思的是,这也是在我熟悉的公司中,在 Ops 上花专人投入比例最高的一家。有许多项目的发布和运行,都是基于不同物理地区和物理站点的,这也是电信软件非常典型的一种部署模式。具体来说,就是华为的工程师,需要出差到电信运营商那里去,去安装部署。如果是一个全新的项目,这个过程叫做开局;如果是从别的服务提供商那里把项目接过来(比如一个项目,本来用的是中兴的软件,现在用户体验基本不变的基础上,挪到华为的平台上),这个过程叫做割接。其他我在十年前第一次出差,在中国联通 3G 机房,位置大概在北京上地,就是去开局。和开局花费的时长相比,割接通常更为迅速,但是压力更大,因为割接的场景通常意味着目标设备只有非常短的服务停止的时间,甚至要求无服务中断;另外,有时候竞争对手的关系,没有办法得到之前系统完整的信息,有许多决策需要根据经验来判断,甚至猜测——比如原数据库要从前一家竞争对手的老库迁移到华为的新库,数据转移的时候,某一列原数据库表里的字段在原始文档里没有,需要根据其内容和结构来推理其实际含义,再转移到新库恰当的位置上。

这种方式明显更为传统一些,从客户的角度来说,好处在于,我们跑到客户的地盘上,在他们的设备厂房里做文章,很多事情他们都更方便控制。对于一些复杂项目,需要有多家服务提供商协同合作的情况,甲方客户可以和各家乙方面对面工作,沟通和组织都会更加顺畅。至于这种方式的弊端之一——成本,对于国内的三大电信运营商来说,通常都不是一个问题。

上述成本包括人力成本,毕竟这样的方式需要有专职的运维人员看守。出于安全、审查等等角度的考量,设备是隔离的,网络是隔离的,运维人员需要在现场驻守,以处理预期内或预期外的各种问题。我们把那里叫做前方。而研发基地的工程师团队需要和运维团队沟通协作,解决各种各样的问题。这就是后方。通常后方的研发工程师没有办法直接动手,而是需要和运维工程师沟通以便采集数据和分析问题,在特殊情况下,为了增进效率,后方的研发工程师会出差前往前方现场,直接处理问题。

我还记得在那次开局的过程中,要和所有周边系统协同调试工作,这个过程叫做联调。由于整个 3G 系统庞大,我所负责的视频运营平台,以省为单位,要和不同的服务接口,比如计费服务等等,而甲方客户期望分散风险,每个省份的服务又都是独立的,而且实现厂商都是根据招标结果而来,每个省份都是独立的。因此和我们联调的服务来自各家厂商,这样的协同合作变得无比困难。这里面多数都非软件的问题,而是管理和沟通的问题。

出于成本的考量,如今互联网公司的很多机器设备多为普通性能的廉价设备,而硬件损坏的容错是作为整个分布式系统设计常规的一部分进行的。可那个时候,电信运营商的机器设备和如今互联网公司是大不一样的。我还记得我们的软件是部署在整个机架中间的数块单板上的,存储系统是部署在磁盘阵列上的,而数据库是部署在 IBM 小型机内的……于是我们许多的 Ops 操作,都是基于单台机器进行的。加上联调的许多工作,存在大量重复性的劳动。为此我写了很多 shell 脚本,来帮助提高工作效率,当时觉得很自豪。可是后来才慢慢感受到,真正优秀的 Ops 流程,是不需要自己现场去手写这些脚本的,工具应该帮我们干了几乎所有的事情。手动脚本是介于手动命令和工具之间的手段,但总体来说依然是一个容易犯错而且缺乏延续性的做法。一个成熟的运维流程,应该把这些犯错的可能减到最小。

这种 Ops 的模式可以让研发团队的工程师更专注于本职的研发工作,但是也会带来和实际场景脱节的问题。比如说,我在那个联通项目之后,转去做某一个新产品的基线版本了,基线版本多数情况并不直接上线,而是需要由定制团队进行本地化和具体项目化的定制,之后才能发布上线。这就足以见得我们离实际产品部署有多么遥远了。由此产生的其中一个典型问题就是,当时我们做的那个产品中,网站的那部分,由于搜索引擎优化等等问题,居然被 Google 爬虫给爬死了。这样严重的事情等一层一层分析、讨论和传播上来,等我们获知这样变体了多次的消息的时候,已经过去了很长一段时间,有一些具体的有价值的信息也丢失了,这让我们觉得离实际的产品仿佛很遥远。

我在 Amazon 的经历

Amazon 的库房遍布世界各地,而且更为零散和复杂,因而这种需要奔赴现场才能进行 Ops 的模式,多数情况下都是不适用的。Amazon 的不同团队会负责不同的服务,多数服务只用中心数据库或者数量有限的几个区域数据库,少数服务才在当地库房里面设置数据库。在 Amazon 内部,有一套专门负责版本管理和部署的工具,软件版本、依赖项目、包管理、分析、编译、测试、部署,等等等等,全部都由这套工具来完成。无论是 1 台机器,还是 100 台机器,软件工程师要做的,就是在适当的时候,盯着这套工具提供的界面,把软件按照指定的某种方案,部署到实际的机器上面去。任意两台机器具体部署的代码版本,通过工具就可以对比,如果要打补丁,要升级系统,要改权限,这套工具就可以完成。换言之,多数情况下都不需要 ssh 登陆到具体的机器上去。

我有一些互联网大公司的朋友,包括国内国外,从侧面了解过,再加上如今我所在的公司,综合比较起来,Amazon 内部提供给工程师用于 Ops 的工具应该说多数都非常先进,有些能够领先业界好几年,而这套部署工具尤其可以说极少公司能出其右(我以前的一位老板打趣说过它是 Amazon 内部“四大金刚”工具之一)。其实,极少有公司愿意在没有必要的情况下把一个内部工具功能做得无比强大,更何况是以 frugality 作为领导力准则之一的 Amazon。其原因之一就是,工程师的成本。招聘运维团队的工程师,其实并不容易,而如果能够用尽量少的研发工程师团队,“顺便”去把运维的事情做了,这无疑是很节约成本的事情。从这个角度说,资源的限制才能促进创新和发展。

有了一系列 Ops 工具,Amazon 不需要招特别多的专职 Ops 团队,而多数 Ops 工作自然由不同的工程师完成。其中一个最典型的事情就是 oncall。所谓 oncall,就是值班,一般研发团队里的工程师轮值,一旦出现严重的线上问题,警报就会想起,这个过程叫做 page,这种情况一旦出现,不管是上班时间还是下班时间,都要立刻投身问题应急处理的行动中去。事实上,Google 也好、Facebook 也好,Netflix 也好,专职 Ops 团队的人数相对研发整体来说都比较小,但是我依然认为 Amazon 是其中最不容易的一个,因为 Amazon 的许多产品和服务尤其需要繁重的 Ops 工作,在如今的公司做了将近一年的云设施的工作才慢慢了解,和其它一些互联网服务比起来,提供基础设施的 AWS 需要的运维工作量非常非常巨大。

有人说,让研发工程师去做运维,能做好吗?不是应该让专业的人去做专门的事情吗?这个观点是两说的,运维技能的缺乏可以通过优秀的运维工具来环节;而另一方面,每多一种“专业的人”,就意味着整个工作系统中,多了一个角色,多了一个 N 个需要沟通的环节,这些都是内耗。我在 这篇文章 里面曾经比较过使用专业运维人员和使用研发人员来代理运维工作的情形。这种方式下,出现的问题能够最快速度和最大程度地引起开发人员的注意,有反向强化软件质量的作用。我相信多数软件开发工程师都不喜欢 Ops,这也容易理解,但是不参与 Ops 是很难想象能够做好产品的。

说一个具体事例。我记得在 Amazon 的销量预测团队工作的时候,有一次我 oncall 被 page 醒,因为新发布的软件本身暴露出来了一个问题,于是着手回滚到上一个版本。可是经过 rollback 之后,发现问题并未解决,调查获知原因是客户端缓存了前一个版本的某些有问题的信息,于是连夜赶补丁,刷新客户端内的信息,从而修复问题。事后,我们团队排查了类似的问题,相当于吃一堑长了一智。这样严重的问题不经过 oncall 这样典型的 Ops 经历,是很快速难反向强化回代码上的。

在我目前的公司中,Ops 方面所采用的方式和 Amzon 是类似的,Ops 在每个研发团队中的占比不同,我见过 10% 的,我也见过 80% 的。在我目前的项目团队,由于种种原因,Ops 的比重大概占到 40% 左右,这比我今年在前一个项目组中的 Ops 高了近一倍,也比我在 Amazon 期间最后一个团队的 Ops 工作量 30% 高,以我的理解来说,这明显偏高。其中的原因比较复杂,我们希望我们能够努力把它降到 25% 左右。当然,这并不是一件容易的事情,我对此也有一些思考,有关的内容等合适的时候再说吧。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 http://bit.ly/2MiFoAX

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 写在曼联主教练又一次更迭之际

作为一名好多年的曼联球迷,在后弗格森时代,第三任教练下课的时间点上,总有很多感慨,也有不少想说的话。英格兰足坛浮浮沉沉,进化了这么多年,那个老四强时代已经过去,那个群雄乱起的时代也接近尾声。这两年看来,可以说强弱集团军已经分明。第一集团属于曼城和利物浦,去年在联赛中不可一世的曼城,在今年也遇到了真正的竞争对手。第二集团包括阿森纳、热刺、切尔西和曼联,其中热刺现在位于第一和第二集团军之间,但是我认为从长远来看,加之阵容厚度考量,它是属于第二集团军的。整体上看,英超在世界的格局中目前是往上走的,这些进入欧冠的豪门也已经闯入淘汰赛了。这个时间点上可以谈的事情似乎很多,我想按照自己的理解来谈谈几个敏感的观点。

首先,弗格森退休以后,我们才感受到了弗格森在位的手腕和能力,这没有错,可是也要看到,英格兰联赛,早已不是弗格森时代的样子了。

特别是近几年,克洛普和瓜迪奥拉等新锐教练带来的理念变革,着着实实地帮助英格兰以往那种糙快猛的足球细腻化,如今的攻防体系更加多元和成熟。我从 2004 年开始看曼联的球,老实说,到弗格森退休那一年的班底,是冠军班底没错,但如今来看,我不相信他们还能继续拿冠军。事实上,在弗格森最后几年,在和一些世界强队的交手过程中,我已经看到曼联处在明显的下风。竞技体育的魅力在于结果的不确定性,因而一旦赢球,就会掩盖许多问题。一个神奇的教练,可以让球员发挥 120% 的能力,比较出色的球员可以变得非常出色。但是,球员的班底始终是强弱的主导因素,就如同你没法带领一支英超的中小球队多年竞争于联赛第一集团。应该说,从弗格森最后两三年开始,曼联的球员班底已经不是英超最强了,可能大多数时间里连前三都排不上,因而总是期望于联赛冠军是不甚合理的。我记得好些年前哈维曾经说过,世界上最大的俱乐部,对球员吸引力最大的俱乐部,除去巴萨皇马,接着就是曼联。可是现在看看,曼联的名字,早就排到了远远的位置,因而从这个客观环境的角度看转会市场,对于曼联俱乐部而言,难度明显更大了。

然而,球员班底的建设,在如今足坛,已经不是主教练一人之功了。主教练更迭的频率,已经让主教练主导的青训和交易难以为继。我们看到后弗格森时代,第一任更偏向传统和继承的莫耶斯带来了保守的引援,最后以执教生涯的失败告终;第二任性格乖张的范加尔,带来了数个让人看不懂的引援,提拔能力还远达不到以往一线队标准的青年军,除去足总杯,也以失败告终;第三任倔强和强硬的穆里尼奥,引援是否糟糕另议,但不能很好使用引援大家却都看见了,第一年带来了两个有一定分量的冠军(社区盾毕竟分量太轻),第三年在更衣室一锅粥的情况下还是狼狈离任。一个保持球队建设一致性的角色,包括青年队建设的青训主管,以及转会市场上负责进出的经理,但在曼联后者从未得到任命,让主教练去负责转会市场几乎就意味着一定糟糕的转会判断和风险控制,而主教练的更迭也让诸多引援变成了笑话。现在的引援模式不但不够合理,甚至听起来就觉得有些荒唐——主教练给一个转会清单,然后俱乐部派人去挨个谈判,这样就意味着人选被局限在清单以内了,无论这个清单是来自被信任的主教练还是其他人,这种方式几乎可以说不被宰都不可能。如果有优秀的球员,价格合适,但不在清单上,算多大数,买还是不买?事实上,如今的转会市场,早比十年前、二十年前复杂得多。让懂行的专人来负责几乎是每家大俱乐部的唯一选择。

其次,和在切尔西的成功相比,穆里尼奥真的退步了吗?

我看未必。大体上,穆里尼奥从未改变过他最核心的风格和思路。他的足球永远是立足于传统的攻防体系,压缩防线,针对性部署,支点中锋,边前卫回收防守等等,并且非常看重球员的精神品质。我有时候觉得,穆里尼奥对于精神品质的看重,是否已经到了走火入魔的地步,这也许和他的非球员出身有关。球员毕竟是去踢球的,而不是去打仗的。再激烈的同城德比,也只是一场足球比赛。我不认为从两度入主切尔西都拿了联赛冠军,到来到曼联,他就改变了多少。他的足球一直都是“难看”的,尤其在进攻端,除去球星个人能力,可供分析讨论的进攻套路并不多,而对于收缩防线的刻意追求,又进一步使得生涩的进攻体系彻底难产。我记得有这么一个事情,他公开表扬卢卡库从中锋位置回追到右边卫防守,我相信这是某种优秀的精神品质,但对于这样一个体重的中锋,我是持有明显的保留意见的。卢卡库进球难的问题,一大笔帐要记到这一类防守的部署上面。

在以前,他可以用他的办法赢球,但是足球也在变革和进化,如今的他,我们假想一下,拿着以往成功的办法,再去以往成功的球队,比如第三次入主切尔西,一样给他两年的时间,他还能带来冠军吗?我认为不能。因为瓜迪奥拉和克洛普席卷而来的高位逼抢和出球体系,已经让穆里尼奥的战术显得难以为继。他要找得到多么合适的球员才可能带来成功,而这个难度,已经无法和几年前相提并论了。所以说,不是穆里尼奥不行了,而是他的战术打法已经不足以维系他在如今的英超环境里再拿联赛冠军了。哪怕在弗格森时代,我也注意到,他本人虽说上了年纪了,某些方面相对刻板,却总体来说依然是一个善于不断改进的教练。比如当年他引入香川真司,打菱形 442,虽说最后也不能够算很成功,但能够在阵型上抛开最擅长的边锋,使用真真正正的前腰,也是一个主动的尝试。

看穆里尼奥的人员管理,其实也是类似的。他还是遵循他倔强的从严治军的方针,我不认为他有任何大的改变。可是如今的球员已经不一样了,他们更有主见,更接近市场,也把自己的利益放到更高的位置。就好像你对现在孩子们讲革命时代的故事一样,多半落得个冷场的结局。有不少人对“哄球员开心”嗤之以鼻,可事实就是,它不但重要,还极大地影响了球员的工作绩效。看看他主导的引援,多数都失败了:姆希塔良冷落了半个赛季,断断续续用了数个月,拿去换桑切斯了;可桑切斯呢,签了个毒药合同,变了个人似的,状态一落千丈;卢卡库连续不进球,效率低得可怕;弗雷德,打不上常规主力;拜利,犯了几个错,于是也打不上常规主力了。以前看到大牌球员,或者新球员要赢得和保持范加尔的信任很困难,如今看来他的弟子穆里尼奥更甚。这种情况下,俱乐部否决了穆里尼奥对一些接近三十岁的球员购买的要求,以及要求卖掉马夏尔的要求,也情有可原。俱乐部这种做法很难说最佳,但这件事情上明显是更合理的一方。

最后,现在曼联的这批人怎么样,是否真的不堪?

俱乐部层面球员班底建设的落后,确实存在,但也并非落得很远。无论是索尔斯克亚留任,还是以波切蒂诺为代表的进攻派教练带队,在人选方面,我们都可以从后到前一层一层来分别看看情况,并做一些猜测。

首先是门将,首要任务是和德赫亚续约,我认为他是属于那种训练一般,但天赋极高的门将。他在门线上的表现,也许就是世界最佳。损失德赫亚,在市场上极难找得到相近能力的替代者。

后防线上,问题其实是比较多的。从索尔斯克亚的用人来看,中卫上排第一的是林德洛夫,事实上,这也是符合他战术理念的。中卫出球能力极其重要,林德洛夫事实上单对单防守很不稳固,头球更是能用“糟糕”来形容。但是对于这些极度重视进攻的教练来说,在现代的防守体系中,一个出球能力强的中卫,有着无可替代的作用。有点遗憾布林德已经离开,要不然他可能是队中出球最好的中卫,也自然能得到一定的机会。罗霍和琼斯的出球能力都尚可,比拜利强,但是总体来说都不够稳固,强点也不足够强,属于平庸的中后卫。斯马林属于典型的英式中卫,头球好,可脚下的活要命。如果和林德洛夫搭档,一个脚下技术过得去但侵略性、上抢都很出色的中卫会是更合适的选择,而让林德洛夫去避开对抗的弱势,去补位打覆盖,从这个角度看,没有一个合适的人选,因而中卫的引援是必要的。左后卫上面,我认为目前问题不大,如果要培养卢克肖,那就要找有合适的轮换,如果目前的身体素质没有明显退化,目前罗霍偏防守而阿什利杨偏重进攻,是很好的搭配。如果阿什利杨今夏离队,需要买人替代。右后卫的问题最大,无论是阿什利杨还是瓦伦西亚,都远远达不到要求(虽说曾经的瓦伦西亚有那样的能力,作为全能型的右后卫中,说是世界前五都不为过)。其原因在于,曼联的前场是严重左倾的,即是习惯使然,也是战术使然,无论是马塔还是林加德,都不甘心待在右路和套边的右后卫打配合。因此右后卫需要一个有能力自己拿球上下的人选,这样的人事实上在市场上很难找,找到了也是比较高的价格。

中场在我看来大体上不太需要进补,而且我看到不同风格的球员,能带来不少战术可行性。马蒂奇属于覆盖能力不强,但是出球和组织能力好的后腰。在后卫线出球遇到困难的时候,我们经常看到他坠后协助出球,在后卫线压力小,往上顶的时候,他又可以把球直接送到禁区前沿。埃雷拉属于奔跑能力强的 B2B 中场,覆盖广泛。目前看这两人搭配,都偏重防守,可以给博格巴带来最大的助益,让他多深入禁区。曼联实力是真正的世界级球员不多,可能除了德赫亚,就是博格巴了,我不管他有什么其他新闻,只要能帮助博格巴发挥出色,几乎就意味着进攻端解决了一半的问题。还有一个值得一提的人是费莱尼,我看他在索尔斯克亚的人选中排名比较靠后,而事实上,我数次看到,除了众所周知的高球战术,在中场推进困难的时候,他的作用也是无可替代的。比如超一流的胸部卸球能力,不能指望他传出什么杀伤力强的球,但是失误少,拿得下球,是个很重要的补充。至于其他人选,要么实力差太远,要么有严重的问题。比如弗雷德,半个多赛季了,依然适应不了英超的节奏和对抗,拿球和出球失误率太高,而且对防守端贡献似乎是个天生的短板,似乎能期待的就是他能够靠自己超过常人的跑动了,在当前的体系下,很可能是一个平庸的引援。

锋线上,我认为可以不补充新人,如果需要,那就是一个正儿八经的右边锋。世界上顶级的右边锋本来就很少,相反左边锋可能是最容易出球星的位置,这也是普利西奇能够卖到如此高价的原因之一。右边锋的缺乏让整个左侧过于拥挤,而对右边后卫的攻防要求都增加。左侧的马夏尔和桑切斯显得位置重叠,而拉什福德的最佳位置是在锋线,他在边路的时候倒是能拉开宽度,但是只有在中锋位置的时候他的跑动优势能够发挥得最佳,因此即便他打右边路,他只有游弋到禁区内才最有威胁。卢卡库的触球是个灾难,但他现在最大的问题还不是触球,而是体重。他需要减重,尤其是在绝大多数进攻教练的体系里面,中锋的跑动能力,尤其是单前锋的战术下,至关重要。以目前这样的体型,要保持第一时间压迫,很难支撑一整场比赛保持高强度跑动。

所以,总体来说,一个有独立拿球能力的右后卫是最需要补充的,其次是能拉开宽度的右边锋和一个盯人中卫。

看了那么多年曼联的足球了,心态以及渐渐平和,也更关注俱乐部长期的发展,而非一场比赛的得失。弗格森时代的结束,带来的不是阵痛,而是长期的痛楚,这个影响看起来远比当初想象的深远。看起来阿森纳也在慢慢开始经历类似的境遇,当然可能会缓和得多。英超如今的竞争,要比十年前良性得多,越是群雄并起的“乱世”,越能给更多球迷带来竞技体育未知性的魅力和体验。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 http://bit.ly/2SH3jfy

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 倔强的程序员

对于程序员来说,大多数人公司都有技术和管理两条发展路线,通常在同一家公司,管理路线的发展可能性,要相对广阔一些;但是技术路线也有技术路线的好处,比如相对而言更依赖于硬实力,因而工作机会丰富。我相信有不少程序员都和我一样,坚守着技术路线,无论是进还是退,都对管理者的岗位没有什么兴趣。

兴许大家都听到软实力和硬实力的概念。对于一个技术人来说,硬实力大致上可以认为是计算机和软件工程相关的技术能力,1 还是 0,是还是非,会不会算法,懂不懂设计,清清楚楚,明明白白; 而软实力则反过来,听起来挺抽象,挺模糊,比如沟通能力,自我管理能力,但是却扮演者重要的角色,甚至随着职业生涯的发展,它的影响力越来越大。而性格,是软实力中一个很特别的影响因素。

下面我讲的是在程序员技术发展路线中,“倔强”性格的影响这一个窄窄的范围,而且是就我的认知而言的。显而易见它不可能是很客观的。我相信会有很多人持有不同的看法。

我想大家都认可的是,基本上每个团队里面都有各种脾气性格的人。记得我刚工作的时候,团队里面平和和好说话的人更多。多数人性格都比较平和,这可能和资历、眼界等等因素也有关。以前读过一篇文章,说一个团队里面,有各种各样的角色,有牛、有猪,有狗、有猴子等等等等,分别代表着不同的性格。随着时间的试炼,大家发展的情况各不相同。在讨论方案和问题的时候,肯定有人不同意,但是只要多数人决定了做法,或者是几个强硬派决定了做法,大多数人也就不再计较,因此 commitment 比较容易做出,且朝着一致的方向。

但是随着工作年头的增加,我发现团队里面个人的性格,普遍是越来越倔了。无论什么时候我们讨论问题,观点不同是司空见惯的。可现在不同的是,要达成一致,并不是那么容易的事情。好吧,大多数人支持方案 A,少数人支持 B,兴许几年前这票支持 B 的就表示愿意按照多数派的 A 来实施了;可是现在呢,少数派一定要争论下去,技术方案的选择不是少数服从多数的选举,为什么要 A,我们来给 A 和 B 做做分析,我们来激烈地争论吧……

以前我认为,职业生涯的发展,到一定阶段,高级别一些的工程师,想必也是性格各异的吧,应该有的人比较强硬,有的人比较容易 pushover 的吧,性格这东西嘛,分布都是有随机性的。可是如今我接触到的情况呢,却恰恰相反。这些发展比较好的程序员,相对于其年龄和资历,级别比较高的程序员,居然性格几乎无一例外的“倔强”。而那些性格比较“好”的呢,相对来说发展普遍都没有那么好。看到的案例多了,似乎可以粗略地得到这样的结论:走技术路线的程序员中,性格倔强的人不一定发展得快,但是性格平和的人肯定不行。

虽然我能看得到的案例数量并不大,但我依然觉得这个现象有一定代表性。我觉得这里有这么几个因素:

  • 倔强的程序员,往往也是较真的程序员,他们会追求最佳的解决方案,他们会追求最合理的代码实现,他们可能抠一点某些人看来无足轻重的东西,但是就是这些东西把软件的质量提高。
  • 倔强的程序员,懂得维护自己认为正确的观点,而为了维护这个观点,会反复思考和分析。我没有见过一个能把 trade-off 做得好的人对维护自己的观点抱无所谓的态度。
  • 倔强的程序员,遇到困难也不那么容易退缩。这也是显而易见的,性格软弱的人,通常也不愿意坚持己见。

但是,物极必反,倔强的程序员,也可能死得特别惨。我见过一些被踢出团队的程序员,大致分为两类。一类是能力实在不足,绩效特别差,比如代码写得又慢 bug 又多;还有一类就是这类硬骨头,倔强到难以维持基本客观的程度,到处树敌,太过拖累整个团队的工作。

再结合程序员工作中的许多具体事情,再进一步谈一谈这些倔强的程序员们。就说个有趣的事情吧。我们把他们中的其中一个,叫做大 Z(这个字母看着就很霸气),而相对不那么“难搞”的程序员,叫做小 s。

在一次的设计讨论会议上大 Z 说对小 s 说,我认为你的方案不如我的好,理由是 xxxxx,于是大 Z 和小 s 来来回回一番争论,刚开始还算可控,但是大 Z 说,“我觉得你缺少扩展性的常识”。有经验的人可能马上意识到,大 Z 的这句话已经从“对事”变成了“对人”,这明显是不对的。于是这句话一冒出来,小 s 马上就不高兴了,再不痛不痒辩论几句以后,没有继续争论下去,显得很失落。

这个场景看起来是不是很熟悉?哪怕小 s 是更在理的一方,也放弃了继续争论下去的欲望,反而落得自己不爽好几天,每次和大 Z 沟通都会想着当时的场景,甚至觉得大 Z 还会有意无意针对他。有人可能会觉得,那大 Z 会不会事后觉得自己过分呢?我想说,大多数情形下,不会的,以大 Z 的性格来说,他冒犯了小 s,他也许意识到了,也许没意识到,可是这样的事情他根本就不会放在心上。回到事情本身,谁的方案更合理很难讲,但这件事情本身伤害到了团队中的成员,影响了团队的氛围。我们可能见到类似的事情到处都是,甚至在某些沟通强烈的地方尤为严重,比如 code review。

多数情况下,我们撇开技术本身的因素,谁的发展更好呢?却是大 Z。虽然有少数情况并非如此,但是多数情况下,大 Z 却有着更更为广泛的影响力,而某些情况下争论所显露出来的 backbone 会盖过他在争论和为人上面的“恶霸”属性。这也从某种角度说明,为什么到了一定级别的程序员,且不论技术如何,心理承受能力和沟通的技巧,都是有一定造诣的,那些敏感而脆弱的呢,已经挂在晋升的半路上了。

交流和沟通本身就是一个说不清道不明的复杂体,很多人可能会想要安安心心做技术,我相信也有很多公司希望提供这样环境。可事实是,绝大多数情况下,越是这样想的人,就越会发现,这只是一种美好的愿望,不可避免地,有很多为人处世上的“屁事”,未必要上升到“职场政治”那么高的程度,却依然会考验你的心理,磨炼你的性格。

最后,从团队管理的角度来说,哪一种人更合适呢?

其实,“合适”这个词的定位很难讲,但是倔强的程序员通常更难管理,这倒是真的。可是,换一个角度想这个问题,为什么要“管”,管理又要做到怎样的侵入性?理想的状况是,虽然有一些性格似乎比较“强硬”的程序员,但是他们是讲原则,讲道理的,如果团队的成员在总的目标上大致是一致的,团队就能够具备一定的兼容性。可理想毕竟是理想,团队中的磕磕碰碰遇到谁都能喝一壶的。特别是,如果管理者想成为那个决策绝大多数事情的人,碰到这些倔强的“大爷”们,很可能就会碰一鼻子灰。

在我的职业生涯中,待过好些团队,我见过这种管理者和倔强的程序员们之间的碰撞,有在挣扎和妥协中寻求平衡的,有程序员滚蛋的,也有管理者扫地出门的,甚至有两败俱伤,鱼死网破的。这里面也有很多有趣的故事,下次再说吧。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/2SOaylG

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 幸运的时代

差不多四年来第一次回国,感触颇深。中国的发展,尤其是互联网发展就像一个孩子的成长,如果每天都盯着看,没觉得有什么变化。但是如果稍稍离开一段时间,回头就发现巨大的变化。

互联网正在不断融入生活,其中最显著的变化,便是支付。

依然记得 2012 年初我刚到北京的时候,直到 2014 年离开,那些时间基本上还是现金走天下的年代。由于种种原因,老早就兴起的信用卡没有办法流行开来,大家还是习惯于装一兜子钞票,然后在各个不同的地方大票换小票花掉它们。

如今呢?当我结账的时候,被问到“微信还是支付宝?”,我弱弱地回了一句——“现金”,引来一阵哄笑。足以见得,那么短的时间,互联网已经占领了老百姓的支付战场。无论是预约、注册、缴费……到处都是微信或者支付宝的二维码。不是你扫商家,就是商家扫你。这个速度是如此之快,快到让仅仅离开那么一小段时间的我已经彻底沦落成土鳖一枚。

我认为同为参与互联网建设的芸芸众生,我们这一小簇人是最幸运的——我们同拥有美国和中国,这世界上两个最大的互联网国家的经历,而且是参与互联网发展的经历。世界十大互联网企业,六个在美国,四个在中国。美国的苹果、Amazon、微软、Google、Facebook 和雅虎;中国的阿里巴巴、腾讯、百度和京东。难道还有比这更美好的事实吗?

由于多数外商过于自负、高傲和不接地气本土化,再加上众所周知的那堵墙,无论原因来自哪些方面,对于互联网企业的国家保护事实可谓水到渠成。这些天在阅读一些中国成功互联网企业的传记,我觉得与其单纯分析企业家和企业自身的成功因子,倒不如更关注这些年的互联网浪潮,淹没了一大批,也把一些气质出色的和出招各异的互联网企业捧到浪尖上。

我们也要看到,市场的规范性远远落后于其野蛮生长的进度,滞后的法律法规和孱弱执行的事实,让互联网本身正在遭受难以避开的阵痛。但是即便如此,成长的的力量无可阻挡地爆发了。如果你和我年龄相仿,也许记得在十几至二十年前,网速还是论多少 kb 的年代,那个需要连电话线接猫拨号的年代,那个几 M、十几 M 的东西要拿“网络蚂蚁”扒拉半天的年代,仿佛就在眼前。再看看如今的互联网世界,天翻地覆的变化就在眼前。

这些天还去联通营业厅和银行网点办理业务。这些企业的效率和办事方式,低效而落后。比如我的国内后付费手机号在北京联通开户以后,必须回到北京的联通营业厅才能注销,对,不但要来到营业厅,还必须是北京的营业厅,否则连暂停服务保号都不行。这简直荒唐。再比如招商银行的一卡通挂失,由于是曾经的公积金卡,挂失后必须在 7~10 个工作日再来到招商银行的柜台取新卡,连邮寄都不支持,而招商银行的网点又只有大城市有(我的家在一个小镇),这就让挂失没有了可操作性。

于是又联想起那些支付的变革,像电信和银行这样传统的企业,又怎能和支付宝和微信这样的真正的互联网企业竞争呢?即便有各种扯淡的国企保护政策,它们依然从骨子里就落下了十条八条街了。

在几年前,我说过我为中国的基础建设感到自豪,如今又可以自豪地增加一个,它就是互联网。未来几年,互联网在高速发展的同时,我更希望能看到这些缺失的法律和规则可以慢慢补上,而那一堵让中国互联网某些部分无法互联的墙,可以慢慢倒掉。我相信我们这代人中,大多数人是愿意保留许多耐心的。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/2Or6IAg

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 给车换电池的神奇经历

水文预警。

这段故事,像小说或者电视剧一样的故事,发生在三天前的下午。我不相信这辈子还能遇到第二次。我本来发在朋友圈上,而且我觉得这样悲催而搞笑的经历,除了哄笑一番以外,应该没有什么价值。但是好几个朋友看到以后,表示对我的神奇经历有了解详细情况的愿望,希望通过给我的悲惨故事他们带来欢乐…… -_-|| 我仿佛看到了那个得意的和嘲笑的嘴脸,好吧,我就稍微详细一点讲……

准备开车去附近买个午饭,车启动的时候挣扎了一下。凭借我二把刀的用车经验,我猜应该是电池快要没电了,但是我对我的车抱有十二分的信任,我相信它的顽强,我相信它的潜力——出去买个饭总不至于出问题吧。

好吧,判断失误是可能发生的。买好热腾腾的披萨,准备回家的时候,发现车启动不起来了。我听着电打火的声音,却看不到它任何试图发动的迹象。

凭借多年应试教育和自我钻研培养的问题分析技术,一通调查判断(瞎猜)是电池嗝屁了。

于是打电话给保险公司,被告知要等很久,于是决定先试着跑到边上的 Jiffy Lube(修车铺)去求助。

来个小哥哥,带来了 jumper cable,但是发现不够长。

但是人家不是混白饭的,他凭借高超的超近距离停车技艺,在我的(瞎)指挥下,他泊车成功。

于是冒着吧 cable 扯断的风险,终于勉强连上,接上电,车灯马上亮了。

我们欢呼击掌 (✧∇✧)╯╰(✧∇✧)̣ —— Oh year…

然后我说,启动了,把钥匙还给我吧,我这就把车开到修车铺去。

他说,好,车钥匙不是在你那吗?

我马上有了不祥的预感…… o(╥﹏╥)o

果然,发现车钥匙落在车里了,一接电,车门居然自动锁上了…… 凸 (艹皿艹 )

小哥说,凭他多年的修车经验,车都有探测器的,钥匙在车里是锁不上的,放宽心吧。\(^o^)/

研究 20 分钟以后,他终于承认——好吧,我们碰上了一个“例外”…… 〒▽〒

我:@#¥%……&*~

面面相觑……

务实的我们马上找到了下一步方案,他决定载着我回我家去取备用钥匙。

到家发现平时都是用车载遥控开车库门的,没带家门钥匙。(*/ω\*)

更糟的是,平时从来不锁的后门,昨晚我哪个筋搭错了,居然锁上了,现在进不去了。

面面相觑 x2 ……

凭着工程师的基本技能,强行撬开车库门,进入家里面。ヾ(◍°∇°◍)ノ゙

但是,找不到备用钥匙,遂打电话给我老婆,她说她带回国了……

面面相觑 x3 ……

小哥说,不急,他有人脉!他有好哥们可以过来撬车锁。联系以后,说 45 分钟后就到。

于是我们开始闲聊,他和我吐槽讨厌的老板,我们聊生活的艰辛,居然扯出惺惺相惜的感觉……

可是两个小时过去了,他老板派人来拉他回去干活,可他哥们说还堵在路上……

面面相觑 x4 ……

面对这不靠谱的人脉,无奈决定不等了,我再打电话给保险公司。

保险公司问,你是不是刚才电话说电池挂掉的那个客户?

我说是。

他问,那好,电池挂掉之后,你又是如何能把钥匙锁车里的?

我叹了一口气说,这个故事太长,太难以置信,还是不解释了吧…… 〒▽〒

于是保险公司说还要再等一个小时……

天,你们是从外太空派人来吗?

半个小时以后,小哥的双臂纹着各种带鱼、皮皮虾等海产品的好哥们终于来了!

拿出一堆工具,一看就是撬锁专业的。

咣当咣当一通熟练操作,果然 5 分钟解决问题。O(∩_∩)O~

我强行忍住没问,“为什么你撬锁那么熟练?”。

把车开到 JiffyLube,被告知没有配套电池……

于是开车到 O’Reilly(汽配商店),另一个小哥哥掏出一堆的工具帮我换电池。

嗯,一看就是专业的。看着就靠谱。

半个小时以后,旧电池纹丝不动,死活卸不下来……

他问,我们可以用(蛮)力撬吗?

我…… 凸 (艹皿艹 )

好吧,我不忍心看了。

终于把旧电池弄下来了,也终于把电池换上了,这时候已经是晚上了。

我说谢谢谢谢, 终于帮我解决了问题(心里想着我擦我可怜的车啊)。

对于如此美妙的一个下午,仿佛八点档电视剧的剧本一般,我已经无力吐槽。

这件事情以后,我鼓励自己说:对于生命中各种扯淡的事情,我已经可以笑着面对了。

要不,还能怎的?╮(╯▽╰)╭

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/2PXUhcy

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 一点不同的看法

最近微信的朋友圈和公众号,被 《离开华为三年,我才真正认同狼性文化》 这样一篇文章刷屏了。基本上,评论都是正面的,表示支持、理解,或者赞赏。还有许多人表示,正是因为华为这样的狼性文化,这样的领导管理方式,才造就了公司今天的成就。

一开始我也没有太在意,后来发现大量的一边倒的正面评价和转发,我觉得我应该唱个反调,在这里谈谈不同的看法。如果您还未读过原文,不妨先移步阅读。

对于文中的观点,除去在开头的案例,我大致是认可的。特别是强调了实打实地做事给钱,坚持原则和不找借口,我觉得是值得用来树立一个好的典范的。只是开头这个案例太过瘆人,太过引起不适:

同事为与家人团聚,想调来我们办事处。第一年没调成,但因流露要走,被部门领导毫不客气打 C;第二年调来了,考核按规定仍在原部门手上,又是 C。

C 是一个很糟糕的绩效,在华为连续两次打 C 就是要淘汰走人的。而显然,文中的情况,打 C 的原因并非绩效不好,而是同事想调动,“因为流露要走”,连续两年都拿了 C。

在我看来,这样的事实确实够悲哀,但也并非多么稀奇。可是,高级主管对事件申诉的回应却荒谬到不可理喻的程度:

我和我领导为他的事向上级申诉。中国区某大领导回应:制度就是这样的,谁知道你们有没有猫腻和包庇?谁都这样来闹,这么大一家公司还怎么运作?

我在华为也呆过几年了,第一次听到有“想调动就要考评打 C”这样的制度,简直是无稽之谈! 公司需要的是接受雇佣关系的职场人,而不是洗过脑的光讲“忠诚”的员工!更糟的是,居然还有那么多人在文章后头跟风喊好?

而这进一步的反问“谁知道你们有没有猫腻和包庇?”,立即把员工摆在了不信任的对立面。

紧接着又一个反问“谁都这样来闹,这么大一家公司还怎么运作?”我的乖乖,真会上纲上线,要把公司运作那么大的锅推到这位员工头上了。

有一些评论则强调,其理由“为与家人团聚”是一个核心争议点,是应该值得理解的,是应该得到安抚的……后半句话其实没错, 可这是问题的核心吗? 我就是不为了这个原因,我就是希望换个环境,我就是不愿意透露原因,哪怕我就是想“换个窗口的风景”,只是单纯地希望调动,而且也只是表达了这样的诉求,仅此而已,有任何错吗?

文中也强调了,该员工并未有出格的做法,“一个勤勉踏实的技术骨干,即被辞退。一点儿转圜余地都没有。”因此假想员工在诉求表达以后跟进了不职业地做法是没有根据的。

正如同在我离职以后对华为正反两面的评价一样,我认为,朋友圈里也好,公众号也好,发表观点的时候, 大家大多是具备客观和理性分析事物的能力的,而即便实际工作并不理想,心中也应当有一杆相对理想的孰是孰非的秤

我一直对某些媒体有些厌恶,主要是把人神话,把事物绝对化。就好比好人就饮仙露,喝圣水,坏人就臭得彻头彻尾。华为的成功毫无疑问,但是这样荒唐的事情居然还能够拿过来反着用,把黑的洗成白的,实在是令人发指。

当然,以上借题发挥得有些远,现在话说回来,我对于文章的作者并没有任何鄙夷之意味,我只是对于这样一股跟风捧赞而缺少合理分析思考的潮流,感到无比遗憾。

狼性文化能和“怀柔”的包容文化结合起来吗?我觉得可能,但是很难,但为了不虚化本文的主旨,他日再说。

就这样吧。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/2xlBIam

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share