tags: LeetCode https://leetcode.com/problems/validate-binary-search-tree/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { if (root == nullptr || (root->left == nullptr && root->right == nullptr)) { return true; } if (root->left != nullptr && root->right != nullptr) { if (root->left->val >= root->val || root->right->val <= root->val) { return false; } return isValidBST(root->left) && isValidBST(root->right); } if (root->left != nullptr) { if (root->left->val >= root->val) { return false; } return isValidBST(root->left); } if (root->right != nullptr) { if (root->right->val <= root->val) { return false; } return isValidBST(root->right) ; } return true; } }; 无法处理子树元素大于上一层的问题。中序遍历排序： ...

tags: LeetCode,backtracking https://leetcode.com/problems/path-sum-ii/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int targetSum) { vector<vector<int>> r; if (root == nullptr) { return r; } if (root->left != nullptr) { auto left = pathSumSide(root-> left, root->val, targetSum); if (left.size() > 0) { left.insert(left.begin(), root->val); r.push_back(left); } } if (root->right != nullptr) { auto right = pathSumSide(root->right, root->val, targetSum); if (right.size() > 0) { right.insert(right.begin(), root->val); r.push_back(right); } } return r; } vector<int> pathSumSide(TreeNode* node, int sum, int targetSum) { vector<int> r; sum += node->val; if (node->left == nullptr && node->right == nullptr) { if (sum == targetSum) { r.push_back(node->val); return r; } } if (node->left != nullptr) { auto ret = pathSumSide(node->left, sum, targetSum); if (ret.size() > 0) { ret.insert(ret.begin(), node->val); return ret; } } if (node->right != nullptr) { auto ret = pathSumSide(node->right, sum, targetSum); if (ret.size() > 0) { ret.insert(ret.begin(), node->val); return ret; } } return r; } }; 失败的错误用例: ...

tags: LeetCode https://leetcode.com/problems/path-sum/ 递归版 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root == nullptr) { return false; } return pathSum(root, 0, targetSum); } bool pathSum(TreeNode* node, int sum, int targetSum) { sum += node->val; if (node->left == nullptr && node->right == nullptr) { if (sum == targetSum) { return true; } } if (node->left != nullptr) { if (pathSum(node->left, sum, targetSum)) { return true; } } if (node->right != nullptr) { if (pathSum(node->right, sum, targetSum)) { return true; } } return false; } }; 测试用例 ...

tags: LeetCode 79. Word Search class Solution { public: bool exist(vector<vector<char>>& board, string word) { backtracking(board, word, 0, 0); return res; } private: string track; bool res = false; enum Direction { right, down, up, left, }; /** * @param dir: 0: right, 1: down, 2: up, 3: left */ void backtracking(vector<vector<char>>& board, string word, int row, int col) { if (track == word || res) { res = true; return; } for (int i = row; i < board.size(); i++) { for (int j = col; j < board[i].size(); j++) { auto directions = get_next_directions(board, i, j); if (directions.size() == 0) { return; } for (auto d: directions) { int r, c; track.push_back(board[i][j]); std::tie(r, c) = next_char_pos(board, row, col, d); if (word.find(track) == 0) { backtracking(board, word, r, c); } track.pop_back(); } } } } vector<Direction> get_next_directions(vector<vector<char>>& board, int row, int col) { vector<Direction> r; if (col < board[row].size() - 1) { r.push_back(right); } if (row < board.size() - 1) { r.push_back(down); } if (row > 0) { r.push_back(up); } if (col > 0) { r.push_back(left); } return r; } tuple<int, int> next_char_pos(vector<vector<char>>& board, int row, int col, Direction dir) { switch(dir) { case right: col++; break; case left: col--; break; case up: row--; break; case down: row++; break; } tuple<int, int>r(row, col); return r; } }; 失败的用例： ...

《领域驱动设计》读书笔记

tags: 计划读的书,HTTP,High Performance,Network 在线： https://hpbn.co/ source: Grigorik, Ilya. High-Performance Browser Networking. Beijing ; Sebastopol, CA: O’Reilly, 2013. “Good developers know how things work. Great developers know why things work.”

