Algorithm
本周选择的算法题是：Construct String from Binary Tree
规则如下：
You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.
The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Input: Binary tree: [1,2,3,4]
1
/ \
2 3
/
4
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())",
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be "1(2(4))(3)".
Example 2:
Input: Binary tree: [1,2,3,null,4]
1
/ \
2 3
\
4
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example,
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
Solution
我实现的方案：
解法一：递归
Runtime：52 ms，快过 93.22%。
Memory：16 MB，低于 21.37%。
class Solution:
def tree2str(self, t: TreeNode) -> str:
if t is None:
return ''
if t.right:
return "%s(%s)(%s)" % (t.val, self.tree2str(t.left), self.tree2str(t.right))
elif t.left:
return "%s(%s)" % (t.val, self.tree2str(t.left))
else:
return "%s" % t.val
这周随机到的题很简单。
解法二：栈
Runtime：60 ms，快过 61.54%。
Memory：15.5 MB，低于 69.44%。
class Solution:
def tree2str(self, t: TreeNode) -> str:
if not t:
return ''
result, stack, visited = '', [t], set()
while stack:
node = stack[-1]
if node in visited:
stack.pop()
result += ')'
else:
visited.add(node)
result += '(%d' % node.val
if node.right and not node.left:
stack.append(node.right)
result += '()'
if node.left:
stack.append(node.left)
return result[1:-1]
Review
Microservice Architecture at Medium
Medium 是知名的优质内容社区，这是一篇关于微服务如何在 Medium 落地的文章。
我用 FAQ 的方式做了些总结：
什么是微服务架构？
微服务架构能让多个松耦合的服务协同工作，每个服务都是单一职责、高内聚，只负责自己的行为和数据。
微服务的设计原则有哪些？
- 单一职责 - 每个服务只做一件事
- 松耦合 - 服务彼此之间了解很少，一个服务器的变化不会引起其他服务的变化，服务间只通过公共接口通信
- 高内聚 - 每个服务封装相关的全部行为和数据，如果我们需要增加新的特性，所有的变化应该只局限在这一个服务内
如果不遵守：
- 单一职责 - 微服务会做太多事情，最终变成一个庞大的服务，付出了改动的成本，但是获取不到微服务的优势
- 松耦合 - 一个服务的改动将影响其他的服务，后果是不能安全、快速的部署，而这本来应该是微服务架构的优势，更重要的是，紧耦合会导致一些严重的问题，比如数据不一致、数据丢失等
- 高内聚 - 最终变成一个由一些服务混乱集合成的分布式单体应用，它们必须为一个新功能同时修改和部署，一个分布式单体应用通常比中心化的单体应用更糟糕，它的复杂度和服务间的协调成本更高，有时还要跨越多个团队
微服务的误区有哪些？
- 不是由几行代码组成的微任务，微服务的目的不是尽可能地拆分出小而多的服务，要满足上述三个原则
- 不是一定要由新技术构建，微服务能更容易地测试新技术，但这并不是主要目的，只要团队能从解耦的服务中受益，完全可以保持相同的技术栈
- 不是从头开始构建的，当你已经有了一个工作的很好的单体应用，你应该避免从头开始，直接从单体应用中提取出逻辑会更好，当然也要满足上述三个原则
是否要完全避免构建单体应用？
虽然微服务架构对新技术支持更好，但是它仍然有极高的复杂度，对于小型团队来说，单体应用通常仍然是更好的选择。不过为了在以后更容易地向微服务架构过渡，可以参照微服务的三大设计原则（单一职责、松耦合、高内聚），以组件化的方式来构建，这样和微服务相比，除了“服务”是由相同的技术栈构建，在同一进程内部署、运行外，没太大差别了。
什么时候开始更合适？
任何架构的调整不是随时都合适的，必须考虑眼下的工作、机会成本、分散注意力的成本、人力和资源等，确保一个合适的优先级。
其次，目前的架构是否达到了瓶颈。Medium 的早期架构采用的是 Node.js，但是计算量大、I/O重的工作不适合 Node.js，Medium 花了很多时间尝试改进它，但是收效甚微，它已经无法让 Medium 提供更好的产品。除了性能瓶颈，庞大的单体应用对产品开发的效率也有很大影响，所有的工程师都要在同一个应用内构建功能，耦合度很高，调整系统的某一块功能时，会担心影响到其他地方，决策变得保守，害怕大的改动。由于单体应用作为一个整体部署，当某一个 commit 出现问题导致部署不成功时，其他功能也部署不上。
除了性能、开发和部署外，对单体系统拓展也变得很难，无法拓展或者隔离不同的资源，只能整体拓展。
最后，单体应用使用的是相同的技术栈，无法为服务选择最合适的工具。
而微服务架构能解决这些问题。
Tip
本周学习到的一些内容：
- Python 中
/和//的区别：- 前者为浮点数除，floating point division；后者为整数除，floor division，或者叫 integer division
- 当然浮点数的”陷阱”也是存在的，当面对大数时，比如 10000000000000000000006：
- 10000000000000000000006 / 2 = 5e + 21
- 10000000000000000000006 // 2 = 5000000000000000000003
- 10000000000000000000006 / 2 != 10000000000000000000006 // 2
Share
本周分享：
如何做好 Code Review？
先对做不好的原因进行梳理：
- Reviewer 有时候很难理解代码的目的和背景
- 团队认为频繁或者耗时过长，影响进度
- 长期流于形式，实际改善作用不大
针对以上几点，可以设计出一个相对较好的方案：
- 在发出 PR 时写个文档做个清晰的说明，以便 Reviewer 了解其目的，促进 Reivew 的有效进行；再者写文档的过程也是重新梳理自己的逻辑，便于发现自己逻辑上的漏洞或者过于复杂，从而重新调整代码的实现
- 开发者的心态很重要，要能接受好的意见，不过 Review 总是给人感觉原先的代码不够好，长期这样的过程很容易给人负面反馈，特别是自信等方面，所以如果有这样一个环节，允许 Reviewer 提出“这段代码很棒”之类的话语，提供正面鼓励的方法
- Review 的目的要明确，不能只说“此处要如何如何修改”，要加上一些目的性的注释，比如“能增加稳定性、内聚性”、“避免无用的重复代码”等，这个过程能让团队的价值观得以明确
- 除了代码、说明文档以外，还要提供一个测试列表，能列出所有测试过的案例，这样 Reviewer 可以做出更多的测试建议，培养团队的测试观念