分类目录： 算法数据结构

如何使用1M的内存排序100万个8位数

作者：童燕群 | 发布日期：三月 27, 2014 | 阅读次数（12,551） | 评论（3）

今天看到这篇文章，颇为震撼，感叹算法之“神通”。借助于合适的算法可以完成看似不可能的事情。

最早这个问题是在Stack Overflow网站上面给出的（Sorting numbers in RAM）：

Sorting numbers in RAM 

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.00分 - 5票) Loading ... Loading ... | 同时归档在：奇趣见闻 | 标签： |

[转] 一个经典编程面试题的“隐退”

作者：童燕群 | 发布日期：三月 22, 2014 | 阅读次数（3,444） | 评论（1）

本文由 伯乐在线 – 王伯 翻译自 The Noisy Channel。

面试程序员很困难。Jeff Atwood 抱怨找一个会写代码的候选人是如此艰难。在技术媒体发布的那些“最佳”面试题中，很少有能让我提起兴趣的——尽管我很喜欢IKEA的这个面试题。Codility和 Interview Street这样的创业公司从这个具有挑战性的课题中看到了机会。与此同时，Diego Basch 呼吁我们停止逼迫求职者进行白板编程。

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.00分 - 6票) Loading ... Loading ... | 同时归档在：职业发展 | 标签： , , , |

云存储中的HTTP鉴权算法分析

作者：童燕群 | 发布日期：二月 7, 2014 | 阅读次数（18,636） | 评论（9）

基于Base64编码的HTTP Basic Authentication由于安全问题，已经不再广泛使用了。在云存储中，数据的安全性一直被广泛关注。亚马逊的AWS S3和Openstack Swift分别采取了不同的算法来对每一个HTTP请求进行鉴权。这里想对二者的鉴权过程作简单分析和总结。

一、AWS S3的HTTP请求鉴权流程

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00分 - 9票) Loading ... Loading ... | 同时归档在：Amazon S3, Swift, 云计算/云存储, 存储技术 | 标签： , , , , , , , |

基于C语言的hash table实现进程内缓存

作者：童燕群 | 发布日期：十二月 3, 2013 | 阅读次数（5,215） | 评论

最近遇到一个问题需要做本地缓存，首先想到就是hash表。如果是java，太easy了。C语言就是需要不停的造轮子，实在不想写这个面试题样的东西了，求助于万能的Google了。找到一个不错的hashtable开源实现：http://troydhanson.github.io/uthash/，BSD的许可，赞。也找到了一篇文章介绍详细的用法：http://blog.csdn.net/hongqun/article/details/6103275。

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00分 - 9票) Loading ... Loading ... | 同时归档在：C/C++, 语言基础 | 标签： , , |

广度优先搜索解决“营救公主”问题

作者：童燕群 | 发布日期：十月 14, 2013 | 阅读次数（10,254） | 评论（6）

在之前的一篇文章（迷宫营救公主算法）中提供了一个半成品的解决方案，之所以说他是半成品，是因为首先选择的算法就不对，采用的是深度优先搜索，其次也没有真正的用对深度优先算法，走过的点应该标记为已经走过，而不应该重复遍历该节点。下面的文章对于广度优先和深度优先两种算法的解释非常到位。今天准备把这个问题再完整的用正确的算法解答一遍。

文章链接：【图论】广度优先搜索和深度优先搜索。

就营救公主的问题而言，这里不再重复描述问题了，请点击这里查看题目分析：链接。这次选用广度优先算法来解决该问题。上面的算法介绍文章中对该算法已经分析得非常清晰了。先给解决本问题的算法伪代码：

这里每个节点有三种状态：

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00分 - 3票) Loading ... Loading ... | 同时归档在：Java | 标签： , , , , , |

Hacker News的排名算法–越是简单的越是有用

作者：童燕群 | 发布日期：十月 2, 2013 | 阅读次数（6,324） | 评论

从dbanotes.net的startup news知道了hacker news，关注了一段时间，发现排名确实能反映绝大多数用户的喜好，并且也不至于让比较热的文章永远出现在前列，而导致没有新的内容被关注。因此对其算法比较好奇，在网络上搜索了一下，看到实际的算法，有点不敢相信，整个系统只需要依赖这样一个简单的算法，不需要任何人工干预（也许链接是否发布出来需要审核）。hacker news的原理很简单，任何人都可以提交链接到网站首页，然后大家可以阅读其他人提交的链接，当发现该链接对自己有意义或者非常好时可以点击一个类似赞的按钮，给该文章投上一票。最终首页上会按照文章的票数多少和发布时间对文章进行热度排序。

整个算法就是基于下面这个表达式：

r=(P – 1) / (t + 2)^1.8

P是得票数，t是时间，天为单位。因此时间越短得票数越多的文章排名靠前，得票数一定，随着时间的增加，文章的排名也会慢慢降低。