预写日志（write-ahead log，WAL），也称为重做日志。 一个仅支持追加修改的文件，每个 B-tree 的修改必须先更新 WAL 然后再修改数本身的页。 当数据库在崩溃后恢复时，该日志用于将 B-tree 恢复到最近一致的状态。

AMQP/JMS 风格的消息代理 将单个消息分配给消费者，消费者在成功处理后确认每条消息。消息被确认后从代理中删除。 适合作为一种异步 RPC。 RabbitMQ ActiveMQ HornetQ Qpid TIBCO Enterprise MEssage Service IBM MQ Azure Service Bus Google Cloud Pub/Sub 多个消费者 负载均衡式 每一条消息都只被传递给其中一个消费者。 扇出式 每条消息都被传递给所有消费者。 确认和重新传递 为了确保消息不会丢失，消息代理使用确认：客户端必须在处理完消息后显式的告诉代理，以便代理可以将其从队列中移除。 如果客户端的连接关闭或超时，而代理没有收到确认，则认为消息未处理，因此它将消息重新传递给另一个消费者。 消息顺序性 即使消息代理试图保留消息顺序（标准要求），负载均衡与重新传递的组合也不可避免地导致消息被重新排序。 基于日志的消息代理 代理将分区中的所有消息分配给相同的消费者节点，并始终以相同的顺序发送消息。 通过分区机制来实现并行（写在多个磁盘上突破磁盘带宽），消费者通过检查他们处理的最后一条消息的偏移量来跟踪进度。 代理将消息保存在磁盘上，因此如果有必要，可以回退并重新读取旧消息。 代表性的有： Kafka Amazon Kinesis Streams Twitter DistributedLog 基于日志的消息存储 参照 LSM-Tree 和 B-tree 的 WAL，可以使用相同的结构来实现消息代理： 生产者通过将消息追加到日志的末尾来发送消息，消费者通过依次读取日志来接收消息。 如果消费者读到日志的末尾，它就开始等待新消息被追加的通知。 通过对日志进行分区突破单个磁盘所能体能的带宽吞吐上线。 代理为每个消息分区分配了一个单调递增的序列号或偏移量，保证了分区内的消息完全有序。 消费者偏移量：记录哪些消息已经被处理，减少 ACK 开销 磁盘空间：分段，定期删除 消费者跟不上生产者：增加 LAG 报警 重新处理消息：重置偏移量

tags: TCP,High Performance Browser Networking 原文链接：https://hpbn.co/building-blocks-of-tcp/。 Overview The 4th version of RFC 675, and final two seperate RFCs: RFC 791 - Internet Protocol(IPv4) RFC 793 - Transmission Control Protocol TCP provides: Effective abstraction. A reliable network running over unreliable channel. Hiding most the complexity of network communication: retransmission of lost data, in-order delivery, congestion control and avoidance, data integrity, and more. Three-Way Handhsake Sequence numbers are important for keep in-order delivery, and they are picked randomly from both sides for security reasons. ...

tags: Network

阻止生产者发送更多的消息。使用背压的场景： Unix 管道 TCP

