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

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

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

 

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

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

我们先来看一个数据。下图来自 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

【四火】 谈谈微信的信息流

最近才更新到微信的最新版本,早有耳闻公众号变成了微博似的信息流展示信息。之前也没有太在意,这次微信客户端版本更新以后,发现坏了坏了,以往的阅读习惯已经被彻底毁掉了。下面两图都是我手机上的截图,左边是新的信息流模式,右边是信息流界面下点击右上角图标,回到的“类似以往”的基于订阅号发布者的模式。

image1 image2

首先我要澄清的是,我认为信息流是绝大多数 SNS 软件都乐意采用的信息传递模式,简洁而且高效,包括我经常使用的那些应用,比如微博,比如知乎,比如 LinkedIn,甚至绝大多数 RSS 软件,因此,它绝不是一个新东西。毫无疑问,基于信息和基于信息发布账号(公众号)的方式比较起来,通常前者更有优势,但是此事不绝对,而且很遗憾的是,在微信这块地盘上,对于多数用户来说它恰恰就是一个反例。

别急,听我慢慢道来。

先谈一谈这方面的老大哥微博

为什么要谈微博?因为 在微博出现以前,在国内你找不到一个像微博这样能够在非双向联系,而仅靠单方面关注中迅速扩散消息的软件了 。它的革命性是在多方面都是毋庸置疑的。想想微博出现以前,互联网上消息要扩散有哪些典型方式?博客?显然无助于迅速扩散消息,而且作为快餐消息的载体明显不适宜。新闻?新闻只能说还是基于 Web 1.0 的模式,它和 Web 2.0 的最大区别是,普通的用户无法成为主要的信息创造者。QQ、MSN,甚至人人网?它们虽然差异很大,但是都是基于“好友”的方式,利用的是“杀熟”,而非微博这种以明星为核心用户(与草根为核心用户相反)来决定的信息传递群体完全不同,信息扩散速度也慢得多。扯一句题外话,应该说,一般情况下,信息扩散速度越快,国家机器的审查就越困难。在这个信息爆炸的时代,最大的优势当然是信息自身。可是除了信息本身的价值,信息出现的位置和时机至关重要。利用时间来组织信息,把越新的信息越往上放,非常有助于实时性软件,或者接近实时的软件扩散信息。

于是,微博出现了。和其它成熟的 SNS 产品不同,在当时你根本不可能找到一个相近功能(相近功能是指上文所述)的替代品。但是,纯粹的基于时间线来调整信息优先级是有很多问题的。虽说从技术层面来看,这种简单的方式,无论是实现还是优化,都有相对成熟而且有效的方式。比如根据不同的用户量采用 push 还是 pull 的模式,比如采用从冷到热分级存储,等等等等,我在 这篇介绍系统设计典型问题的文 中曾经介绍过,举的例子是 Twitter。

最大的问题就是,对用户来说, 信息重要性的衡量,绝不是一个简单的基于时间的逻辑 。虽说越是实时的软件,时间因素的重要性占比越大。比方说,微博的时间线重要性,就要比 RSS 软件高得多。但是,重要性的衡量不能仅仅靠时间。微博有 转发机制,这个机制保证了,热门的消息,即便不那么“新”,它依然能够经常在眼前出现 。而如今的微博和 Twitter,除了转发机制自身,都还有自己评估“重要消息”的一套办法,即便错过了,即便没有看到它的转发,它依然有机会回到你的视野里面。这个弥补,是一定需要引入基于用户特征的机器学习的,否则对于消息重要程度的的认知无从谈起。咱们暂且不论是转发机制还是这个额外的重要消息评估机制,它们毫无疑问都是对时间线弊端的弥补。

好,再回到微信公众号消息上面。

先看看基于时间信息流这一半

首先,微信公众号文章发布的实时性如何?有一定实时性,但是远没有那么高的实时性,也就是说,9 点钟的消息,我 11 点看到,也没什么大不了的。从这个角度说,基于时间的信息流,有益,但多数情况下并不能带来特别大的好处。而且,微信信息流优先级还不完善,用户更感兴趣的内容很容易被淹没在茫茫信息大海之中。

其次,微信公众号的文章数量如何?这是一个非常影响信息组织决策的因素。如果文章数量众多,那么基于信息流一定程度上可以提高浏览效率。或者说,如果有 1000 条信息,用户站在时间线的顶端,眼睛和手指一起工作,扫到了其中的 100 条,然后点开了其中的 10 条阅读,并对其中的 1 条感兴趣并完成发布者的关注。这听起来似乎是一个说得过去的场景。可是,如果没有那么多订阅号呢?公众号每日发布的文章数量是有限的,多数公众号每天就发那么一两条(其实这是微信非常有远见的一点,文章发布数量的限制必然督促发布者提高文章质量,而非单纯用数量来提高过目率,可是微信现在在抽他自己的嘴巴),而 大多数用户,恰恰没有那么多订阅号,也就没有那么多需要一扫而过的标题信息块,他们更在乎的是消息的质量(这也是“置顶公众号”一条非常重要的功能,能获得用户置顶的公众号,想必在文章内容上有着特殊的认可)。但是信息流以后呢?文章质量的重要程度,明显下降。

再说说基于订阅号的这另一半

订阅号最大的好处,在于基于消息发布者的消息组织。比如说,我订阅了 20 个公众号,但是其中 3 个我特别喜欢,我希望不要错过它们每一条,这就是这一方式优势的一个体现。

