CodingTour —
ARTS #150

Algorithm

本周选择的算法题是：Convert BST to Greater Tree。

规则

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

img

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2:

Input: root = [0,null,1]
Output: [1,null,1]

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -104 <= Node.val <= 104
  • All the values in the tree are unique.
  • root is guaranteed to be a valid binary search tree.

Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Solution

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.dfs(root, 0)
        return root
    
    def dfs(self, root: Optional[TreeNode], base: int) -> Optional[TreeNode]:
        if root is None: return base

        right = self.dfs(root.right, base)
        left = self.dfs(root.left, root.val + right)

        root.val += right
        return left

Review

Stop Using JSON Web Tokens For Authentication (The wrong way).

感觉存在争议，作者的观点基于一个假设：JWT 被偷走了怎么办？这个问题和 JWT 本身是否安全已经无关了。

认同的点：

  • JWT 应该 short-lived
  • JWT 在连接各种三方服务上有一定的优势
  • JWT 可以避免 out of sync 问题，比较像 isAdmin 这类的字段就不该存在里面

现在业界有既满足 short-lived，又具备更高安全性的方案，比如把 access token 配合 refresh token 来使用，虽然会增加一定的成本和复杂度就是了。

Tip

无意中在 GitHub 上找到一份中国程序员容易发音错误的单词清单，还挺有意思的~

Share

假设你正在参与某个产品或者服务的开发，如果要求你提高产品和服务的商业价值，你会怎么去做呢？提高商业价值的手段又有哪些呢？

也许你会有一些对策，不过如果有一种工作方法可以通过迅速、持续地增加新功能，以此打败竞争对手，或者能够灵活地对不够完善的功能进行修正，你觉得怎么样？

Flickr 在 2009 年时发表了一篇名为 “10+ Deploys Per Day:Dev and Ops Cooperation at Flickr” 的演讲，将 Dev 与 Ops 联系了起来，让业界强烈感受到原来发布也可以做到如此“容易”，并提出了背后所需要的工具和文化。

用于应对变化的工具：

  • Automated infrastructure（基础设施自动化）
  • Shared version control（版本管理共享）
  • One step build and deploy（一站式构建和部署）
  • Feature flags（功能开关）
  • Shared metrics（共享指标数据）
  • ChatOps（即时通信机器人）

用于应对变化的文化：

  • Respect（尊重）
  • Trust（信任）
  • Healthy attitude about failure（正确认识失败）
  • Avoiding Blame（避免指责）

DevOps 是通过 Dev 和 Ops 的紧密合作来提高商业价值的工作方法、工具和文化。

DevOps 的优势：

  • 消除对个人的依赖
  • 减少团队之间的损耗
  • 提高产品品质

DevOps 反向驱动技术革新的案例：

  • 蓝绿部署
  • 不可变基础设施、基础设施即代码
  • CI & CD
  • 微服务架构

不需要套用业界已有的最佳实践，把 DevOps 的思想引入到组织里才是关键。

对既有组织来说，引入大抵分为三步：

  1. 实现个人效率化: 从小的地方开始实践，一步步培育适合 DevOps 生长的土壤
  2. 实现团队效率化: 在团队中实现效率化的难度和个人实现效率化的难度完全不同，使用这些工具倒不是什么难事，难的是要在团队开发中熟练使用，并形成一套理想的工作流程，只有做到了这一点，才算真正实现了效率化
  3. 融合架构: 前面都是尽量在沿用已有架构的前提下实现效率化，然而 DevOps 有一套自己追求的架构模式，这和在已有架构的基础上采用影响较小的方式逐步实现不太一样。比如微服务的架构设计风格，这些小的服务都是以业务、模块功能为单位构建的，都可以采用自动化部署机制进行独立部署，而且由于各个进程相互独立，所以每个服务都可以采用不同的编程语言来编写，也可以使用不同的存储技术

第3步其实也说明了最先进的基础设施，也不能和应用架构割裂开来，应该让两者以互相依赖、互相结合的形式一起工作。

最后从 DevOps 组织形式角度看，往往会划分成3种类型：

  • 没有专门的人，开发和运维通过密切合作完成 DevOps
  • 专门的 DevOps 团队，通常是以专家为中心组建的，他们的工作包括写基础设施代码、实现持续集成、进行版本控制等
  • 跨职能团队，由产品、设计、测试、开发、运维等不同职能的人组成的团队，通过共享各个领域的知识，提供“万能”的解决方案

最好的团队结构是什么？取决于企业当前的需求，变更组织结构的确能提高实现 DevOps 的速度，但通过“临时”团队或者采取技术性的解决方案也可以实现 DevOps，核心还是思想。