发送事件流 消息系统 生产者速度比消费者快：丢弃消息、将消息缓存在队列、激活背压。 节点崩溃或者暂时历险，是否会有消息丢失？ 生产者与消息系统之间的直接消息传递 UDP 组播：广泛应用于金融股票 无代理消息库：ZerroMQ 和 nanomsg StatsD 和 Brubeck 使用 UDP 传递消息 HTTP、RPC 接口 消息代理 参见：AMQP/JMS 风格的消息代理。 也称消息队列。 消息对比与数据库对比 多个消费者 确认和重传机制 分区日志 参见： 基于日志的消息代理。 数据库与流 保持系统同步 变更数据捕获 变更数据捕获（Change Data Capture，CDC）记录了写入数据库的所有更改，并以可复制到其他系统的形式来提取数据。 如果在写入时立即将更改作为一种流来发布，那么 CDC 就更有趣来。 实现变更数据捕获 解析复制日志，并将解析的内容发送到事件流中进行 replay。 初始快照 replay 日志占用空间过大，需要进行截断，截断之前的进行初始快照保存。 日志压缩 参考哈希索引。 对变更流的 API 支持 数据库开始支持将变更流作为标准接口。 事件溯源 一种在领域驱动设计社区中开发的技术，与 CDC 最大的区别在于事件溯源在不同抽象层次上应用了将所有对应用程序状态的更改保存为更改事件日志： CDC 中：应用程序以数据可变方式来操纵数据库，从数据库中提取较低级的变更日志，从而确保从数据库提取写入顺序与实际写入顺序相匹配。写入数据库的程序不需要知道 CDC 正在发生。 事件溯源中：应用程序的写入逻辑是基于写入事件日志的不可变事件构建的。事件存储仅支持追加，不鼓励甚至禁止更新或删除操作。事件旨在反映在应用程序级别所发生的事情，而不是低级别的状态改变。 专门的数据库 Event Store 来支持使用事件溯源的应用程序。 从事件中导出当前状态：真正对用户有意义 命令和事件 命令经过校验后转化为事件。 状态，流与不可变性 流处理 事件中的数据写入数据库、缓存、搜索索引或类似的存储系统，提供给客户端查询。 通过某种方式将事件推送给用户，如电子邮件、短信等。 处理一个或多个输入流产生过一个或多个输出流。 流处理适用场景 复杂事件处理 复杂事件处理（Complex Event Processing，CEP）尤其适用需要搜索特定的事件模式。 实现：Esper、IBM Info Sphere Streams、Apama、TIBCO StreamBase 和 SQLstream。 ...

原文链接：Why MapReduce is making a comeback。

tags: Rust 原文：When Zero Cost Abstractions Aren’t Zero Cost

基于 Hadoop 分布式文件系统使用 SSTables 和 LSM-Tree 实现随机访问的 OLTP 数据库。

MPP 数据库 Gamma 数据库机器 Teradata Tandem NonStop SQL

tags: 分布式,一致性,Clock Synchronization,Multicast source: https://signalsandthreads.com/clock-synchronization/ Electronic Oscillator: Computer itself to Dervie its Notion of Time Computer’s clock are based on a 1 MHz electronic oscillator circuit, that is oscillating at some frequency, and driving an interrupt. So the operating system can use it to derive its notion of time. It helps computer to keep the time correct. But a bad oscillator could be influenced by the heat of CPU, like compiling Linux kernel, etc. A really high-quality oscillator would be really expensive. So most computers come with fairly bad oscillators. ...

tags: Bigdata bucketed map join

tags: Bigdata Hadoop Distributed File System MapReduce MapReduce shuffle 按照 reducer 分区，排序和将数据分区从 mapper 复制到 reducer。（令人困惑的术语，并不完全与洗牌一样，在 MapReduce 中其实没有随机性）。 MapReduce 的分布式执行 Hadoop MapReduce 并行化基于数据分区实现： 输入：通常是 HDFS 中的一个目录。 分区：每个文件或文件块都被视为一个单独的分区。 处理：每个分区由单独的 map 任务来处理。 每个 mapper 都会尽量实现计算靠近数据。 代码复制：JAR 文件。 Reduce 任务的计算也被分隔成块，可以不必与 mapper 任务数量相同，MapReduce 框架使用关键字的哈希值来确保具有相同关键字的键值对都在相同的 reduce 任务中处理。 键值对必须进行排序，排序是分阶段进行的： 每个 map 任务都基于关键字哈希值，按照 reducer 对输出进行分块。 每个分区都被写入 mapper 程序所在的本地磁盘上的已排序文件，参见 SSTables 和 LSM-Tree。 reducer 与每个 mapper 相连接：MapReduce 调度器会在 mapper 写入经过排序的输出文件后，通知 reducer 开始从 mapper 中获取输出文件，框架进行 MapReduce shuffle。 reducer 任务从 mapper 中获取文件并将它们合并在一起，同时保持数据的排序。不同 mapper 使用相同的关键字生成记录，会在合并后的 reducer 输入中位于相邻的位置。 reducer 可以使用任意逻辑来处理这些记录，并且生成任意数量的输出记录。记录被写入分布式文件系统中的文件。 MapReduce 工作流调度器 Oozie Azkaban Luigi Airflow Pinball 对比分布式数据库 MapReduce 中的并行处理和并行 join 算法已经在十多年前所谓的大规模并行处理（MPP）数据库中实现了。 ...

tags: Rust

