小谈程序员面试

  最近我的一位技术不错的同学想换工作,然后跟我吐槽在面试中碰到了一些奇怪的面试官问了一些不着边际的题目,让我这位同学很是苦恼。其实我之前一直想说说面试,但是也一直比较懒。这次听完他的谈话,结合我的一些面试别人的经验和自己被面试的经验,今天分别来谈谈从面试官角度和被面试者出发,我对一次”良好“面试的看法吧。因为我是做后台开发的,所以讲的东西可能有点偏重于后台开发,但是我觉得面试方法来说是具有普适性的。 1. 从面试官角度出发 面试题目应该覆盖足够广的程度。比如我是做后台开发的,我认为一次合格的后台开发面试应该覆盖到:数据结构&算法、操作系统、网络知识、某一门求职者擅长的编程语言。以上4个我认为是必须需要考察的,另外还有一些比如数据库、分布式、Linux基本操作等相应知识也可以进行适当的考察。不能一次面试只面操作系统,这个就没办法进行系统而全面的考察。 面试考…

Read more

线段树小结

  线段树是一种比较强大的数据结构,主要用于在动态更新区间的情况下,保持查找和更新在O(log(n))级别的时间复杂度。虽然它不是一颗完全二叉树,但构造时按照完全二叉树进行构树,没有的话叶结点留空,数组按完全二叉树构造:对于父节点编号为x,其左右儿子结点分别为:2x和2x+1。如下图所示:   Management range表示该结点的『负责输入结点』的范围,1-3表示负责输入结点1,2和3,即:in[1],in[2]和in[3]。value值表示初始化值,刚开始构造时值为0,构造之后的值为子结点的『某种运算』结果:比如,对于『求区间最小值』,则value(4) = min(value(8), value(9)),value(1) = min(value(2), value(3))`,这个在图中未标出来。图中蓝色结点为输入的结点,虚线方向为数组的输…

Read more

如何修改代理穿透已经升级的墙

  上个月祖国的墙又升级了,据说是阿里联合搞得……这让我等码农怎么活,只是想查查IT的资料而已。这次升完我的shadowsocks都不能用了,上个月一直没时间搞,今天上午折腾了一下,重新穿透了墙。   整个ip没有禁止,因为还是可以访问博客和ssh登录的,然而代理的端口竟然被封了,难道真的是用机器学习方式探测到的。我试了一下,把代理的端口从大端口改到常用的小端口就可以了,比如ftp的20端口,telnet的23端口,当然前提这些进程不能启动,因为肯定无法识别到底是真的ftp服务还是代理中转。   我很怀疑以后墙再升级我的整个ip和域名都要被封了。 说明 本文禁止转载…

Read more

算法题:遍历树中m个点最少需要经过多少个结点

  给定一棵树,从树中任意结点出发,遍历m个结点,最少需要结果多少个结点,结点可以重复走。   思路:找树中最长的链,也就是树的“直径”,假设为d,如果m小于等于d,则输出m就可以了;如果m大于d,则输出d+(m-d)*2,这是因为最长链上的分支路径需要走2遍(一来一回)。那么,直径也就是最长链怎么求?先从任意一个叶子节点x出发,找到最长的路径,假设路径结尾是y节点;再以y为根,找出最长的路径,这条路径就是树的最长路径。两次dfs可以搞定了。   代码: #include <iostream> #include <vector> using namespace std; vector<int> vis; vector<vector<int>> tree; pair&l…

Read more

父进程捕获SIGCHLD信号依旧产生僵死进程

  最近自己写的一段代码出现了很多僵死进程,简约版本代码如下: #include <stdio.h> #include <string> #include <unistd.h> #include <stdlib.h> #include <iostream> #include <sys/wait.h> #include <pthread.h> using namespace std; int cnt = 0; void sig_handler(int signo) { pid_t pid; int stat; pid = wait(&stat); cout << "cnt:" << ++cnt << ", pi…

Read more

Broadview功能简介

  Broadcom最近推出了他们的新产品broadview,提供telemetry的监控方式,将问题定位至芯片级别,其架构如下:   在交换机侧加入agent,提供对芯片级别的操作:包括信息采集以及报文注入等,北向提供REST接口提供信息交互,控制器侧提供操作的具体逻辑。其官网介绍的功能如下: Buffer statistics tracking Packet tracing and injection Black hole detection Performance metrics for BST Drop counters due to congestion Support for StrataXGS and StrataDNX silicon families Reference implementation for applications…

Read more

数据中心网络监控小结

  最近调研了一些关于数据中心网络监控的论文和解决方案,主要关于丢包和延时的定位排查,现在telemetry的技术比较火热,写点东西小结一下,越来越懒得写博客了,写的不是很详细,特别是后面几篇,也可能有理解不到位的地方,欢迎指正。 1. Pingmesh   Pingmesh是微软在2015年提出的,其架构模式在那之前已经在微软的数据中心运行了超过4年,采用商用交换机,每天收集10TB的延迟数据。它能够解决以下三个问题: 定位业务的延迟是否因为网络 提供并且跟踪当前网络服务水平(service level agreement ) 自动排除障碍   微软数据中心采用CLOS架构,如下图所示。拥有的规模如下:服务器规模在10万级别,交换机规模为万,服务器上联万兆。论文中阐述的一些统计和架构如下:时延统计采用端到端,中控系统为微软自己的…

Read more

OpenDaylight中DataStore Tree Notification示例

  DataStore有三种监听事件DataChangeListener、DataTreeChangeListener和DOMDataTreeChangeListener,他们具体的区别可以参考这篇博客,本文主要介绍一下DataTreeChangeListener。DataTreeChangeListener可以用来监听整棵树或者某个子树,子树结点的改变将引发由该子节点递归到根结点整个支路结点都发生改变,原理是version号的变化,具体可以参考我之前的博客。 实验 yang文件   包含多级container的yang文件定义如下: container threshold { description "Threshold configuration"; container temperature {…

Read more

memcpy, memmove和copy/copy_if/copy_n/copy_backward的区别

  在C++中有多种方式可以进行数据拷贝,但它们实现的方式略有不同。 memcpy   memcpy原型如下,其以字节为单位,可以用来拷贝非重合区域。也就是说如果拷贝的源、目的有重合部分的话,结果是undefined,意味着可能偶尔也是对的。但最好不要这么做,原则上memcpy是一种后向拷贝机制:从区间的最后一个元素开始进行拷贝,直到第一个元素。 void* memcpy( void* dest, const void* src, std::size_t count ); memmove   memmove可以支持重合区域的拷贝,其实现可以理解为memmove用另外一块buffer缓存src数据,然后往dst拷贝。但实际上并不是这样,代码在输入时会进行判断:如果src地址小于dst地址,进行后向拷贝;反之如果src地址大于ds…

Read more

OpenDaylight DataStore分析

  网上关于DataStore内部架构和实现细节太少了,大部分都是讲如何使用DataStore,而很少有分析从client开始读写到内存到硬盘的数据流,也没有相关性能分析之类的。由于不能满足『知其所以然』的需求,我只能自己看了。然而,官方的文档真的是杂而乱,在社区问了几个问题也没有反馈……无力吐槽了。以下是我吐血看文档和源码总结的,版本为Beylium,如果有不当之处,希望各位指出。   本文首先简单讲一下MD-SAL的大体架构,然后介绍DataStore内容,包括其内存db和硬盘db。内存db也就是所谓的In-Memory-DataStore主要存储两棵树:Operational Tree和 Config Tree。硬盘db对内存db序列化后写入硬盘,包括snapshot和journal两部分,用于重启后恢复内存db。 1.MD-SAL &emsp…

Read more

NeXt UI Tutorial Supplement

  NeXt is an awesome toolkit developed by Cisco. It is an HTML5/JavaScript based toolkit for network web application which can be used to draw network topology, e.g., data center, laboratory network experiment. It has been added in OpenDaylight community which is an open source community of SDN controller.   There are some tutorials that we can follow online like Next-Tutorials…

Read more

Python json格式化输出

  输出json格式时默认没有换行,不便于查看json结果,可以采用这样进行输出:json.dumps(ret, sort_keys = True, indent = 4, separators=(',', ': ')),进行缩进和换行,方便查看结果。 参考 http://stackoverflow.com/questions/16318543/cant-pretty-print-json-from-python…

Read more

Codeforces 374 Div 2解题报告

  codeforces越打越差,我都无力吐槽了,脑子真的赶不上当年了T_T。 A. One-dimensional Japanese Crossword   题意:挨个输出连续的B的个数。   解题:暴力即可。 B. Passwords   题意:给定一堆密码,Vanya 忘记密码,需要不断尝试,尝试的规则是:长度小的先试,长度一样的顺序不定。求Vanya 最长和最短的尝试次数,尝试k次失败后需要暂停5秒。   解题:暴力即可,注意边界情况的考虑。 C. Journey   题意:给定一个有向图,给定时间约束T,每条边有个时间长度,求在给定时间内经过点的最大值。   解题:简单的爆搜题,需要剪枝的是dist[x][node_nr] != -1 &am…

Read more

How to get return code and return data from Restangular

  Use response.status to get return code when failed and use response.plain() or Restangular.stripRestangular(response) to get return clean data without any Restangular methods. Pay attention that the .plain() attribution is supported after 1.4.0 version of Restangular. Here comes the example: Restangular.all(xxx).post(cmd).then(function(response) { //console.log(response.plain()…

Read more

在OpenDaylight DLUX中添加新的模块

  本文主要介绍如何在DLUX中添加一个模块,加完后我们可以通过http://[host-ip]:8181/index.html的左边侧导航栏访问到我们的页面。添加过程需要对ODL,DLUX和一堆前端的框架比较熟悉,否则会碰到一堆问题,折腾了我好长一段时间,现记录如下,也给有同样问题的人一点帮助。   以下是我从头开始操作的过程以及遇到的问题,注意,本文不是直接安装,而是通过源码编译进行安装。 提前安装软件:grunt、npm、bower。 在github上下载controller,dlux和odlparent,切换到同一分支,然后执行mvn clean install -DskipTests进行分别编译,需要首先安装odlparent,再controller和dlux。此处,注意分支要一致。对于controller和odlparent编译错误较少,…

Read more

STL中的关联式容器

  STL中的关联容器分为set和map两大类,以及他们的衍生体multiset和multimap,这些容器均由红黑树(RB-tree)实现。另外,STL还提供了不在标准之外的关联式容器:hashtable以及以此为底层机制的hash_set,hash_map和他两的multi衍生体。   以红黑树和哈希表为底层结构构造的容器最大的不同是前者为直接排序而后者不是。 1.红黑树   我的这篇博客介绍了红黑树和AVL树的大概轮廓,具体插座和查找细节可以参考《算法导论》,此处不介绍这些细节了。红黑树是一种接近平衡的平衡二叉搜索树,拥有良好的查找、插入复杂度。   STL中的RB-tree提供了两种插入操作:insert_unique()和insert_equal(),前者表示被插入节点的key值独一无二,后者表示ke…

Read more

树状数组小结

  退役好久了,惭愧的是一直没搞过树状数组和线段树,以前都是队友搞的,最近刷codeforeces被树状数组卡了好几次,遂决定怒刷树状数组。 0.算法   本来想写写长篇的算法过程,从如何建树到如何维护更新,结果发现这篇博客写的很赞了,我也就不写了,就写写个人对算法的理解以及刷的题目吧。   树状数组的优点就在于维护了一个前序和树,算法的核心就是『前序和』,碰到的各种题目也都是将各种模型转换为前序和,然后再进行查找和插入操作。   其时间复杂度如下:查找和插入/更新都是O(log MaxVal),其中MaxVal表示树的最大下标,非常适合插入频繁的操作。以下read(x)表示查找x的前序和,update(x, p)表示更新x下标对应的数组的数值为p,以下BIT为表示树状数组的简称。   模板…

Read more

STL中的序列式容器

  在STL中,有以下几个序列式容器:array、vector、heap、priority_queue、list、slist、deque、stack、queue。其中vector、list、deque为三个标准容器(container);stack和queue是在deque上进行封装而成的,专有名词叫做配接器(adapter);array是C++内建容器,不对外使用;heap是基于vector封装的,priority_queue是基于heap封装的;slist是非标准的单向链表。 1.vector   vector是C++中的动态数组,可以动态增删,而不需要类似静态数组自己维护空间的分配,其维护的也是一个连续线性空间,支持随机存取,良好的特性使得其成为STL中最常用的容器之一。   vector中有几个需要注意的概念: vecto…

Read more

后台进程读/写控制台触发SIGTTIN/SIGTTOU信号量

  Unix环境下,当一个进程以后台形式启动,但尝试去读写控制台终端时,将会触发SIGTTIN(读)和SIGTTOU(写)信号量,接着,进程将会暂停(linux默认情况下),read/write将会返回错误。这个时候,shell将会发送通知给用户,提醒用户切换此进程为前台进程,以便继续执行。由后台切换至前台的方式是fg命令,前台转为后台则为CTRL+Z快捷键。   那么问题来了,如何才能在不把进程切换至前台的情况下,读写控制器不会被暂停?答案:只要忽略SIGTTIN和SIGTTOU信号量即可:signal(SIGTTOU, SIG_IGN)。   stty stop/-stop命令是用于设置收到SIGTTOU信号量后是否执行暂停,因为有些系统的默认行为不一致,比如mac是默认忽略,而linux是默认启用。stty -a可以查看当前…

Read more

Pid file和进程副本

  在守护进程(daemon)中,经常需要向/var/run/中写入pid文件:xxx.pid,该文件里的内容是xxx进程的进程号。 1.如何防止启动多个副本   为了防止启动一个进程的多个副本,需要在写的时候申请文件锁,一个进程一旦申请文件锁后,会一直锁住该pid文件,直到进程退出,这样也就达到了只启动一个副本的目的。   实例代码如下: const string LOCKFILE = "/var/run/agent.pid"; const mode_t LOCKMOD = (S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH); int lockfile (int fd) { struct flock fl; fl.l_type = F_WRLCK; fl.l_sta…

Read more