Arts

题目： Given a binary tree, return the inorder traversal of its nodes\’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? 解题： 树的中序遍历： 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。 a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。 b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。 重复以上1、2直到当前节点为空。 实现： 递归方式： 对左子结点调用递归函数，根节点访问值，右子节点再调用递归函数 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector <int> res; inorder(root, res); return res; } void inorder(TreeNode *root, vector<int> &res){ if (!root) { return; } if (root->left) { inorder(root->left, res); } res.push_back(root->val); if (root->right){ inorder(root->right, res); } } }; 空间复杂度：O(n)， 时间复杂度：O(n)。 使用栈实现 从根节点开始，先将根节点压入栈，然后再将其所有左子结点压入栈，然后取出栈顶节点，保存节点值，再将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右， ...

这篇文章 CFS Scheduler是Linux Kernel文档 1.概述 CFS - “Completely Fair Scheduler”，是新的交互式流程调度算法,由Ingo Molnar实现，并在Linux 2.6.23中合并。它是替换以前的Vanilla Kernel的SCHED_OTHER调度策略对应的调度算法。 SCHED_OTHER是老版本中的调度策略后续成为SCHED_NORMAL Vanilla Kernel是指http://www.kernel.org/的上Linux的发布版本 What is Vanilla kernel Debian wiki vanilla CFS 80%的设计可以用一句话来概括：CFS基本上是模型真实硬件上的“理想，精确的多任务CPU”。 理想的多任务CPU是一种（不存在的 :-) ）具有100％物理性能的CPU 功率和每个任务可以以精确的相等速度并行运行每个任务 1 / nr_running速度。例如：如果有2个任务在运行，那么它就会运行每个物理功率为50％, 即实际上并联。 在真正的硬件上，我们一次只能运行一个任务，所以我们必须这样做 介绍虚拟运行时(vruntime))的概念。任务的虚拟运行时 指定下一个时间片何时开始执行理想 上面描述的多任务CPU。在实践中，任务的虚拟运行时是它的实际运行时间标准化为正在运行的任务总数。 2.部分实现细节 在CFS中，通过每个任务task的虚拟运行时(vruntime)通过 p->se.vruntime（纳秒为单位）值体现。这样，就可以任务可以等到准确时间戳并测量应该得到的预期CPU时间。 [小细节：在理想硬件上，任何时候所有任务都会相同 p-> se.vruntime — 任务将同时执行, 没有任务将从CPU时间等到一样的份额。] CFS的任务选择逻辑基于此p->se.vruntime值，因此非常简单：它总是尝试以最小的p->se.vruntime运行任务值（即至少执行到目前为止的任务）。 CFS总是试图拆分 可运行任务之间的CPU时间接近理想的多任务硬件 可能。 CFS的其余大部分设计都脱离了这个非常简单的概念， 有一些附加的装饰，如nice值,多处理和各种算法变体去识别睡眠者。 3. 红黑树 CFS的设计非常激进：它没有使用旧的数据结构 runqueues，但它使用按时间排序的rbtree来构建未来执行任务的时间轴 ，因此不涉及数组切换（以前的Vanilla Kernel调度器O(1)和RSDL/SD涉及到）。 Linux 2.4调度使用时间片epoch,类似多路复用模式,使用runqueue调度方法与进程个数有关 array switch:O(1)为每个CPU维护了两个数组active与expire数组,随着时钟中断发生，1.调度器判断当前进程类型交互进程或者实时进程，重置其时间片重新插入active数组，不是交互实时进程、时间片使用完毕的放入expired数组, 当所有active为空,active与expired交换 RSDL/SD是对O(1)改进 Linux 调度器发展简述 CFS还维护rq->cfs.min_vruntime值，这是一个单调递增值，用于跟踪runqueue中所有任务中的最小vruntime。使用min_vruntime跟踪系统完成的工作总量; 该值用于尽可能多地将新激活的实体放置在树的左侧。 每一个cpu维护一个min_vruntime,每一个子进程创建时被初始化为这个值，如果schedule_feature 设置了SCHED_DEBIT，vruntime还会再增大一些 从几个问题开始理解CFS调度器 runqueue中运行任务的总数通过rq->cfs.load值计算，该值是在runqueue上排队的任务的权重之和。 ...

题目： You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Example 1: Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Note: ...