tags: 分布式

tags: Bigdata,分布式文件系统 与网络连接存储（NAS）和 存储区域网络（SAN）架构相比，HDFS 基于无共享原则，无需定制硬件和特殊网络基础设施（光纤）。 HDFS 创建了一个庞大的文件系统，来充分利用每个守护进程机器上的磁盘资源。 HDFS 包含一个在每台机器上运行的守护进程，并会开放一个网络服务以允许其他节点访问存储在该机器上的文件。 名为 NameNode 的中央服务器会跟踪哪个文件块存储在哪个服务器上。 考虑容错，文件快块复制到多台机器上，或者像 Reed-Solomon 代码中这样的纠删码方案（类似 RAID，但无需特殊硬件）。 提供很好的扩展性，配合商业硬件和开源软件，可以运行在上万台机器，容量达几百 PB。 计算靠近数据 只要有足够的空闲内存和 CPU 资源，MapReduce 调度器会尝试在输入文件的副本的某台机器上运行 mapper 任务。

tags: Emacs M-x life RET 康威生命游戏（Conway’s Game of Life）

tags: 技术 数据库作为一个长期发展的技术，但是在中国相对处于一个起步阶段，相关人才比较少。近年能够看得到的技术： TiDB 分布式关系型数据库 TDengine 面向 IoT 的 OLAP 数据库 相关创业公司： 神策 https://zhuanlan.zhihu.com/p/396433354

MapReduce MapReduce 与分布式文件系统 MapReduce 就像分布在上千台机器上的 Unix 工具。 MapReduce 作业通常不会修改输入，除了输出外没有任何副作用。 MapReduce 作业在分布式文件系统上读写。（Unix 工具 stdin、stdout），如 HDFS（Hadoop Distributed File System)等（GlusterFS、QFS、Amazon S3、Azure Blob 和 OpenStack Swift）。 MapReduce 作业执行 MapReduce 是一个编程框架，可以使用它编写代码处理 HDFS 等分布式文件系统中的大型数据集。 要创建 MapReduce 作业需要实现两个回调函数： mapper 和 reducer （另请参阅 MapReduce 查询）: Mapper: 每个输入记录都会调用一次，从输入记录提取任意数量的关键字和值（可以为空），不保留任何状态，可以独立处理。 Reducer: MapReduce 框架使用 Mapper 生成的键值对，收集同一个关键字的所有值，并使用迭代器调用 reducer 以使用该值的集合。 Reducer 可以生成输出记录。 MapReduce 分布式执行 参见 Hadoop 的 MapReduce 的分布式执行。 MapReduce 工作流 将 MapReduce 作业链接到工作流是非常普遍的，作业的输出作为下一个作业的输入。通过目录名隐式的完成： 第一个作业必须配置将其输出写入 HDFS 中指定目录； 第二个作业必须配置读取相同的目录名作为输入。 目前已经开发了处理依赖管理的 MapReduce 工作流调度器。 Reduce 端的 join 与分组 批处理的背景下讨论 join，主要解决数据集内存在关联的所有事件。 假设 join 两张表：用户和活动事件。 ...

tags: LeetCode

tags: LeetCode https://leetcode.com/problems/valid-sudoku/ <- high -- low -> +------------------- wow(row(i):0,col(j):0) 0 -> [ 0010, 0010 ] | 1 -> [ 0000, 0000 ] | 2 -> [ 0000, 0000 ] | | +--------------- wow(row(i):0,col(j):1) 0 -> [ 0010 | 1 = 0011, 0010 ] | | 1 -> [ 0000, 0000 | 1 = 0001 ] | | 2 -> [ 0000, 0000 ] | | | | +----------- wow(row(i):0,col(j):2) 0 -> [ 0011 | 3 = 0100, 0010 ] | | | 1 -> [ 0000, 0001 ] | | | 2 -> [ 0000, 0000 | 3 = 0100 ] +---+---+---+ | 2 | 1 | 3 | +---+---+---+ ----| 3 | 2 | 1 | | +---+---+---+ | | 1 | 3 | 2 | | +---+---+---+ |- wow(row(i):1,col(j):0) 0 -> [0010 | 3 = 0110, 0010] +---------------------+ 1 -> [0000, 0001 | 3 = 0101] 2 -> [0000, 0100] class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { vector<int> wow(9,0); int mux1; int mux2; int mux3; int box_index; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(board[i][j] == '.'){ continue; } mux1 = 0x01 << (board[i][j] - '1'); mux2 = 0x01 << 9 << (board[i][j] - '1'); mux3 = 0x01 << 9 << 9 << (board[i][j] - '1'); box_index = (i/3) * 3 + j/3; if((wow[i]&mux1) != mux1 && (wow[j]&mux2) != mux2 && (wow[box_index]&mux3) != mux3){ wow[i] = wow[i]|mux1; wow[j] = wow[j]|mux2; wow[box_index] = wow[box_index]|mux3; } else{ return false; } } } return true; } };

