Link to this problem

HackerRank Extra Long Factorials

Intuition

• Implement large number multiplication using a string or an array.

Approach

1. Create an array called largeInteger, which represents a large number.
2. Fill the largeInteger with n.
3. Iterate over numbers from n to 0:
   1. Multiply largeInteger by this number.
   2. Handle the potential carry.
4. Output the content of largeInteger to stdout.

Pseudocode of largeIntMultiply:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

largeIntMultiply(largeInt, n):
	Input largeInt a very large number represent by an array
		n the multiplier
	Output the largeInt multiplied by n
	carry = 0
	for every i from largeInt.size()-1 to 0:
		number = n * largeInt[i] + carry
		largeInt[i] = number % 10
		carry = number / 10
		if i == 0 and carry != 0:
			add a 0 at the beginning of largeInt
			i++
		end if
	end for
	return largeInt

Intuition

• Find the first and last occurrence (say firstOccurrence and lastOccurrence) of an unused character c.
• Count the number of unique characters between firstOccurrence and lastOccurrence (including c itself).

Approach

1. Create an empty set visited.
2. For every character c in s:
   1. If c is a member of visited, jump to the next character.
   2. Otherwise, find the firstOccurrence and lastOccurrence of c in s.
   3. Create an empty set unique.
   4. Add every character between firstOccurrence and lastOccurrence to unique.
   5. Add the size of unique to answer.

Pseudocode of countPalindromicSubsequence:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

countPalindromicSubsequence(s):
	Input string s
	Output number of unique palindromic subsequences in s of length 3
	
	visited = empty set
	ans = 0
	for every character c in s:
		if c in set:
			continue
		end if
		add c to visited
		firstOccurrence = -1
		lastOccurrence = -1
		for every i from 0 to s.length():
			if firstOccurrence == -1:
				firstOccurrence = i	// Ensure that firstOccurrence only updates once
			end if
			lastOccurrence = i
		end for
		unique = empty set
		for every i from firstOccurrence + 1 to lastOccurrence:
			add s[i] to unique
		end for
		ans += unique.size()
	end for
	return ans

Complexity

• Time complexity: $O(n)$.
  • At most $\Sigma = 26$ iterations of outer loop.
  • In each iteration:
    • Find firstOccurrence and lastOccurence is $O(n)$.
    • Create unique set is $O(n)$.
  • Overall complexity is $O(\Sigma n) = O(n)$.
• Space complexity: $O(\Sigma)$.
  • s only contains lowercase English letters, so $\Sigma = 26$.
  • As a consequence, the maximum size of visited and unique is 26.

Intuition

• Set the first element arr[0] to 1.
• Limit the difference of two adjacent elements to 1 or less than 1, which means arr[i+1] is the same as arr[i] or equal to arr[i] + 1.
• Return the maximum possible value in arr.

Approach

1. Set arr[0] to 1 (that’s the rule of this challenge).

2. Set max to 1, which represents the maximum possible value in arr is 1.

3. Sort arr in ascending order.

4. Iterate over arr from the second element arr[1] (because arr[0] has already been set to 1):

   1. Set arr[i] to max if it’s the same as or higher than max, then increase max by 1.
   2. Do nothing if arr[i] is smaller than max (which couldn’t happen because arr has already been sorted in ascending order).

5. Return max.

Pseudocode of maximumElementAfterDecrementingAndRearranging:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

maximumElementAfterDecrementingAndRearranging(arr):
	Input arr an array of integers
	Output maximum possible element in arr after decrementing and rearranging
	
	sort arr in ascending order
	max = 0
	arr[0] = 1
	for every i from 0 to arr.size():
		if arr[i] >= max + 1:
			arr[i] = max
			max++
		end if
	end for
	return max

Complexity

• Time complexity: $O(nlogn)$.

  • Sorting arr in ascending order is $O(nlogn)$.
  • Iterate over arr to update arr and max is $O(n)$.
  • Overall complexity is $O(nlogn)$.
  • $n$ is the total size of arr.

• Space complexity: $O(1)$.

Background of the Problems

I’ve enrolled in a course whose main content is AVR assembly language this semester. In the lab of this course, we have to use an IDE called Microchip Studio (aka. Atmel Studio) to develop, debug, and test AVR assembler programs. Since I mainly use macOS and Microchip Studio supports only Windows, I need to use this IDE with a Windows 11 virtual machine.

I used Parallels Desktop, the virtualization software that I mainly used, and its official wizard (Get Windows 11 from Microsoft) to create a Windows 11 VM, then successfully installed Microchip Studio in it. However, I encountered some weird problems when I started using Microchip Studio.

What the Problems are

A Warning was Generated on Startup

A warning is generated every time Microchip Studio starts.

The Layout is Weird

问题的背景

这学期选了一门以讲解 AVR 汇编为主的课，在实验课中需要用到 Microchip Studio（也称 Atmel Studio）编写、调试 AVR 汇编程序。由于我平常使用的操作系统是 macOS，但这个软件只支持 Windows，所以我需要通过虚拟机使用这个软件。

