Halo

A magic place for coding

0%

Problem

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Read more »

Problem

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Read more »

Introduction

  Golang 给开发者提供了一个很成熟的单元测试框架,我们可以直接使用 go test 来执行测试。但是在单元测试中还有需要细节要考虑的,比如哪些文件会运行?测试的范围是什么?这些测试是串行运行还是并行运行等,这些都是我们实际应用时要考虑的问题。


测试范围及文件类型

   我们在运行 go test 命令后,哪些测试文件会被执行,他的范围又是什么?

   首先在某个文件夹下执行了 go test 命令后,这个命令会在 ** 当前的 package** 中寻找符合 *_test.go 的文件,并在这些文件中找到 TestXxx (*testing.T){}BenchmarkXxx (b *testing.B) {}ExampleXxx () {} 这些函数执行测试用例。

   如果想要执行当前 package 下所有的测试用例,可以使用命令 go test ./...,这样就会搜索当前目录及子目录下所有符合要求的测试文件。

串行还是并行

   在测试过程中测试用例的执行串行还是并行很重要吗?当然,这直接影响着测试的结果。试想一下如果测试的时候需要连接到测试的本地数据库,A 用例需要创建一条记录,而 B 用例则需要删除一条记录,如果是并行的话就会有意想不到的效果。这会导致每次测试的结果可能都不同,无法有效地测试代码的正确性。

   默认情况下,在不同的 package 之间的测试是并行的,在 package 内部是串行的。但是如果在 package 内部需要串行执行的话,就需要显式执行 t.Parallel () 或者在运行命令是带上参数 go test -parallel 1 -p 1。第一个参数 -parallel 设定的是并行测试函数的数目,对应的是 package 内部的测试,默认值是 GOMAXPROCS;第二个参数 -p 设定的是并行测试的 test binary 数目,对应的是 package 之间的测试,默认值是 CPU 的核数。


小结

   这里简单分享一些有关 Go 单元测试的小知识,后续遇到了相关的问题会继续在这里分享。