这种方式完全脱离时间线了吗?并没有。普通公众号的排列,是根据最新发布消息来完成的,也就是说,勤奋的公众号,掌握发布时机的公众号,还是能够得以在非置顶区域占据一个有利的位置。当然,也只能占领一个位置,而且由于每日发布文章数量的限制, 这种“勤能补拙”带来的收益,还是明显敌不过文章质量带来的好处

这种方式还有其它缺点吗?当然。其中一条,毫无疑问它也被微信的团队认识到了,如果没有置顶,发布消息不那么频繁的公众号,特别是在订阅号较多的情况下,自然被积压到了下面,脱离了用户视线的热区。即便这样的文章质量再优秀,也很难敌国信息轰炸带来的淹没效果。

说了这些,你可能也感觉到了,如果微信的产品经理们(未必是张小龙一人的主意),我大胆猜想,他们都是重度用户(我们说一个优秀的产品经理得首先是一个产品的重度用户,这没错啊),他们都习惯于订阅大量的公众号,而且文章质量的层次对他们来说没有“那么大”的区分度,那么很容易就会走上信息流这样的传统路数上。但是, 这就是“重度用户”们的短见,“越了解产品,未必就越能设计好产品”一个绝佳的例子

我猜,未来微信一定会回滚到以往的基于订阅号发布者的模式去。或者至少,给用户这个选项(现在这个点击信息流右上角图标的切换不伦不类,不但需要额外的一次点击,而且在切换后“未读消息”的功能也丢失了)。

从大的互联网 SNS 产品生态的角度来说,我是更希望看到多种信息推送模式的,信息流已经泛滥成灾了,基于订阅号的模式,其实本是很好的求异而生。

这件事又让我想起,在朋友圈中推广告等等的事情。朋友圈也好,公众号也好,腾讯自己先革的 QQ 的命,再把它做大,所以才有了如今微信这块大蛋糕。腾讯的产品经理们,敢于去革很成功的产品的命,我还是非常佩服的。但是能不能保持头脑清醒,明确核心价值,守住节操而不短视,犯了错又敢于回头,就是另一回事了。

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

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

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

【四火】 招聘有多重要?

A red vintage “for hire” sign招聘有多重要?

很重要……

嗯,废话!

说“很重要”的确是废话,而没有比较就没有差异,同样一句“很重要”我看到许多人理解其程度实际上大相径庭。 在很多互联网公司,招聘被视为“最重要”的事情。这是令许多人不理解,甚至觉得不可思议的事情 ,这里的“许多人”也包括曾经的我。公司不开展业务吗?不管理员工吗?不和了解客户需求吗?这些事情哪个不比招聘重要呢?

中午吃饭的时候,同事老兔和我算了这么一笔账。估算非常之粗略,请勿以之作为任何有效依据,但是从大略上足以窥其端倪。

  1. 假如一个勤奋的中级程序员工程师,一年薪水 200K 的话,一年 365 天,大约有 52 周,扣掉双休日还有 365-52*2 = 261 天,加上法定假大概 10 天,休假大约 3 周,还有乱七八糟的病假、事假大约 10 天,也就是说,工作的时间只有 261-10-3*7-10=221 天,平均每个工作日的薪水是 200K/221≈$905,那么按照多数人朝九晚五且扣除一小时午休等原因的一小时以后,每天工作 7 小时,时薪大约是$905/7=$129。
  2. 另一方面,考虑 Google、FB、Microsoft、Amazon 之类的知名互联网公司,粗略地如下假定:onsite 都要经过 5 轮左右的面试,每轮大约 1 小时,外加最少 1 小时左右的电话面试(有些电话面试要两轮),而且电话面试的录取比例大概是 1/3,所以每一个 onsite 认为绑定了三轮电话面试,debrief meeting 讨论面试情况半小时,以及面试官的面试准备,和面试完毕后 report 的撰写半小时后,那么光是工程师就要投入 5+3*1+0.5+0.5=9 小时,按照时薪算就要耽误掉$129*9=$1161,再加上 HR 和 recruiter 等其他人的工作投入,场地费、有时会有的餐旅费等等,onsite 一个人的成本平均在$1300 往上。
  3. 即便这样的投入后,多数结果当然都是没有录用的,即便给了 offer,还有多家公司在 offer 上的竞争。很多公司的 onsite 的录取率都在 40% 左右,而最终入职率的百分比就要掉到 20% 以下。所以这个数还需要调整:$1300/0.2 = $6500。花了那么多钱,才能录用一个工程师。
  4. 这个计算已经触目惊心了,招人的成本看起来是非常巨大的,而事实上,这个数会更大。考虑其他的开销,它就更扎眼了。比如和招聘机构合作的年费,比如招聘校园行宣讲的费用,比如工程师内推的 bonus(普通工程师通常在$1000 ~ $2000)……

所以,就如同我一位老朋友程序员所说,“工程师是很贵的”。

可是,我要说的是,这只是“小钱”。

什么!?

为什么?

因为对于许多互联网公司来说, 招聘这个环节,和后面的环节比起来,性价比太高了,投入相对更值得 。在招聘上省钱,很有可能,会让之后的团队运作付出多得多的代价,还不一定能识别并挽回造成的损失。

也许你会猜,我大概会举招聘的 bar 太低,入职员工技术能力不足,拖累团队的例子。诚然,这样的例子很典型、很普遍,但是这方面绝大多数团队和招聘流程都会关注,并无新意可言。而且, 对于一个技术或者业务能力不足的人,无论在决策还是实现层面,由于缺少技术或者业务影响力,往往造成的负面影响比较有限 ,换言之,更可怕的人,可能是技术或者业务足够强,但是种种原因不契合团队,严重影响工作输出的那些,而这,足以带来超出想象的破坏力。

经历过这样一个例子:

