类型-长度-值(TLV)协议

在数据通信协议中,可选的信息或字段通常使用type-length-value(a.k.a TLV)元素来进行编码。

  • Type - 类型

用来标示字段类型的值,通常是一个二进制值或简单的字母

  • Length - 长度

字段长度,单位通常为Byte

  • Value - 值

一个变长的比特数组用来存储这个字段的值

优势

  • TLV序列方便遍历查找
  • 新的字段可以无痛的加入现有的协议中。解析的时候,对于未知的字段,可以轻松的跳过。这点与XML类似
  • TLV元素的顺序可以是随意的
  • TLV元素通常使用二进制存储,可以使解析速度加快并且使数据更小
  • TLV可以与XML数据相互转换,易于人类阅读

例子

在这里,我们以protobuf的可选和变长字段为例。

field_number ++ wire_type

每一个protobuf的字段在传输时,都会加上field_numberwire_type这两个值,这两个值组成这个字段的key。

key = (field_number << 3) | wire_type

field_number标明了字段的编号,方便协议向前向后的兼容。而 …

more ...

Reasons They Recruit

From Ace of Programming Interview, Cpt1 - Hiring Programmers: The Inside Story

Establish a Rapport

For an interviewee, one the the most efficient way to build a rapport is to try to see things in from the interviewer's perspective.

  • understand the motivation of the interviewer
  • establishing a common ground
  • adapting your …
more ...


The Checklist of Steve Yegge

Hey man, I don't know that stuff

Stevey's talking aboooooout

If my boss thinks it's important

I'm gonna get fiiiiiiiiiired

Oooh yeah baaaby baaaay-beeeeee....

非技术部分

热身

好好读一本讲数据结构和算法的书

熟悉一些“术语”,可以强化分辨问题的能力。

Yegge推荐了 Steven S. Skiena 的《算法设计手册》,而我推荐的是 Udi Manber 的《算法引论》

每一本书都有它的长处短处。找一本评价不错的书,认真读完,肯定会有收获。

找个朋友来面试你,尝试白板编程

在白纸/白板上编程的体验和在计算机上大有不同。没有条件的情况下 …

more ...

Snake Problem

题目

在一个平面上,有n+m条蛇,其中n条蛇沿水平方向(y轴方向)移动,m条蛇沿竖直方向(x轴方向)移动。

现给出这些蛇头和尾所在的坐标点,求出这n+m条蛇在此时共有多少个交点。在同一个方向移动的蛇不会有交点。

如图所示,n = 5, m = 4,这些蛇一共有5个交点。

Alt text

分析

对于此题,最简单直接的方法就是枚举蛇两两之间的关系,这种算法的时间复杂度为O(n^2)。

当然,我们不能满足于这种暴力的解法。那么,有没有更优美的方法呢?

Alt text

对于这一条在y轴方向上的(红)蛇来说,它与x轴方向上的(黑)蛇共有三个交点。那么,也就意味着,问题的关键在于,我们如何快速确定某一条红蛇(或黑蛇)与其它蛇一共有多少个交点。

我们可以做出如下假设,我们知道当x = k时,所有在平面上的蛇的位置。根据这个假设,我们可以使用区间求和的算法来确定竖直位置上的蛇会有多少个焦点。

假设我们从x = 0到x …

more ...

思维训练 - Thinkin' in induction 2

最大导出子图(maximal induced graph)

你现在在组织一个学术会议。现在你有一份人员名单。假定名单中的每一个人都同意到达,并且有充足的时间交流意见。同时,每一个科学家都写下了他愿意与其进行交流的科学家的名字。

现在,问题来了:挖掘机技术哪家强?

如果要保证每一位科学家至少能与k位到场的科学家进行深入的交♂流♂。那么我们最多可以邀请多少人到会?

注:如果A愿意和B交流,AB一定会进行交流。反之亦然。

我们可以把问题转化成数学语言:对于一个无向图G=(V, E),试求得G的最大导出子图H,使得H中所有顶点的度大于或等于k,或者证明这样的子图是不存在的。

我们继续使用归纳的思想来解决这个问题。

易得,对于顶点数为k的图,如果存在k-导出子图,则该图必为一个完全图。

假设,对于任意顶点数小于n的图,我们总可以找到图的k-最大导出子图。

对于有n个顶点的图G来说,如果有任意顶点的度小于k,那么对于图G的任意子图,此顶点的度总小于k。

所以,对于图中任意度小于k的点,必然不属于所求的子图。于是,我们每次删除一个不属于k-导出子图的点,就可以把有n个顶点的图问题化归为n-1顶点的图问题。

一对一映射

给定一个集合A和一个映射关系f。求A的一个子集S,使得f对于S是一个一对一映射 …

more ...