已经有人画出了不同的P值对应的r与t的函数曲线图：

bg2012022405

参考链接：基于用户投票的排名算法（一）：Delicious和Hacker News

| 1 分2 分3 分4 分5 分 (5.00分 - 5票) Loading ... Loading ... | 同时归档在：移动互联 | 标签： , |

一道基础的词法解析题

作者：童燕群 | 发布日期：八月 24, 2013 | 阅读次数（4,119） | 评论

原日志信息
标题：《计算单词数目的小程序-2009-05-24考试》
发布时间：5/24/2009
作者：童燕群

2009年，公司开始推行技能鉴定考试，这是我第一次参加的技能鉴定考试，那次考试最终以成绩不作为技术等级评定的依据收场。据说有的部门直接以金钱来奖励考分高者，在天涯论坛上面闹得沸沸扬扬。当年做这道题目时用完了所有考试时间，但是仍然没有调通，晚上回家后又接着奋战几个小时，重新写了这份代码。在现在看来，当时那个迫切想写代码的心情真的是难以理解。软件维护工作做多了，好像是会有这样的感觉。

直接贴代码，题目在代码头部的注释中。

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.86分 - 7票) Loading ... Loading ... | 同时归档在：C/C++, 职业发展 | 标签： , |

迷宫营救公主算法

作者：童燕群 | 发布日期：八月 10, 2013 | 阅读次数（10,711） | 评论（2）

今天下班前在公司的技术题库中看到这道题目，思路很快就有了，递归遍历每一条可能的路径，然后找出最短的路径。回家把代码写出来了。发现算法效率实在是太低了，在矩阵较小的时候还好，当矩阵稍微大一点时根本算不过来，感觉复杂度像是O((N*M)^(N*M))这个数值太庞大了，也完全没有意义。公主等到花儿都谢啦。。

貌似这位同学的算法还不错，还没来得及研究，先做个链接：http://blog.csdn.net/joseph_1118/article/details/9390301

应付较小的矩阵下面的方法还是能蒙混过关的。先发到这里，后面再继续研究优化。题目和代码都在一起：

/**
* 公主被魔王抓走了，王子需要拯救出美丽的公主。他进入了魔王的城堡，魔王的城堡是一座很大的迷宫。
* 为了使问题简单化，我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙，王子不能通过。王子只
* 能移动到相邻（上下左右四个方向)的方格内，并且一秒只能移动一步。地图由’S’，’P’，’.’，’*’
* 四种符号构成，’.’表示王子可以通过，’*’表示墙，王子不能通过；’S’表示王子的位置；’P’表示公主
* 的位置；T表示公主存活的剩余时间，王子必须在T秒内到达公主的位置，才能救活公主。如下图所示：
*/

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00分 - 9票) Loading ... Loading ... | 同时归档在：Java | 标签： , |

分布式存储知识学习清单（完善中）

作者：童燕群 | 发布日期：七月 3, 2013 | 阅读次数（5,361） | 评论（1）

分布式存储是云存储和云计算的基石。没有特别深入的存储基础知识，但是对分布式存储比较感兴趣。希望以不同的开源存储系统的架构特点和细节组成一条学习的主线，以点带面的掌握主流的架构、算法和适用场景。

1、DRBD

1）磁盘IO的截获和处理流程；
2）同步和异步IO复制流程
3）内核态与用户态交互流程
4）文件系统、VFS和块IO之间的关系

2、Ceph

1）对象接口
2）分布式存储的元数据与数据节点分离架构

3、VFS

1）内核知识点
2）本地文件系统

4、关系数据库

1）PostgreSQL、Sqlite，SQL语法，DB文件组织的数据结构

5、算法

1）PAXOS算法：Chubby、BigTable、GFS论文
2）NoSQL、Cassandra、Voldemort，节点间消息通讯模型，多副本一致性保障。
3）CAP定理相关

| 1 分2 分3 分4 分5 分 (4.80分 - 10票) Loading ... Loading ... | 同时归档在：C/C++, Java, Linux内核 |

大整数乘法

作者：童燕群 | 发布日期：一月 3, 2013 | 阅读次数（4,938） | 评论

很长时间都没写过代码了，试着写了这个常见的题目。整体思路：采用整形链表记录大整数的每一位，然后分别遍历乘数和被乘数的每一位，将每两个数字的乘积累加到结果的相应位上面。针对大整数类型，重载输入和输出流，重载乘法。

输出部分实现不是特别好。用STL的容器实现链表也许会简单的多。重载乘法的实现不合常理，本应该返回一个新的对象，为了简单起见，直接返回了新对象的指针；在计算乘法结果时使用了一个递归，理论上来说有可能深度过大，导致栈溢出；另外对于指针和应用的使用不规范。

具体代码：

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.83分 - 6票) Loading ... Loading ... | 同时归档在：C/C++ |
返回顶部