有一位黑客界的牛人,费了九牛二虎之力把他招到团队,结果入职以后工作能力并不达标,或者说,并不契合他所擅长的内容和方式,结果搞出一大堆问题不说,deliver 也不合格,同事不得不跟在他后面给他收拾残局,给他的代码修 bug、打补丁,他本人更是非常痛苦。最后他自己和公司双方都选择“解脱”,他入职不到半年就离职了。

其实这个问题就出在招聘,他至少在某些方面得到过业界的证明,他拥有顶尖的某些能力。可是无论是工作方法上,还是向往的工作内容和团队的契合程度,都不符合要求。

一个团队的包容力固然重要,可它依然是有限的。 太多的鸡汤文推崇招募牛人,可随便什么牛人放到一起工作就可以做得很好,这只是一厢情愿,它只在书本上出现

再比如这个更可怕的例子:

有一种可怕的开会,特别是那些十几个人的团队,一开就是一个小时的会议,结果变成了神仙大会,扯的东西看似工作相关,实则都是一些遥远而不甚关联的话题。每一次开会就是十几个小时工时的浪费。按照上面粗略的时薪计算,开销可观。

什么情况下会这样?

招来不干实事,却口若悬河的人。更可怕的是这样的人混成了团队骨干。于是带着一帮人天天在会议上侃大山。

招聘就是这样,招得好,公司和团队长期受益,招得不好,长期危害。

于是有人说,招聘小投入,等到入职以后再来衡量绩效不就好了吗?绩效不好就裁掉,或者其它方式中止合同。经历实战才能出英雄,不是吗?

理儿是这个理儿,可这个逻辑存在几个致命伤:

  1. 入职后的绩效衡量,等到得到结果的时候,羊已亡,无论补牢是否已晚。有很多后果是很难弥补的。
  2. 这个绩效衡量,又怎样保证尽可能客观而有效?一个“最能混”的工程师,也许能够有十种百种奇葩的办法拿到好的绩效,却没有为团队带来真正等效的价值。
  3. 这里 还忽视了中止合同的代价 。虽说合同都是 at will 的,法律上上午说离职,下午就可以滚蛋的。除非涉及种族歧视等法律底线,极少有公司这样做,如果因为绩效原因,通常这样的合同终止,公司都会给员工以数个月的补救或缓冲时间。原因很简单,一个习惯于中止合同的公司,名声就臭了,谁还愿意来?
  4. ……

更重要的,也是我要提醒的是,我们不能总把眼光放在“不损害团队利益”这样低层次的层面,而应该盯着怎样提升团队能力这个层面。

招聘就像是唯一的一个损失极小的影响产品方方面面的环节,如果不努力招聘更好的人,怎样要求最后发布的产品变得更好?

这也是 Amazon 最初定下的,要求招的人,“比团队中 50% 以上的人更好”这个说辞的由来。

若说起招聘环节在整个公司运作中的位置,它其实和软件工程里的项目流程同理,越早发现 bug 代价越小

从招聘,到入职,到团队建设,到项目输出,整个流程下来,总要在一个环节上面付出很大的代价。如果招聘做不好,那么倒霉的就是后面的环节。这也像软件工程的项目流程一样,如果设计做不好,那么糟糕的设计带来糟糕的版本质量,就要靠大量的测试来弥补,多数还补不过来;而如果测试也草草了事,那就要靠疯狂的 bug fixing 和打 patch 来弥补,还几乎肯定会造成大得多的后果。越往后,代价越大,效果也越差。

因此,把问题解决得越早越好。把工程质量这个 bar 抬高,抬得越早越好,不如就从筛选工程师开始。

招聘到的工程师不只是优秀,还符合团队需要,那么在后面的流程中,就可以减少很多投入。比如,不需要花钱请人监督工程师的工作,因为工程师又自我鞭策的能力;比如,不需要大量的团队建设活动,因为工作态度和方法上彼此都有大致相似的观点;再比如,不需要招许多测试来保证质量,因为良好的设计和实现阶段的开发期测试已经足够好;比如,不需要再维护优化环节投入很多专职人员,是因为良好的稳定性、易用性和可扩展性配合好用的工具使得开发团队自身就可以搞定这些事情。

最后,回到招聘本身。面试是双向的,一个草草了事的招聘几乎意味着一家草草了事的公司。想知道未来的团队氛围是不是适合自己,那么看看是不是和面试的人聊得来;想知道公司的技术实力如何,那就看看招聘过程反映出来的技术怎样;想知道入职以后身边的人会不会优秀而且契合,那就看看来面试你的面试官是不是优秀,招聘是不是严格且谨慎吧。

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

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

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

【四火】 程序员懂业务有多重要?

Image result for complex程序员懂业务有多重要?印象中我从来都说,“很重要”这句没有营养的废话。在许多项目中,业务才是真正驱使价值兑现(冠冕堂皇的说法,基本上意思就是“赚钱”)的法宝,而技术实际上有诸多选择,选择某一项并无太大区别。可是,老实说,下意识地,在技术和业务难以两全其美的时候,我还是倾向于选择那些从技术角度更有趣,但是业务上显得没“那么”重要的项目。我不讳认这一点,但是随着这些年的经验积累,或者说经历的项目的洗礼,业务的分量已经越来越大了。

在华为的时候,我做过一些杂七杂八的项目,其中最大的一个项目是一个大型的电信门户网站,由于我参与的是基线版本的研发,定制业务少,变态需求少,扩展性、性能、可维护性这些技术层面的因素考虑更多,因而总体来看,还可以说是一个技术比重明显大过业务的项目。