我使用我最常用的虚拟机软件 Parallels Desktop 官方提供的创建 Windows 11 虚拟机的向导程序（Get Windows 11 from Microsoft）创建了一个 Windows 11 虚拟机，并成功地在虚拟机中安装了 Microchip Studio。但是，在完成安装并开始使用 Microchip Studio 时，我遇到了一些奇怪的问题。

问题的表现

启动时弹出警告框

每次启动 Microchip Studio 都会弹出如下图所示的警告框：

界面布局怪异

I chose not to follow Cloud Native for several reasons, and I found that Cloud Native is not as powerful as I used to believe. It’s not a “silver bullet”, and I don’t need to stick to it.

How did I know Cloud Native

I was passionate about Spring Cloud Alibaba-based microservices before April 2020 because it’s really easy to use it to develop faultless microservices. I developed a Spring Cloud Alibaba-based project to participate in a software development competition. However, after I transferred the microservices into Docker containers and used Kubernetes (K8S) to manage them, I found Kubernetes and Spring Cloud could not work together: some functionalities (like Nacos and ApiServer, Spring Cloud Gateway and Ingress) overlapped and caused incompatibility between them. There were so many conflicts that the entire project couldn’t work properly.

That failure reminded me that I didn’t know enough about Spring Cloud and Kubernetes. After searching for a lot of information, I realized that Spring Cloud is a framework for building “traditional” microservices, which are not so suitable for Kubernetes unless using Spring Cloud Kubernetes. I also learned about a new technology called “Service Mesh” and a new theory related to Service Mesh called “Cloud Native” when collecting information related to K8S.

It was a little hard for me to understand service mesh and Cloud Native then, but after I read some articles and books related to them, I finally knew what they were and what their advantages were. Suddenly, I felt that “traditional” microservices were outdated because they depended a lot on SDKs. Many basic functionalities, like service discovery and resource management, are provided by SDKs, which are coupled with service codes. What’s worse, the service codes need to be changed every time the SDKs make destructive updates. Service mesh provides a better solution: refactor those basic functionalities into a separate process or container that runs with (in the same Pod) the microservice container. Service mesh amazed me and solved my problems with microservices completely.

Cloud Native is my favorite theory ever

Service mesh piqued my interest in Cloud Native. I found that it’s an attractive theory that everyone holds their own opinion on it. Though it’s so abstract that I still can’t fully understand it, I kept studying and following Cloud Native from 2020 to 2022. I decided I needed to get a job related to Cloud Native (such as Cloud Native Engineer, Site Reliability Engineer, and Basic Software Developer). So I chose Golang as the programming language I mainly used and studied a lot about Docker, Kubernetes, and Istio. I never missed every conference about Cloud Native and service mesh that I was able to attend then. I don’t think it’s a successful choice, but in addition to learning how to use Cloud Native tools and their inner workings, I also learned a lot about software design and software architecture.

Looking back to that time now, I can confidently say that “Cloud Native is my favorite theory ever”.

出于种种原因，我选择不再关注云原生。在那之后，我发现云原生并没有像我以前坚信的一样强大，它不是银弹，我也无需执着于它。

第一次认识云原生

在 2022 年 4 月之前，我曾经非常喜欢基于 Spring Cloud Alibaba 的微服务——使用它可以很容易地开发出完善的微服务。我开发了一套基于 Spring Cloud Alibaba 的微服务用于参加一个软件开发比赛，但在我将这些微服务制作成 Docker 容器并使用 Kubernetes (K8S) 去管理之后，我发现 K8S 和 Spring Cloud 并不能很好地配合：它们中的很多功能（例如 Spring Cloud Gateway 与 Ingress）都是重复的，造成了两者互不兼容。两者之间的冲突多到整个项目都无法正常运行。

这次犯错让我意识到我对 Spring Cloud Alibaba 和 Kubernetes 的了解都远远不够。在查找了足够多的信息后，我意识到 Spring Cloud 是用于构建传统微服务的框架，并不适合与 K8S 一起使用——除非你使用 Spring Cloud Kubernetes。此外，我也在收集资料的过程中了解到了一种名叫“Service Mesh”的新技术和一种名叫“云原生”的新理论。

对于当时的我来说，云原生和 Service Mesh 并不是容易理解的知识。但当我读了许多与此相关的文章和书籍之后，我最终理解了它们是什么，以及它们的优势在哪里。我立刻感到传统微服务是相当落后的东西——传统微服务过于依赖 SDK，服务代码与 SDK 紧密耦合，微服务架构中的许多通用基本功能，例如服务发现、资源调度等，都是由 SDK 提供的。更糟糕的是，当 SDK 发生破坏性更新时，服务代码也得跟着更新。Service Mesh 提供了一种更棒的解决方案：将这些基本功能做成一个进程或容器，并使其与微服务容器共同运行（也就是运行在同一个 Pod 里）。Service Mesh 令我震惊的同时，还解决了我关于微服务的所有问题。

