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 ...

思维训练 - Thinkin' in induction

热身题 - 24Game

原题请戳我

题意

给你一个包含整数1...n的集合S。接下来进行n-1次操作,每次操作从集合S中选取两个数,在加、减、乘三种运算中选取一种,将结果放回再集合S。在n-1次操作完成后,集合S中只剩下一个数。求问一种取数和运算策略,使最后的结果为24。

举例:

S = [1, 2, 3, 4, 5]

我们选取(2, 5),并进行加法运算,获得结果7。再将7放回集合S中。

此时,S = [1, 3, 4, 7]。

数据范围

1 <= n <= 100000

解答

建议:请思考10分钟后再来看答案

我们日常写代码,往往是为了实现一个功能或者实现一套逻辑。这时候,我们做的事一般是从零开始,然后逐步迭代,最终实现目标。

这是正常的一种思维方式,也是不错的思维 …

more ...

FlatBuffer代码阅读 - 1

FlatBuffer白皮书

Flatbuffer是一个全新的序列化库。

动机

在远古时代,程序性能基本取决于你的指令和循环运行的有多快。但是,在如今的计算机上,计算组件的速度已经远远超过存储组件的速度。如果你想让你的程序飞起来,最重要的就是优化你的内存使用。例如,用多少内存,怎样布局内存,如何分配内存,何时拷贝内存等。

序列化是在程序中非常常见的一种操作,并且通常是程序性能低下的主要原因。一是由于序列化需要额外的临时空间去解析和表示数据,二是由于不优雅的内存分配模式和局部性。

如果一个序列化框架可以不使用额外的对象,没有额外的内存分配,没有内存拷贝,良好的数据局部性,这正是太好不过。不过当下的很多框架通常不能满足以上的条件,因为它们需要向前/向后兼容,需要兼容不同的平台,例如大端/小端和内存对齐都是需要进行兼容性处理的。

FlatBuffer可以做到以上的一切。

Flatbuffer尤其适合移动设备(内存容量和带宽比桌面设备的要低不少),以及需要高性能的应用:游戏。

FlatBuffers

总述

Flatbuffer是一个二进制的buffer。Flatbuffer可以包含嵌套对象如struct、table、vector等并使用偏移量来进行寻址,这样一来,我们就可以像遍历基于指针的结构一样,对flatbuffer元素进行in-place的遍历。 Flatbuffer使用严格的字节对齐和字节顺序(通常是小端)以保证可以跨平台使用。

另外,像table这样的对象,Flatbuffer提供了向前 …

more ...

最小表示法及其证明

问题

对于一个字符串S,求S的循环的同构字符串S’中字典序最小的一个。

我们举例说明,字符串"abcd"的循环同构字符串有:["abcd", "bcda", "cdab", "dabc"]

题目的目标是求这些字符串中字典序最小的那个。

暴力解法

暴力解法非常直观,直接枚举字符串的起点,然后找到构成最小字符串的那一个。

代码就不在这里写了。

最小表示法

最小表示法是解决同构字符串最小表示的巧妙算法。

其算法描述如下:

令i=0,j=1
如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i] == S[j] 设指针k,分别从i和j位置向下比较,直到S[i] != S[j]
         如果S …
more ...

System Design - 最热门的IP地址

写在前面

问题是非常流行的,也确实流行了一阵的system-design问题。在知乎上再次被人提起。然后我非常欣赏陈硕的回答。所以要写一篇文章,记下自己的感想。

问题

海量数据算法:如何从超过10G的记录IP地址的日志中,较快的找出登录次数最多的一个IP?

银弹?

面对这种system-design问题,尤其是这种,非高并发、非实时的问题,很多人会采用_map-reduce_ —— 解决system-design问题的银弹。

我对map-reduce的理解非常肤浅,但是可以解释一下大概的流程。

  1. 将日志进行分片。把hash(ip)相同的ip地址分到同一个片中。(注:这里的hash并不是签名函数,只是一个分片标示)
  2. 分片后的日志的大小会小很多,可以方便的进行排序,记数。
  3. 然后再从各个片中,统计出最热门的IP地址。(或TopK的IP地址)

如果不满意我的答案的话,推荐Mining of Massive Datasets一书,其中对map-reduce算法做一番不错的介绍。

正确的分析姿势

业务实体

业务实体拥有四种主要的组件: 信息模型、生命周期模型 …

more ...

Single Number Problem

Introduction

There are a lot of interview problem based on the 1D-array, which is the one of the easiest "data structure".

But the problem about that simple data structure might not be that simple. Here is the summary of the problem about 1D-array.

Of course, most of them come from …

more ...

简明Python魔法 - 2

再说描述符 - Descriptor

最简单的描述符

覆写类的__get____setter__函数就可以实现一个简单的描述符。对某个类型实例的读写进行额外的控制。

>>> import datetime
>>> class CurrentDate(object):
...     def __get__(self, instance, owner):
...         return datetime.date.today()
...     def __set__(self, instance, value):
...         raise NotImplementedError("Can't change the current date.")
...
>>> class Example(object):
...     date = CurrentDate()
...
>>> e = Example()
>>> e.date
datetime.date(2008, 11, 24 …
more ...

简明Python魔法 - 1

Python中类的实现

在Python的Web框架Django中,Python类的构造特性实现了它大部分的核心功能。

当Python解释器遇到类声明时,会创建一个新的namespace ,并执行其内的所有代码,并将变量注册到这个namespace中。

举例:

>>> class Foo(object):
...     print 'Loading...'
...     spam = 'eggs'
...     print 'Done!'
... 
Loading...
Done!
>>> f = Foo()
>>> f.spam
'eggs'

动态的实现一个类

使用type方法可以动态的代码中实现一个类,接受三个参数“类名”、“基类”、“属性”。

>>> Bar = type('Bar', (object,), {'spam': 'eggs'})
>>> Bar.spam
'eggs'

超类改变一切

“metaprogramming”是指一种在程序运行时创建或改变代码的编程手段。type是一个metaclass,一个创建其它类的metaclass。

我们可以替换掉原生的type,使用我们自己的版本,从而控制创建类的过程。

>>> class …
more ...

Codeforces 447D DZY Loves Modification

题意

给你一个n * m的矩阵,让你做K次操作,使得最后得到的值最大。

操作有两种:

一是在任意一行上操作,最终的结果值加上这一行数的和,然后这一行每一个数都要减去p。

二是在任意一列上操作,最终的结果值加上这一列数的和,然后这一列每一个数都要减去p。

数据范围:1 ≤ n, m ≤ 10^3; 1 ≤ k ≤ 10^6; 1 ≤ p ≤ 100

退化版的题目思路

如果我们只限定一种操作,此题就是简单题了。我们维护一个大根堆,堆中保存每一行(或列)之和。

每次操作只需要取出最大值,加到最终结果上。之后将这个值减去对应的p * n(或p * m),再加入堆中。

经过K次循环,就可以得到最后的答案了。

真正的题目思路

对于行和列同时操作,我们也可以套用这种方法。但是要解决对行操作后,对列上数字的值的影响 …

more ...