来到亚马逊,换过几个 team,第一个呆的时间比较长的 team 是 Demand Forecasting(销量预测),由于团队比较成熟,组织结构无论是人员上还是代码上,解耦都做得还可以,因而我更关心的是数据的 ETL 过程、schema、版本、可视化等等这些通用而并不耦合业务逻辑的东西。我们当然有业务方面的需求,但是这个 team 的核心还是在数据上面,大量的机器学习内容,不太可能内建太多的业务逻辑,主要影响销量预测还是数据本身。但是这个团队中,我接触了不少领域知识,这是一个比较大的变化,而这部分和预测算法,以及机器学习相关的领域知识,不同于某些典型的纯业务范畴的领域知识(比如说许多医疗领域、金融领域等等),可以说是技术和业务之间的灰色地带——既有技术的部分,也有业务的部分。

接着是 Contribution Profit 这个组,计算成本和盈利。从架构和系统上和大数据更深入地打交道,却基本上没有了机器学习的内容。主要原因在于,成本和盈利情况的计算,并不,或者说基本上不需要机器学习的技术,主要还是一些复杂的统计量化的方法,包括一大堆逻辑纷繁的公式。所以从业务和技术的角度上看,每天既要从系统上和元数据角度去解决那些大数据计算存储方面的问题,又要深挖业务逻辑,尝试去理解一些数值的缘由。加上我们的工具不足够出色,许多本来应该由数据分析师(Data Analyst)来做的工作,被迫转嫁到了程序员工程师的头上。这个角度看,业务逻辑的比重已经非常大了。当时我们组的同事也可以大致上分成两部分,一部分擅长业务,一部分擅长技术。

现在来到 Oracle,在 Storekeeper 组每天的工作包含了云设备(包括 instance 等等)管理,我最初的理解是,应该说工程师主要的贡献应该是提供不同种类的工具,让 Data Center 的技术人员去使用它们来管理。但是,和上面一条的情况类似,工具不足够好用,加之我们算是一个相对比较年轻的团队,还有很多相对混乱的地方,有大量的业务问题需要工程师介入以后才能解决。比方说某些数据的修改,由于工具的缺乏,这些现场的技术人员只能给工程师开 ticket,然后由工程师去更新数据。毫无疑问,这里存在大量的业务逻辑需要厘清,每当新需求分析的时候,通常比技术层面难度更高的是以沟通和梳理业务为主的部分,去和许许多多不同的用户聊,去现场了解情况,去和不同的 team 谈,从而逐步理清思路,了解问题,给出可行的解决方案。我觉得这些事情在一个足够成熟的团队中,是很难遇到的,即是机遇,亦是挑战,很难一刀切谈好坏。

老实说,曾经业务的东西从打心眼里是远不如技术受到我的重视的,再加上我换了那么多领域,我一直觉得只有技术的东西才是持久的,业务的东西却一直在变。但是这样的观点也在慢慢改变。一个是我留意到,有一些同事能够专注于某一领域(比如说 billing 系统,做了几年,换了几个团队,甚至公司,却一直研究账单系统;再比如和我现在打交道的一位 TPM,在亚马逊、微软干过,现在来到 Oracle,都在云计算的最底层处理涉及硬件和设备的需求,考虑到本来云计算就没多少年,在这一块领域,她可以说是非常罕见的老江湖了),这一旦在进一步职业选择的时候,如果选择到了相同的领域,无疑是在经验上有很大优势的。这也促使我在 这一次求职 的时候所说,希望在几年后的三十五岁的时候,明确一个大致上希望精进的方向。也许未来的新业务难以预测(比如哪怕就在五年前有谁能知道区块链居然能火成这样?),但是有一个大致熟知的领域为根基去伸展枝叶,会比一直没有清晰的门路强。当然,我不觉得之前的各个业务领域的积累是浪费,毕竟,眼界不只取决于深度,还取决于广度。

程序员工程师,毕竟主要做的是工程,不是研究。和生活更紧密,和实际问题更贴近,因而有大量的非技术问题和知识需要把握。入职以后,今年给自己的一个小目标,就是想提高包括沟通和业务理解在内的软实力,一定程度上也是我的短板。业务本身兴许未来能用到,更多的可能是用不到,但是对于业务和技术两条腿走路的多数程序员来说,瘸了哪一条都显得受限许多。

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

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

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

【四火】 为什么云计算服务是亚马逊先做出来?

Image result for aws google cloud azure最近看了一个知乎的帖子,大家讨论为什么是Amazon先把云计算服务做出来,而不是Google。类似的问题我遇到过好几次了,之前还在亚马逊的时候,我觉得利益相关等等原因,自己不太适合回答这个问题;而现在,又看到各路人马大神已经把这个问题从各个角度分析得底朝天了,于是觉得似乎又没有太大必要了。不过现在,回头看到这个帖子的时候,我还想再从我的视角总结总结,不只是为什么Amazon先把云服务做出来,还有为什么现在它可以一路领先。虽然说Google也是云服务的三驾马车之一(另两驾是Amazon和微软),但如今许多方面它都和另两驾还有不少的差距。我记得刚加入Oracle的时候,但凡听说我从Amazon来,就理所当然地assume我来自AWS,足见其在业界AWS的影响力之巨。而事实上,Amazon的范畴远比AWS大,而且AWS也是这些年才火起来的。

首先,最本质的一点,是深入到公司DNA中务实的文化,而DNA的形成发展,来自于残酷的发展环境。简单而不准确地说,Google是精英文化,而Amazon是实用文化。Google的广告业务太赚钱了,搜索引擎的广告是互联网最著名的印钞机。多数情况下,这当然是好事,但是当一个业务太赚钱了以后,公司就没法体会到生存的压力,公司老大就没法在互联网泡沫的谷底时顶着巨大压力和骨干员工说“我不在乎股价”而成为美谈。国内的百度就是一个一定程度上非常糟糕的例子。