云原生，我曾经最爱的理论

Service Mesh 引起了我对于云原生的兴趣。我发现云原生是一种引人注目的理论，并且一千个人眼中有一千种云原生。即使云原生如此抽象，以至于我至今都无法完全理解它，但我仍然在 2020 到 2022 年间持续学习它。我决定要从事与云原生相关的工作（例如云原生工程师、SRE、基础软件工程师等），所以我选择了 Go 语言作为我主要使用的编程语言，并且深入学习了 Docker、K8S 和 Istio，还没有错过任何一场我可以参加的有关于云原生和 Service Mesh 的会议。我并不认为这是一个成功的选择，不过我除了学习使用这些云原生工具以及它们的原理之外，还学到了大量软件设计和软件架构的知识。

现在再来回顾这段时光，我可以自信地说“云原生是我曾经最爱的理论”。

1
2
3
4
5
6
7

#include <iostream>
using namespace std;

int main() {
  cout << "Hello world!" << endl;
  return 0;
}

This is the very first program I developed.
Just like me, most programmers’ very first program is to print “Hello world” in the terminal.
Then, it’s the most suitable title for the very first article I write after I’ve started a completely new life.

A destroyed “game account”

Do you have such an experience: you destroy your character or account in a game, so you must create a new character or register a new account and start from zero? I had such an experience, but the thing that I destroyed was not my character or account in a game; it was my life.

In 2022, I’ve chosen Golang as the programming language that I mostly use and Site Reliability Engineer as my job. I didn’t know that that was the worst decision I’ve made in my life. That doesn’t mean Golang is a terrible language or that SRE is a bad job for a programmer. They are just not suitable for a fresh graduate. You probably know that the status of a fresh graduate is really important in China because there’s a special opportunity for fresh graduates to be hired by companies in China regardless of work experience. But SRE is a job that requires a lot of experience, and Golang is a new programming language that also requires 3-5 years of experience in other languages. So, it’s really hard for a programmer who doesn’t have more than 3 years of experience to become a SRE using Golang in China; the chances are really limited.

Fortunately, I finally got a job at a big international company as a SRE with a satisfactory salary. I worked hard, developed a lot of important features, solved many complicated bugs alone, and became an indispensable member of the SRE team. That’s the happiest 8 months of my life: my job became a part of my life, I live in a big city where everything is convenient and enjoyable, and I never need to work overtime. I feel happy every time I remember that time.

The good times didn’t last long. I’ve lost my job because my department and group were abolished due to the company’s poor decision-making. I tried to find a new job as an SRE and asked over 400 companies, but I wasn’t given a single chance to interview because I only have 8 months of experience and I’m not a fresh graduate anymore. I was rejected by every company simply because of my experience, regardless of my strong programming skills and my ability to work as an experienced programmer.

Review my mistakes

1
2
3
4
5
6
7

#include <iostream>
using namespace std;

int main() {
  cout << "Hello world!" << endl;
  return 0;
}

这是我写下的第一个程序。
像我一样，大多数程序员编写的第一个程序都是打印“你好，世界”（Hello world）。
那么，我人生重启之后的第一篇文章，最好的标题非“你好，世界”莫属。

号练废了

你有过号练废了删号重练的经历吗？我有，不过我练废的不是游戏账号，而是我的人生。

在 2022 年，我选择使用 Go 语言并且成为一名 SRE。那时的我并不知道，这是我迄今为止的人生里做出过的最错误的选择——当然，这不是说 Go 语言或者 SRE 这份工作不好，它们只是不适合应届生。我们都知道，因为校招这一不需要任何工作经验的特殊招聘方式的存在，应届生身份在中国是至关重要的。但是，SRE 是一项对经验有着很高要求的工作，Go 语言又是一种需要在其他语言上有 3 - 5 年工作经验的新兴编程语言。因此，在中国找到经验要求低于 3 年的 Go 语言 SRE 工作实在是太难了，岗位简直少得可怜。

幸运的是，我获得了一份外企的 SRE 工作机会，并且薪水和 base 地都令我十分满意。我当时工作十分努力，完成了许多重要功能，独立修复了许多复杂的 bug，并逐渐成为了 SRE 团队中不可或缺的成员之一。那是我人生中最幸福的 8 个月——做着喜欢的工作并以此为生、住在一座便利而又舒适的大城市，并且从不加班。直到现在，每当我想起那段时光，我都感到很高兴。

好景不长，由于公司决策失误，我们的部门和组都被重建，我也因此失业了。我投了四百多份简历，试图重新找到工作，然而所有公司都因为我只有 8 个月的工作经验且不是应届生而拒绝了我，我甚至都没有得到哪怕一个面试机会。我就这样被所有公司拒绝了——即使我有足以胜任工作的技术还能比很多有好几年工作经验的人都工作得更好。

复盘