今天基本上都是中等题，感觉也要复习复习基础知识 树的子结构 先用一个递归的函数判断当前的树是不是可以构成子结构，如果不能的话，就递归的考虑当前树的左子树和右子树 反转链表 这次尝试用递归写了一下，就是递归的反转当前节点的下一个节点，然后再把当前节点接到尾部即可 一次编辑 因为只有一次机会，所以当两个字符串长度相同的时候，判断最多只有一个字符不同 当长度不同的时候，最多相差1，并且只能有一个地方不匹配 零矩阵 可以用两个数组记录每一行每一列是否出现了0，之后再扫描一遍就行 一个优化是用第一行和第一列去存储这个信息，然…
记录一下刷题过程中遇到的一些值得思考的点，以便之后复习用。 同时回顾一下每天遇到的问题，来重新整理自己的思路。 题目1 求数组中的波谷，但是波谷要满足一定的长度 分别求出来每一个位置上，最长的非递增序列和非递减序列的长度。最后遍历一遍就可以 题目2 对于每一个位置，求出数组中所有数除去当前数的乘积 这个最简单的方法就是求出前缀积和后缀积，然后单独计算就行 一个优化是可以只用一个变量来保存前缀积或后缀积，然后给对应的位置乘上贡献即可 题目3 投n个骰子，问每种点数出现的概率是多少 设dp[i, j]为当前投了i个骰子…
Raft-KV 这里写一下lab4 shardkv的思路吧，感觉如果不好好想一下设计细节的话写代码的时候就很容易乱套 目标就是完成所有的part，所以后面的选做部分也要实现（其实感觉不实现那我们的代码就太玩具了） 每个shard不能干扰其他的shard，比如一个shard正在等待数据，他是不能干扰其他shard完成正常操作的。所以我们分别维护每个shard的状态。每个shard有自己的map 去重表，可以放在shard外面也可以放在shard里面，我这里就选择放在shard里面 有一个定时向shardctrler去…
1 通过算法分解（leader选举，日志复制和安全）和减少状态机的状态来提升Raft的可理解性 Raft独特的特性 强leader： 日志只从leader发送给其他的服务器 leader选举： 使用随机计时器来选举领导人，在解决冲突的时候更加简单 成员关系调整： 使用共同一致(Joint Consensus)的方法来处理集群成员变化的问题，处于调整过程中的两种不同配置的集群中大多数会有重叠，让我们可以在集群变化的时候保证可用性 2 Replicated state machine 在一组服务器上的状态机具有相同状态…
通过functional model和用户指定的map和reduce操作，我们可以很容易的将这些计算并行化。 通过re-execution作为主要的fault tolerance的手段 2 programming model map接受input pair，并生成一组中间键值对。MapReduce Library会把相同key的键值对的所有value组合在一起，并把他们传给reduce reduce接受一个key以及对应的一组value，他将这一组值合并到一起，并返回给用户 一个计算每个document的单词数的例…
How to Read a Paper Just a note for convenience. First pass, get a bird's eye view of the paper Carefully read the title, abstract, and introduction Read the section and sub-section headings, but ignore everything else Read the conclusions Glance over the refe…
多核架构下的中断处理 来一句题外话，本以为我目前的体系结构相关的知识已经足够充分了，但没想到还是不够细节。在理解xv6的过程中，通过教授的一些assertion，我才找到了自己对于中断理解的一些错误，这里特此记录下来。 问题的起因是这样的，在xv6中，中断处理程序一般都需要用lock来防止race condition，所以我就理解成了lock是用来防止多核同时执行一个中断处理程序时，在操作共享数据结构的时候导致的race 但是xv6的net lab中，教授的solution在中断处理程序中没有用lock。同时在课上…
Daily Rust 有关所有权和生命周期的一些问题 首先看一段代码 use std::rc::Rc; #[derive(Debug)] struct Node { id: usize, downstream: Option<Rc<Node>>, } impl Node { pub fn new(id: usize) -> Self { Self { id, downstream: None, } } pub fn update_downstream(&mut self, do…