Amazon的压力很大,而且传统零售业的利润率,是远远无法和Google的广告相比的。眼看着零售业的空间慢慢蚕食殆尽,Amazon迫切需要新的业务增长点,因此从一定意义上说,这是残酷的环境逼出来的。如今,我们看到Amazon讲frugal,Amazon讲deliver,甚至都有不少人抱怨在公司里洗脑了,过度强调leadership了,而这其实都是源于公司的DNA。

扯远一点,讲到务实的文化,突然想起了我前一家公司——华为。从公司层面上说,它就如同是中国的亚马逊一般成功,而它的务实,我觉得可以用我在新员工培训的时候听到的这样一些话来概括,比如“小改进,大奖励”,说的是,别给公司大的事情说三道四,着眼手头的小事情,改进了工作就有回报;还有一句是,“领先一小步是优势,领先一大步是烈士”,说的也是做实用的创新。事实上我并不认同这些说法,但是依然,它们是务实文化很好的佐证。

其次,有了文化的铺垫,依然不是所有人都可以玩云服务的,在最开始的时候,Amazon搞得开,搞得快。需要有软硬资源上的前提:

疯狂的迭代和发布。Google对于学术菁英以及工程艺术的追求,无其它公司可出其右。Amazon就看起来“土”很多,比如说,代码质量如何?难说追求完美。但是其迭代的能力简直可以说“令人发指”。Amazon几乎不会花上漫长的时间做设计,做架构,我们看到的,都是大量不完美的,甚至存在着明显缺陷的产品,然后开始丧心病狂的迭代。哪怕到现在,打开AWS console上面的服务列表,我想多数人都难以说知道全部的service都是做什么的,我记得最快的时候,每几天就有新的AWS service发布。即便是非AWS的内部产品也是如此,我记得在Amazon工作的时候,内部的工具多而且新,花在这些东西上的学习成本着实可不低,而且,每年工程师都要投票淘汰那些不好用的工具。

大众工程师基础。这是很少人提及的一点,似乎凡是说到IT企业,都谈效率,谈自动化,谈机器替代人力。当然正确,可是要做到这些事情,实在不是——至少当今这个阶段不是——几个或者几十个呼风唤雨的工程师可以搞得定的。而众所周知电商的原因,Amazon工程师资源明显比较富足。许多方面Amazon的面试bar没有Google高,薪酬和工作环境通常也会和Google有一些差距,但是,无论是招人还是晋升,都接近实战。我把这些工程师叫做“大众工程师”,不是所谓的菁英,但也绝不是庸才,他们是真正是生力军。在疯狂扩张的时期,Amazon也可以保持招聘的效率和强度。直到现在,很多人都知道的一件事情,是Amazon薪资中的base,有着明确的上限,因此报酬要靠股票来弥补,而且股票都是按照年份递增发放,最大限度地把员工和公司的利益绑在一起。

丰富的硬件资源。这一点很多人也提到过,做电商的,而且做那么大的电商,哪个国家没有个疯狂的消费季呢?如同中国国内的双十一,美国的圣诞-元旦期间,以及后来大力经营的prime day,都需要大量的计算资源。而消费季以外,这些资源放着又是浪费,因此云服务的催生是自然而然的过程。

再回过头来看这三点,可见虽然说互联网公司那么多,甚至还有不少已经触及了云服务的边界,比如网格计算,比如私有大规模计算或者存储集群,却都没有真正发展起来,也不足为奇了。第二、三点把几乎所有中小公司全部过滤掉了,而第一点又把许多大公司都过滤掉了。

最后,我想强调一点,在云服务萌芽以后,需要保持亲民才能持续发展。

我想这与许多公司的策略是不同的,大公司当然是云服务的大客户,比如Microsoft有非常广泛的和不同潜在大客户合作的背景和建立起来的关系,在我来到Oracle以后我又见识到了极度aggressive的销售团队。但是Amazon的商业策略是完全不同的,这和他们的电商背景有关,小客户一直在它们的核心目标客户群之中。因为Amazon做零售,卖十几块甚至几块钱的东西,因此云服务的定位,特别是定价,就是从低端路线开始的。我在Amazon上面买东西,退款,这方面的体验,起码在北美完全无人能及。

我有个朋友,在国内做云服务,他和我讲过,他们比较过成本和定价的关系,发现如果他们采用和Amazon类似的定价策略,实在是没法赚钱。我不知道在最开始的时候Amazon云服务在美国的开始阶段是不是赚钱,但是我知道在Amazon进军中国的开始阶段,被中国的付费习惯和fraud折腾得非常痛苦。既然提到此,在这里扯一句题外话,北美的很多商业模式照搬到中国国内,是很难成功的,我们已经见过太多这样失败的例子,虽说似乎所有人都觊觎中国这样一条大肥鱼,Amazon自己的电商,收购卓越网以后,建库房、做物流,刚开始还可以称之为“眼光长远”,但终究也抵不过利润上的冷清,在国内如今不断走低,网站却慢慢地、悄悄地“淘宝化”,这方面也许我以后可以另开篇幅专门谈谈。