Reference

  1. [Golang 测试](

Introduction

   微服务兴起后,最近有一个词非常热,叫 Service Mesh。很多大厂都极力在推广,这个东西到底是什么呢?在这篇博客我将和大家分享一下有关 Service Mesh 的知识。


What is Service Mesh

   什么是 Service Mesh?中文叫服务网格,它是处理服务见通信的基础设施层。它负责构成现代云原生应用程序的复杂服务拓扑来可靠地交付请求。在实践中,Service Mesh 通常以轻量级网络代理阵列的形式实现,这些代理与应用程序代码部署在一起,对应用程序来说不需要感知到代理的存在。


Why Service Mesh

   在了解 Service Mesh 的工作原理前,首先要知道它诞生的原因,它是解决了软件工程实践中的什么问题。在微服务架构流行并普及后,许多业务都遇到了同一个问题:单个微服务的复杂度大幅度降低,但是系统的整体复杂度并没有下降,反而增加了服务之间连接、管理、监控的复杂度。微服务之间都通过 RPC 的方式获取数据,每个微服务除了包含本身的业务逻辑外,还需要处理 RPC 调用的通讯相关问题,包括限流、权限等。这使得开发者无法把精力都集中到业务逻辑的开发中,当业务场景变得复杂后,这对开发者来说是一个更加大的挑战。

   此时,一种通用的框架应运而生,它的基本思路是,把每个微服务中的通讯部分抽流出来统一交给框架处理,而开发者只需要专注于业务开。这样做的好处是,一是开发者可以专注在业务上,而不需要开发过程中过多地关注微服务之间的通讯问题;二是以通用框架的方式去管理微服务可以更加方便运维,包括流量控制、权限控制等。

   这里我用一个简单的例子去说明 Service Mesh 的作用。在 Service Mesh 之前,如果我要开发一个微服务 A,我需要考虑它的业务逻辑,同时,它对外暴露的接口我也需要做频控、权限控制;如果我再开发一个微服务 B,我需要做同样的事情。这里比较理想的做法可能是把频控、权限控制相关的代码都封装成一个通用库,每个微服务都去使用。但其实这种方法也有缺陷,当需要升级时,几乎每个微服务都需要升级一遍。更大的问题是,如果我想禁止掉 A 对 B 服务调用某个接口,会很不方便,甚至需要改动的代码来完成。

   当有了 Service Mesh 后,这一切变得不同。首先无论是开发 A 还是 B 服务,我不需要关系通讯相关的问题,我只需要在 Service Mesh 提供的平台上配置。同时,当我需要禁止掉某个接口时,直接在运维平台上操作即可,而不需要涉及到代码的改动,这个生效时间是非常短的。


Detail of Service Mesh

   这一部分来看看 Service Mesh 的一些细节及原理。首先来看一张概要图:

Service Mesh Architecture

   上图中,绿色部分指的是微服务本身,承载着业务逻辑;蓝色部分指的是随着服务部署的服务网格,是作为 sidecar 运行在同一个容器中;蓝色的线条表示微服务之间的通讯。整个图片看上去蓝色的方块和线条编织起了一个通讯的网络框架,这就是服务网格的意思,所有的服务都在这个网格之上。

   所以服务网格也可以理解为是若干个 sidecar 服务构成的网络,其中现在业界有很多著名的框架,如 Istio 等。我们就来看看他们具体是怎么工作的:

  1. 首先 sidecar 会把服务请求路由到一个目标地址,也就是需要把这个请求打到哪个服务上。sidecar 会根据请求中的参数判断发往哪个环境(生产环境、预发布环境、测试环境等),是走本地路由还是走公有云环境,这些都是通过读取 sidecar 的配置去实现的;
  2. 当找到目的服务的地址后,就把请求流量发送到相应服务发现端点,在 k8s 中是 service,然后 service 再转发到后端服务实例;
  3. sidecar 会根据最近一段时间内请求的延时,选取出响应最快的实例;
  4. 然后把这个请求发送到这个实例,记录响应的类型、延时及一些信息;
  5. 如果该实例在一定时间内没有响应或者超时,sidecar 会把这个请求转发到其他的实例上重试;
  6. 如果 sidecar 检测到某个实例持续返回 error,或者延时特别高,就会把这个实例从负载均衡池中移除,再周期性重试,这样就能保证调度的请求都能路由到一些健康的实例中;
  7. sidecar 以 metric 和分布式追踪的形式捕获级记录上述的各种行为及参数,并把这些信息发送到集中的 metric 系统。

Summary

   简单来说 Service Mesh 为微服务提供了一个监控的框架,能够让业务开发者专注在业务逻辑的开发,而不需要考虑微服务之间的通讯问题。同时也通过框架的形式,提供高可用的通讯框架,以及汇总更多的监控信息用于维护。总的来说 Service Mesh 会是未来的趋势,许多大厂现在也在极力推 Service Mesh。


Reference

  1. 什么是 Service Mesh
  2. 深度剖析 Service Mesh 服务网格新生代 Istio

Problem

Given a list paths of directory info, including the directory path, and all the files with contents in this directory, return all the duplicate files in the file system in terms of their paths. You may return the answer in any order.

A group of duplicate files consists of at least two files that have the same content.

A single directory info string in the input list has the following format:

  • "root/d1/d2/.../dm f1.txt (f1_content) f2.txt (f2_content) ... fn.txt (fn_content)"

It means there are n files (f1.txt, f2.txt ... fn.txt) with content (f1_content, f2_content ... fn_content) respectively in the directory “root/d1/d2/.../dm". Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.

The output is a list of groups of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:

  • "directory_path/file_name.txt"
Read more »

Problem

Given a list of words, each word consists of English lowercase letters.

Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

Read more »

Problem

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Read more »