tags: 分布式共识,技术概念

tags: LeetCode source: https://leetcode.com/problems/combination-sum-ii/ LeetCode: 39. Combination Sum 的进阶。元素不在唯一且每一个元素只能出现一次。对结果进行排序然后通过 set 对结果进行去重： class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtracking(candidates, 0, 0, target); vector<vector<int>> r; for (auto t : res) { r.push_back(t); } return r; } private: set<vector<int>> res; vector<int> track; map<int, bool> visited; void backtracking(vector<int>& condidates, int start, int n, int target) { if (n == target) { res.insert(track); return; } if (n > target) { return; } int c = 0; int sz = condidates.size(); for (int i = start; i < sz; i++) { c = condidates[i]; track.push_back(c); backtracking(condidates, i + 1, n + c, target); track.pop_back(); } } }; 以下测试用例无法通过： ...

tags: LeetCode source: https://leetcode.com/problems/combination-sum/ class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { backtracking(candidates, 0, target); return res; } private: vector<vector<int>> res; vector<int> track; void backtracking(vector<int> & candidates, int n, int target) { if (n == target) { res.push_back(track); return; } // this is new if (n > target) { return; } for (auto c : candidates) { track.push_back(c); backtracking(candidates, n + c, target); track.pop_back(); } } }; 问题：会有不同顺序但是元素相同的数组，如何快速高效的进行过滤？ ...

tags: LeetCode,backtracking source: https://leetcode.com/problems/n-queens-ii/ 参见：LeetCode: 51. N-Queens

tags: Algorithm,Brute Force Approach

tags: 技术概念 创业公司有：积梦智能。

tags: 技术概念

tags: 技术概念

tags: 技术 目前互联网领域里比较热门的概念和方向。

tags: 技术概念

tags: LeetCode,backtracking source: https://leetcode.com/problems/n-queens/ 一旦一个 Queue 被放置，那么横轴、纵轴、对角线都不再允许放置。我们按行进行遍历，所以我们需要跟踪以下位置是否已经放置 Queue： 纵轴（Column）：cols 主对角线（Positive Diagonal）：posDiag 次对角线（Negative Diagonal）：negDiag 纵轴很好记录，但是对角线比较困难，我们先来看一下对角线的特征，假设横轴为 r 纵轴为 c ， r - c 在正对角线是一致的： 斜对角线 r + c 是一致的: class Solution { public: vector<vector<string>> solveNQueens(int n) { for (int r = 0; r < n; r++) { string col = string(n, '.'); track.push_back(col); } backtracking(0, n); return res; } private: set<int> cols; // c set<int> posDiag; // r - c set<int> negDiag; // r + c vector<vector<string>> res; vector<string> track; void backtracking(int r, int n) { if (r == n) { res.push_back(track); return; } for (int c = 0; c < n; c++) { if (cols.find(c) != cols.end() || posDiag.find(r - c) != posDiag.end() || negDiag.find(r + c) != negDiag.end()) { continue; } cols.insert(c); posDiag.insert(r - c); negDiag.insert(r + c); track[r][c] = 'Q'; backtracking(r + 1, n); track[r][c] = '.'; cols.erase(c); posDiag.erase(r - c); negDiag.erase(r + c); } } }; 结果 ...

tags: 分布式共识,Paxos

tags: 分布式共识

tags: 分布式共识,分布式

tags: 共识算法，分布式共识

tags: Incomplete，分布式，共识算法

tags: 分布式,Incomplete