文末,我想思考和预测一下如今的云服务三驾马车的未来。我不觉得Google有能力去和微软以及Amazon竞争。Google依然会很成功,依然是小众和精尖的代名词,但是对于将如此遍及生活的云服务——我只能说DNA层面的东西是很难改变的,它很难做到像微软和Amazon那样再多条战线上面如此亲民。起码在北美,你可以不断地骂微软的东西臃肿而没有品位,可以不住地抗议Amazon对传统零售劳动力岗位的摧残,但是你还是不断地,不断地,不断地使用微软和Amazon的各种产品和服务……

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

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

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

【四火】 关于RESTful不足的思考

Related image在Amazon的时候,公司内有大量的组来维护不计其数的service,而service之间的通用通讯方式是公司内部的一个框架,协议是自定的,客户端也是内部的;现在到了Oracle,我看到这个变成了RESTful,也就是说,协议本身变成了最常见和适用的一种。我看到有太多论述RESTful优点的文章了,而实际工作中也确实有所体会,比如接口和报文的可读性好,不需要特制的客户端,上手和调试都比较容易等等。但是,如果看到某个东西被冠以过多正面的评价,就要当心了。我也慢慢地体会到了一些问题。不过,在谈谈我的思考之前,我想先明确一下我对REST的认识,而这点,鉴于历史原因,也是我不太愿意花时间争辩的内容。我认为REST是一种设计和架构的方式,体现了系统响应请求交互的风格,而非接口规约,更不是什么报文协议。

对于RESTful的四种HTTP/HTTPS的方法,我看到不同的工程师有着不同的理解,而这点,是缺少足够明确的约束的。

  • 第一个例子,GET、POST、PUT、DELETE分别表示对资源的获取、创建、修改和删除。但是实际操作中,我看到一些不一致的东西。比如修改,我见过有使用PUT的,使用POST的,也有使用PATCH的,很难讲孰对孰错,欠缺的是规约。
  • 第二个例子,使用GET来做查询,清晰简便,但是也有着自己的局限性,其中一个就是参数的携带。明文参数的方法并不适合传递吧比较多的参数,而且如果参数值不是普通字符串或者数值,而是数组等集合,它缺少清晰而友好的传递方式。于是我看到有一些工程师会使用POST来解决这样的问题,这无疑从某种程度上破坏了RESTful的一些规约。
  • 第三个例子——版本的指定:我以前所了解到的,版本是可以再请求头部的Accept头中指定的,但是我看到了一些把版本号放到URL中的解决方案。考虑到REST本来也只是一种方式和风格,不能说这样的做法就是错误的,但我觉得还是缺少一个在REST之上更为细致的协议或者规约。
  • 第四个例子,参数的指定方式,放到问号前面的URI里面去还是放到问号后面的参数键值对里面去,我看到了不一致的处理方式。
  • ……

对于资源名称的定义,也就是RESTful的核心,也不适用于许多问题的解决。我用过SOAP,也用过一些其他的XML协议,REST是更加简洁的一个。如果是针对简单实体的增删改查,RESTful无疑是有效的。换言之,它擅长通用性问题的解决,但是孱弱于特应性问题的处理。但是如果是一个复杂业务的封装,RESTful显得力不从心。这样的封装,之所以不任其发展为通用接口,就是考虑到某些业务的特殊性,而通用接口对于特定场景的优化是不足的。就像一个简单的二维表,一个简单的select-from语句可能就可以解决,但是当业务复杂到多数请求都需要join、filter、map,这就似乎很难用擅长通用性的REST来解决问题了,否则就要创造一大堆不易理解的、不易重用的名词在作为resource了。

前面提到过缺少REST之上更为细致的协议或者规约,这个可以进一步展开说。对于某些基于请求和响应的通用操作,和内部框架+协议的方式比较起来,不太容易统一。比如说鉴权,比如说流控,比如说性能监控,这些东西都是很常用的,但是我看到使用一个专有的内部框架会更方便地嵌入和推广这样的组件,而RESTful的结果就是各个项目组五花八门,对于具体字段的理解也是分歧不少。

最后一个,我想到的是客户端的生成,以前用到的内部框架,可以方便地生成客户端,而客户端的功能也比较强大。但是RESTful了以后,以往的一些客户端丰富的特性都要重头自己实现过,比如说复杂的参数校验,比如一些自动装包解包到业务对象的代码生成等等。事实上,这些工作是不可能省略掉的,没法借助框架完成,就要自己想办法做。我记得以往获知一个service,为了使用客户端,想了解一下schema,很容易就可以得到自动生成的文档,但是现在则完全不能。

基于这些种种的原因,如果从头来过,依然使用RESTful风格的service,为了保持各个service之间的一致性,兴许一个统一的API框架是值得的。我理解速度在如今软件企业中的地位,但是我们总得在和可维护性的博弈中取得一个平衡。

确实软件开发没有银弹,而我自认为对于RESTful不足的思考还是不够深刻,如果你有很好的认识,不妨告诉我。:)

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

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

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

【四火】 推荐最近玩的几款独立游戏

如今各种平台上的大作满天飞,可是不知道有多少人和我一样,很难对这些大作燃起热情。可是凭着怀旧的心态,去回味一下老游戏,或者所谓的“经典”的时候,却又发现时过境迁,物是人非,一样缺少玩下去的动力。平时工作生活就很忙了,留下属于自己的时间不太多,也不太愿意沉迷太多的时间给或新或老的游戏,再加上随着年龄的增长,似乎对越来越多的事情失去了兴趣。直到某些“独立游戏”出现,由于资金、人力的关系,它们大多没有绚烂的画面,繁冗的剧情,以及漫长的游戏时间,但是由于开发者可以决定它们的走向,始终围绕核心想法构建,于是它们或精致或别样,总能把某一游戏性发挥到极致,让我重新找到许多游戏的快乐。我不算什么资深玩家,在这里稍微推荐几款我非常喜欢的独立游戏。

