数据结构算法之leetcode Longest Substring
给定一个字符串，找到没有重复字符的最长子串的长度。
例如:字符串”abcabcbb”, 最长非重复子串长度是3(“abc”).字符串”pwwkew”, 最长非重复子串长度是3(“wke”).
暴力求解简单粗暴的方法就是找到以字母i开头的非重复子串，比较其长度，找到最大的值。代码如下：
1234567891011121314151617181920212223public class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> hashmap = new HashMap<Character, Integer>(); char[] charArr = s.toCharArray(); int lengthest = 0; for (int i=0; i<charArr.length; i++){ hashmap.put(ch ...
数据结构算法之leetcode Median of two arrays
两个排好序的数组nums1和nums2，长度分别为m和n。找到这两个数组的中位数，如果是偶数，则中位数是上下中位数的平均值。
Example 1:
nums1 = [1, 3]nums2 = [2]The median is 2.0
Example 2:
nums1 = [1, 2]nums2 = [3, 4]The median is (2 + 3)/2 = 2.5
暴力求解按照惯例先来个最简单也最粗暴的方法，将两个数组合并为一个数组，然后根据数组的索引找到中位数。
由于两个数组都是排好序的，则可以使用两个指针进行一边比较元素的大小一边放入第三个数组中，代码如下：
1234567891011121314151617181920212223242526272829303132public class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] num3 = new int[nums1.length+nums2.len ...
NameNode监控用户使用资源
HDFS是Hadoop的基石，对其的使用情况进行监控显的尤为重要。那么怎么来衡量一个用户对hdfs的使用情况呢，用什么来衡量呢？众所周知HDFS是由NameNode和DataNode组成，而NameNode又是HDFS的核心，NameNode中最重要的就是记录整个集群状态的元数据。了解集群的使用情况也就是目前的状态，这些状态记录在元数据中，而元数据中是通过记录各个用户对HDFS的操作来描绘集群的状态，那么是不是可以通过统计各个用户在某个时间段对HDFS的操作数来衡量他们使用HDFS的资源。答案是肯定是，而且此功能已经merge到2.7版本中，下面就来了解下这个patch。
架构nntop的架构图如下：nntop是在NN中的audit loggers中进行拦截，audit log从NN中接收所有user的操作。在audit log中进行拦截能够很好的扩展到其余的NN中。HDFS默认的审计日志是DefaultAuditLogger，nntop是在HDFS中添加了一个新的审计日志类TopAuditLogger，由TopAuditLogger解析审计事件并传送给TopMetrics。Top ...
数据结构算法之leetcode Add Two Numbers
两个非负整数的列表，每个元素都是一个数字，按照由低位到高位排序，求两个链表中的数相加并已链表的方式返回。
例如：Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0 -> 8
这里貌似没有什么高效算法，对两个链表同时遍历相加，并设置一个标识位用来表示是否需要进位。
代码如下：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class Soluti ...
Markdown 及 Sublime Text使用技巧
Markdown 及 Sublime Text使用技巧在已打开的文件中随意跳转
ctrl+p, 然后输入文件名，按Esc 退出该功能
在浏览器中查看效果
ctrl + shift + p 然后输入mp，选择Preview in Browser then 选择markdown
回车空行表示一段#表示一级标题，##表示二级，依次类推，一共六级
强调
被*或者_包围的内容为斜体，被**或者__包围的内容为黑体
无序列表
*
有序列表
1
数据结构算法之leetcode Two Sum
给定一个整形数组和一个整数n，从数组中找到两个数的索引使这两个数之和等于n，以数组的形式返回这两个数的索引。(假设数组中只存在一组这样的数)
例如：Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].
循环遍历首先映入脑海的解决方案，逐步遍历数组中的每个元素，查找是否存在。代码如下：
1234567891011121314151617181920public class Solution { public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; for(int i=0; i< nums.length; i++) { int first = nums[i]; result[0] = i; int second = target ...
数据结构算法之n的平方根保留m位小数
求n的平方根x，x精确到m位小数。例如求n精确到小数点后4位的平方根。
思路：
求n的平方根x，则首先想到的是可不可以从1开始，分别求1、2、3等的平方，看是否等于n。这里就有个问题我为什么首先从1开始，而且为什么各个数的步长为1？也就是说我们应该从哪里开始去试，每次去试时，各个数的步长应该怎么选？
从上面的分析中得出求n的平方根其实就是从小于n的数中找到x，使x*x等于n，这就变成了一个查找的问题，而且是在有序数据集中查找，则最容易想到的就是二分查找，则从哪里开始去试，每次去试时，各个数的步长问题就都解决了。
下面看下二分查找的代码：
123456789101112131415public static int binarySearch(int[] arr, int target){ int low = 0; int high = arr.length-1; while (low <= high){ int mid = (low + high) / 2; if (target > arr[mid])&# ...
HDFS中LightWeightGSet与HashMap结构解析
看见HashMap我就想起了一道HashMap的面试题，先来瞅下这个面试题：HashMap和HashTable的区别？
HashMap是非线程安全的，HashTable是线程安全的。
HashMap的键值都可以为null，HashTable则不行。
HashMap是非线程安全的则效率会高于HashTable，这也是一般都用HashMap的原因。
深入的问题，Java中另一个线程安全的与HashMap类似的类是？ConcurrentHashMap也是一个线程安全类，与HashTable不同的是提供的锁机制不一样(与SynchronizedMap也不一样)HashTable中采用的锁机制是一次锁住整个hash表，从而同一时刻只能由一个线程对其进行操作；ConcurrentHashMap是一次锁住一个桶，hash表默认是16个桶，诸如get、put、remove等操作只锁住当前需要的桶。
上面简单回忆了下HashMap，下面说下LightWeightGSet，LightWeightGSet是HDFS中的一个数据结构，类似HashMap，用来存储block和副本所在dn的映射，是Namen ...
YARN源码分析之StateMachineFactory状态机
状态机由一组状态组成，这些状态大体分为三类，分别为初始状态、中间状态和最终状态。状态机首先由初始状态A开始运行，经过一系列的中间状态后到达最终状态，并在最终状态退出，从而形成一个有向无环图。其状态处理的逻辑是收到一个事件，触发状态A到状态B的转换，而转换操作是由事件对应的hook完成的。
YARN中引入了事件机制和状态机机制，事件机制可以在这篇文章中了解下事件机制的调度器，本篇主要从源码的角度解析下状态机机制中的关键类StateMachineFactory，以ApplicationMaster的状态转换为例。
RMAppImpl中的StateMachineFactoryApplicationMaster的实现在RMAPPImpl类中，其状态转换在RMAppImpl中声明，首先声明了一个静态final类型的属性stateMachineFactory，代码如下：
1234567891011121314151617private static final StateMachineFactory<RMAppImpl, ...
YARN源码分析之AsyncDispatcher事件调度器
YARN采用了事件驱动机制，其核心服务实际上都是一个异步调度器，包括Resourcemanager、Nodemanager、MRAppMaster等。本篇以MRAppMaster为例，其内部包含一个异步调度器AsyncDispatcher，AsyncDispatcher在yarn中的主要作用是对发生的一系列事件找到各个事件对应的handle进行处理，从其功能上可以看出其内部应该有一个队列，队列主要用来存放等待调度的事件，还应该有一个事件与handle的映射表，用来处理各个事件。
通过查看代码首先可以发现AsyncDispatcher是一个服务，继承了AbstractService，其次是通过阻塞队列存放事件，然后单独起一个线程从阻塞队列中消费事件，通过事先定义好的事件和处理器的映射表找到各自的处理器进行处理。
下面看下代码内容，首先看下属性：
123456789101112131415161718192021222324252627// 阻塞队列，用于存放发生的事件private final BlockingQueue<Event> eventQueue;// Asyn ...