题目： Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. Example: Input: {"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1} Explanation: Node 1's value is 1, and it has two neighbors: Node 2 and 4. Node 2's value is 2, and it has two neighbors: Node 1 and 3. Node 3's value is 3, and it has two neighbors: Node 2 and 4. Node 4's value is 4, and it has two neighbors: Node 1 and 3. Note: ...

这篇文章 Timers and time management in the Linux kernel. Part 1. 是出自 linux-insides一书中 Timers and time management 章节 Introduction 内核版本比对5.3-rc 进行了相关调整, 增加相关备注 Linux内核中的定时器和时间管理. Part 1. 介绍 这是另一篇文章，它在linux-insides一书中开启了新的篇章。前面的部分描述了系统调用概念，现在是时候开始新篇章了。正如人们可能从标题中理解的那样，本章将专门讨论Linux内核中的“定时器”和“时间管理”。当前章节的主题选择并非偶然。定时器（通常是时间管理）非常重要，并且在Linux内核中广泛使用。 Linux内核使用计时器执行各种任务，例如TCP实现中的不同超时，内核知道当前时间，调度异步函数，下一个事件中断调度和还有更多。 因此，我们将开始学习本部分中不同时间管理相关内容的实现。我们将看到不同类型的计时器以及不同的Linux内核子系统如何使用它们。与往常一样，我们将从Linux内核的最早部分开始，并完成Linux内核的初始化过程。我们已经在特殊的章节-Kernel initialization process中完成了它，它描述了Linux内核的初始化过程，但是你可能还记得我们错过了那里有些东西。其中一个是定时器的初始化。 我们开始吧。 初始化非标准PC硬件时钟 Linux内核解压缩后（更多关于此内容，您可以在内核解压缩部分中阅读）非特定代码开始在init/main.c源代码文件中工作。初始化lock validator后，初始化cgroups并设置canary值，我们可以看到setup_arch函数的调用。 你可能还记得，这个函数（定义在arch/x86/kernel/setup.c)准备/初始化特定于体系结构的东西（例如它为bss部分保留一个位置，为initrd保留一个位置，解析内核命令行以及许多其他事情）。除此之外，我们还可以找到一些时间管理相关的功能。 首先是： x86_init.timers.wallclock_init(); 我们在描述Linux内核初始化的章节中已经看到了x86_init结构。此结构包含指向不同平台的默认设置功能的指针，如 Intel MID，Intel CE4100 等x86_init结构定义在arch/x86/kernel/x86_init.c，正如您所看到的，它默认确定标准PC硬件。 我们可以看到，x86_init结构具有x86_init_ops类型，它为平台特定的设置提供了一组函数，如保留标准资源，平台特定的内存设置，中断处理程序的初始化等。这种结构如下所示： struct x86_init_ops { struct x86_init_resources resources; struct x86_init_mpparse mpparse; struct x86_init_irqs irqs; struct x86_init_oem oem; struct x86_init_paging paging; struct x86_init_timers timers; struct x86_init_iommu iommu; struct x86_init_pci pci; struct x86_hyper_init hyper; struct x86_init_acpi acpi; }; 备注： 新增以下两个成员 ...

 sysctl命令可以_实时_（runtime）查看和修改linux 内核参数。这个命令可以在大多数发行版本找到， 另外内核参数，也可以通过procfs 文件系统，在 /proc/sys/kernel下 进行查看和修改。 查看指定参数 # sysctl kernel.sched_child_runs_firstkernel.sched_child_runs_first = 0 查看所有参数 # sysctl -a |moresysctl: reading key "net.ipv6.conf.all.stable_secret"sysctl: reading key "net.ipv6.conf.default.stable_secret"abi.vsyscall32 = 1crypto.fips_enabled = 0debug.exception-trace = 1debug.kprobes-optimization = 1 修改指定参数 # sysctl -w kernel.sched_child_runs_first=1 kernel.sched_child_runs_first = 1 注意等号前后不能有空格 修改含多个值的参数 # sysctl -w net.ipv4.ip_local_port_range="1025 60999"net.ipv4.ip_local_port_range = 1025 60999 通过修改procfs 文件系统实现 修改指定参数 # echo 1 > /proc/sys/kernel/sched_child_runs_first# sysctl kernel.sched_child_runs_firstkernel.sched_child_runs_first = 1 修改含多个值的参数 # echo "32768 60999" > /proc/sys/net/ipv4/ip_local_port_range# sysctl net.ipv4.ip_local_port_rangenet.ipv4.ip_local_port_range = 32768 60999 持久化设置 以上修改是临时性的，机器重启后失效，如果要持久化保存，可修改/etc/sysctl.conf # cat /etc/sysctl.confkernel.sched_child_runs_first=1 修改完毕后，使用以下命令使得参数立即生效 ...

题目： Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation. Example 1: Input: ["2", "1", "+", "3", "*"] Output: ...

这篇文章CFI directives in assembly file (18 Jan 2017)， 是出自google 工程师Adam Langley 问题提出： 函数调用栈 : : | caller's stack | +----------------+ <----$rsp value before CALL | return address | +----------------+ <----$rsp at function entry | caller's rbp | +----------------+ <----$rbp always points here | callee's stack | 函数调用中 调用call指令时将call指令的下一条指令 return address 入栈， 其中return address存放在RIP寄存器中也就是将 RIP入栈，之后进入子函数后会将父函数的栈基地址入栈，其中父函数的栈基地保存在RBP寄存器中。 函数栈调用框架： push rbp mov rbp, rsp …. (子函数处理部分) mov rsp, rbp pop bp （leave） ...

 这篇文章 Delightful User Interfaces: Easter Eggs 是出自 Netflix Technology Blog 作者分享了网剧《Marvel’s Jessica Jones》最后一季的预告片标题页上设置的动态图特效的（Easter Eggs）的实现方法。 背景中摇摆闪烁的电灯，点击后预告片中的照片由 Jessica Jones和她的朋友,转化为Gregory Sallinge。 而这个特效没有使用视频或者webGL ， 是通过css实现的。相比视频10MB，仅需要10kb的css与722kb 图片， 背景图片由5mb压缩到108kb， 没有对效果产生影响。（这里的kb我理解是byte） 下面从三个方面介绍了CSS动态图的实现思路： 1. 开灯效果（Turning on the lights） 使用animation property 通过三张片（关闭，闪烁，开启）图片的切换实现灯泡打开的效果； 通过transform （ (rotateX, rotateX, and translate）, 及30帧图片模拟灯泡摇摆。 2. 灯管特效（Lighting: Flare and Flair） border-radius 设置影响边界, and filter: blur(80px) 设置影响区域. mix-blend-mode: 与背景颜色混合， 效果看上去很棒。 3. 背景聚焦（Bringing the background to focus） 使用 clip-path 用一个圆形对图片进行遮挡. 使用 **transition，**展示背景图片。 遇到的问题（求助StackOverflow） 1. 图片不能再某些浏览器分辨率下可以显示，解决方案 ， 将opacity过渡到父元素 不仅仅是预告片 UI工程师与设计师的合作将其实现的更为简洁而有创意。

题目： You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot. The lock initially starts at '0000', a string representing the state of the 4 wheels. ...