《贪婪之枪》(Greedy Guns

应该说算横版过关游戏的一种,但是简单的打击、动作和解谜,加上收集各种武器的乐趣,足以让我把这个游戏流程研究来研究去的了。画面精致,风趣幽默,有一点点像合金弹头,但是又很不一样。整个过程路线很清晰,也没有过多的啰嗦的解谜、事件或者收集的要素。(我忽然想到一个反例——《保卫萝卜》,最开始的核心游戏性是无比清晰的,我也曾是铁粉,但是一代不如一代,到第三代的时候,腾讯把他收购了,系统越来越复杂,越来越慢,界面越来越繁杂,什么乱七八糟的公告、活动一股脑儿都出现了,而平衡性则走了下坡路——这游戏也就玩完了。为此我还写过一点点东西。)

360_shooting_256_nodither

《城堡毁灭者》(Castle Crashers

不同的搞笑角色和各种招式,耐玩的连招系统,颇有挑战性的游戏进程。场景丰富而统一,但是关卡适应性可以说很容易。和《贪婪之枪》比起来,最初的游戏画面并没有那么吸引我,但是玩起来真是非常引人入胜,打击做得也比较出色。一样具有规则比较简单,但是要达成多数甚至全部的动物球收集要素,非常具有挑战性,毕竟隐藏元素颇多。遗憾的是我没有和朋友一起玩,这个游戏是支持多玩家的。

cc2

《神圣土豆的武器店》(Holy Potatoes! A Weapon Shop?!

如果说前面的还具有诸多动作成分的话,这款游戏则完完全全是经营养成加策略的风格了。应该说刚上手,其中的规则需要花一些时间去熟悉和掌握,但是之后就可以把主要的精力放到经营和策略的思考上面去了。故事本身很简单,要给各路英雄打造最适合它们的武器,并且卖出高价,以升级设备,聘请更优秀的匠人。对话幽默,而且角色设计都很有喜感。话说回来,游戏制作上也有遗憾,比如难度曲线的不合理——开始的时候难度有一定挑战性,很吸引人,但是到游戏后期,特别是技巧掌握以后,制造武器的效率太高,角色能力太过强大,于是损失了游戏性。但是总体来看,依然是一款非常吸引我的作品。

manage-agency

《史诗经理》(Epic Manager

非常棒的经营、策略和战棋型游戏。故事主要是讲,要带领一支(以及到后来的2、3支)冒险团队,在一个混乱危险的世界里面接纳任务,招募各类角色,完成任务赚取钱财和经营团队。这个游戏吸引我之处在于,把经营、策略和战棋RPG结合得非常出色。需要动脑,并且需要非常努力地开动脑筋,想方设法把这个团队维持下去,发展下去。要说遗憾我觉得有二,一个是对于热衷于培养一个高潜力角色的玩家来说并不友好,游戏本身的思路要求玩家舍得替换掉那些成长起来但薪资代价过高的角色;另一个是在几个年度后游戏落入尾声,对于喜爱长时间经营培养团队的玩家来说,觉得意犹未尽但是游戏必须在那个时间点结束。

SteamPage_ScreenShots_v2_04_Negotiate

就说这四款吧,这些独立游戏我非常推荐,也都放了官方链接,尤其是第一款和第四款。现在,回过头来想想,我发现这样优秀吸引人的独立游戏,都具备这样的几条特点:

  1. 极佳的游戏性。游戏的核心就是玩,不是什么画面也不是什么声音。举例来具体说,如果是打击动作为核心,那么打击感和角色响应玩家操作的动作必须非常自然流畅;如果追求策略,那么要让玩家得以在忍受范围的时间内上手,并且能够通过合理的难度曲线留住玩家。而这一点,并非有资金有人力就可以做到。为什么独立游戏更可能做到这一点?因为做决策的团队就可以是开发团队,最小化沟通损耗,敏捷、简单,但是高效,而且始终可以围绕在核心点子上面,避免被太多琐事耽误。
  2. 画面精致。游戏性是必要条件,但非充分条件。画面“精致”并不意味着画面“华丽”。为什么这些都是2D游戏?如果要做3D,独立游戏的资金和技术往往很难做到。但是2D游戏,画面风格的统一、配色和界面设计的清晰,这些都是可能做到的,也未必需要很大的开发成本。
  3. 简洁。简洁即包括界面、操作简单,容易入手(挖掘游戏潜在元素可以复杂,但是玩家上手不能复杂);还包括整个游戏世界中,玩家需要达成和追求的目标清晰简单——这两条都非常重要,任一条的违背将使得玩家难以在一定时间内获取足够的游戏乐趣,或者分散玩家游戏的核心乐趣。

最后,必须夸一下Steam平台,实在做得太棒了。现在独立游戏我基本都从Steam上找。有一些互联网服务我可以说是好多年的忠实用户,这样的数量很少,而Steam就是其中之一。

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

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

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

【四火】 关于国内程序员肉身翻墙

Image result for 翻墙本来是没有倾向谈论这个话题的,但是最近邮件或者微信问我这个问题的国内程序员朋友很多,我在这里一并介绍一下,也算作简单的解答。同样的问题就直接参阅即可。事实上,我很乐意收到这样或者那样的问题,也包括肉身翻墙这样的话题,但是也请大家注意一点礼貌,有好几次有程序员没头没脑地微信上跳出来问问题,然而话都说不清楚,或者连个招呼也不会打,更有甚者二话不说直接把log贴过来让我看问题,实在是让人觉得很不舒服。有些我回复了,有些我实在是不想回复了。另外,具体的问题我比较好解答,像有不少人问我,“你觉得美国怎么样?”,我都不知道从何说起。具体问题还是邮件沟通更合适,我答复起来也更舒服,微信更适合有一句没一句的扯淡。另外,要说明的是,因为我是14年搬到西雅图的,并不算待了很久,我也有一些其它国家的程序员朋友,但是我只谈论美国,因为我也没有其它的经历。

首先,我觉得需要问自己一个问题,为什么要出国工作?是一时脑热么?别人的饭碗里的饭,闻起来总是香的;别人的生活,看起来总是美的。但轮到自己的时候,却不一定如此。如果你想去哪个国家工作,那么至少办理旅游签证去玩一玩、看一看吧?签证有时候会很麻烦,这没错,可是连这样的事情都不做的,下了决心立了志愿又有多少可信度呢?现在旅行那么方便,旅游签证又已经是10年签了,出行应该说不能算什么问题。不同人生活上的追求千千万,找到自己最喜欢的,或许才是最合适的。而怎么才能认定喜欢,肯定是去看看最保险了。当明确了目的和原因,那么才往后思考才有足够的意义。

接着,我想泼一点冷水,谈谈我觉得在海外工作令我失去的东西。

1. 朋友和亲人。这不必细谈了。会认识新朋友,但是绝大多数的交际圈和亲人都会远去,而对于远行后父母养老的顾虑,也是很常见的。

2. 便捷的生活。我记得几年前住在北京的时候,下楼就是一条便利街,从吃饭剪头到购物遛狗,日常服务都有了,踢个球打个篮球,边上就是球场和gym,每天可以步行上班,怎一个方便了得……现在呢,不开车出门就相当于残疾一样,最近的公交车站要走很远,更何况公交系统远没有国内发达,经常一小时一班车,还得倒车才能去市区(西雅图)。

3. 职业生涯的某些可能。你可以认为是职业生涯的瓶颈。语言问题和文化问题是夹杂在一起的,本质上是一类问题,无法分开。程序员这样靠技术吃饭的职业,依然需要语言文化这样强力结合的软能力,而这一点,从我观察来看,中国人普遍有短板,基本上能够奋斗到很高职位的母文化为中国文化的程序员,凤毛麟角。

还有很多其他的方面,但主要是以上。知道这些很重要,是帮助冷静下来做trade off的。

至于好的一面,已经有太多的文字了,我只说一点:

体验。不止是生活上。能在世界软件大国中的top 2都当过工程师工作过,实在是一个非常难得的经历。

接着我才说肉身翻墙的方式。据我所知,有这样三种,难度依次增加:

1. 海外读书,现在留学不同于20年前,学校的选择余地也很大。我身边的大多数华人朋友就是在国内读的大学,然后跑出来读研究生。这种方式的好处在于来到美国在语言方面的压力会小一点,并且在学校里右足够的机会得到语言的强化和锻炼。毕业前可以实习,这也是很好的留下工作的机会,比社招面试成功率要高很多。学生签证到期可以申请18个月的opt,因此有若干次机会进行H1B的抽签,如果是美国硕士会有两次不同概率的机会,总体抽中的概率还是比较高的。

2. 在一些大型跨国企业工作,然后藉由L1签证transfer到国外去。这种方式的选择余地没有第一种大,但是适合那些已经走出学校的程序员,先要面试进入外企,然后根据这些外企的内部转岗政策,至少在国内干满一年后,获得海外职位(这很可能需要经过面试、推荐、商谈等不同的阶段)。这种方式的好处在于可以带家属,而且家属在冗长的流程申请到L2的EAD后可以工作。在L1期间如果公司支持,每年都可以申请H1B签证,但是如果没有美国本土的硕士经历,抽中的概率不大,这两年中每年抽中的概率大概不到三成。如果身份没有变化,L签证在5年后到期,必须离境。

3. 直接投海外简历。这种方式最难,并不只是美国直接招聘的公司凤毛麟角,不只是候选人考察bar高,还包括这种方式无法办理L签证,只能走H1B这一条路,这也就意味着能否抽中签证并非自己能够控制,概率见上。如果面试通过,但是H签证没抽到,有的公司会把你送到别的英语国家去等一年继续抽。对于那些拖家带口的程序员来说,这无疑增加了许多不确定性。

当然,无论是哪一种,都会面临大量的签证等等材料的准备,甚至年年如此。身份问题一直是一个比较烦人的问题,通常公司会联系律师代理帮助,但依然会花费很多的心思和时间,但如果对那些文件材料准备看了就头大,恨之入骨的程序员,这显然是件很不好的事情。

最后,回答两个常见的关于海外求职方面的问题。

英语有多重要?就面试而言,英语很重要,但是远没有专业能力重要。能够沟通交流这是必须,否则一定会影响能力的打分。特别是对于投海外简历有兴趣的程序员,电话面试中能够沟通交流是一个必须要做到的事情。在语言层面耽搁的时间越少,留给自己花在问题本身上的思考和沟通交流的时间就越多。现在英语可以不那么好,但是职业的发展来说,英语机会是一个必要条件。我见过不少中文说起来头头是道的程序员,讲英文却要命一样。

适应异地他乡的生活有多难?这要看怎么定义“适应”这个词。直接来工作的话,前三个月会特别困难一点。几年后绝大多数事情都没有太大问题。但是长远看,最大的困难还是在文化上,文化背景的关系,主流的文化圈子还是很难进入,当然我们自己也有自己熟悉的圈子。而这个困难,基本是终生的。这个问题要看你怎么看了,有的人在乎,有的人不在乎。

就说这些吧。

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

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

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