kenby
- 浏览: 726861 次
- 性别:
- 来自: 北京
-
最新评论
-
wxweven：
Surmounting 写道既然 Java 的跳表那么少，我决 ...
SkipList 跳表 -
暮雪云然：
写的不错，很透彻
Java静态内部类 -
bzhao：
好，赞扬！
Linux信号详解 -
jacktao219：
赞一个~！ ，现在正在看redis 所以接触到跳表
SkipList 跳表 -
is_leon：
vote--后还要判断是否为0吧，如果为0则废掉重新置位can ...
现在有一个整数数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数
文章列表
struct hostent *gethostbyname(const char *name);
gethostbyname函数根据域名解析出服务器的ip地址，它返回一个结构体struct hostent：
#include <netdb.h>
struct hostent {
char *h_name; /* official name of host */
char **h_aliases; /* alias list */
int h_addrtype; /* host address t ...
sockaddr和sockaddr_in的区别
- 博客分类：
- linux
struct sockaddr和struct sockaddr_in这两个结构体用来处理网络通信的地址。
在各种系统调用或者函数中，只要和网络地址打交道，就得用到这两个结构体。
网络中的地址包含3个方面的属性：
1 地址类型: ipv4还是ipv6
2 ip地址
3 端口
相应的，头文件有如下定义：
include <netinet/in.h>
struct sockaddr {
unsigned short sa_family; // 2 bytes address family, AF_xxx
char ...
Mongoose的认证方式跟apache的htdigest认证相似
生成密码文件
./mongoose -A /home/kenby/mongoose/htpasswd localhost kenby yejinhui
mongoose采用md5加密
cat /home/kenby/mongoose/htpasswd
kenby:localhost:96c98c81d5c6019724350f98f93b6b46
启动服务器
./mongoose -R localhost -g /home/kenby/mongoose/htpasswd
基础知识 1) 什么是”Last-Modified”? 在浏览器第一次请求某一个URL时，服务器端的返回状态会是200，内容是你请求的资源，同时有一个Last-Modified的属性标记此文件在服务期端最后被修改的时间，格式类似这样： Last-Modified: Fri, 12 May 2006 18:53:33 GMT 客户端第二次请求此URL时，根据 HTTP 协议的规定，浏览器会向服务器传送 If-Modified-Since 报头，询问该时间之后文件是否有被修改过： If-Modified-Since: Fri, 12 May 2006 18:53:33 GMT 如果服 ...
如果不知道dict中是否有key的值，那么最好用
dict.get(key)
如果用dict[key]这个读取会报KeyError异常，
dict.get方法主要是提供一个取不到对应key的value就返回默认值的功能，
而dict[key]实际上是调用了__getitem__方法
1 不要让技术限制你的职业和人生，技术固然重要，但更重要的是你做的事情，一味地固执下去只会使视野越来越狭窄。
2 回想起来我固执了好多年，今天才幡然醒悟，记得大三的时候小胖和逮哥叫我一起参加一个软件设计大赛，小胖问我有没
有兴趣，我想都没想，直接就拒绝了，因为他们采用java开发，那个时候我正打算独自研究网络编程，不想把时间浪费在对技
术没有提高的项目上，就这样我错过了一个有意思的项目。
3 总结研一大半年的时间，我几乎把全部精力花在学习算法上，我明显的感受到coding能力上了一个档次，但是这种学习
是急功近利的，大部分的学习只是为了把题目做出来， ...
20道选择题，每题3分，共60分
内容涉及：1道概率论题目、数据结构与算法、操作系统、计算机网络
1 概率计算题：4个电阻A、B、C和D，B与C并联后又与A和D串联。
已知B,C,A的可靠性分别为0.7, 0.7, 0.9，问：为了使整个电路的可靠性
不小于0.95，D的可靠性至少为多少？
2 MD5算法产生的密钥有多少个比特？
3 已知一个序列的前4趟排序结果，问用的是什么排序方法？
4 对一个序列使用快速排序，第一趟的结果是什么？
5 给定学生和成绩的数据库表，写一个sql语句求出每门课程的平均分
6 TCP socket连接完毕后，关于sen ...
今天写二叉树的时候遇到一个小问题，写了一个create_node函数用来创建一个二叉树的节点。代码如下：
void create_node(node_t **pnode)
{
node_t *tmp;
tmp = *pnode;
tmp = (node_t *)malloc(node_t);
tmp->data = 3333;
}
用如下方式调用：
node_t *node = NULL;
create_node(&node);
我的目标是创建一个节点，数据为3333，然后把node指向该节点， ...
简答题
1 extern "C" {}的含义是什么？用途是什么？
2 请至少说出2种经典设计模式，说明其应用场景，能够用伪代码说明最好
3 TCP连接time_wait状态的发生场景，以及作用
算法与程序设计
1 拓扑排序
2 字符串处理
系统设计题
海量访问日志的查询
一 给定a、b两个文件，各存放50亿个url，每个url各占用64字节，内存限制是4G，如何找出a、b文件共同的url？
两个50亿个url的文件，大概有50 0000 0000 * 64 B = 640G的大小，肯定不能全部读入内存，可以分组解决
准备1030个桶，读取 ...
现在有一个整数数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数。
算法：充分利用出现次数超过一半这个特点，使用两个变量candidate和vote，分别代表候选人和票数，遍历数组
按如下方式投票和更换候选人：
若当前数与候选人一样，则把候选人的票数加1
若当前数与候选人不一样, 则把它的票数减1，如果减掉后票数小于0，则把候选人踢掉，用当前数作为新的候选人
最后剩下的候选人就是出现次数超过一半的数。
算法的正确性证明： 数组中，数值相同的数都会投赞成票，数值不同的都会投反对票，有一个数出现的次数超过一半，
其它数得到的反对票必然大于 ...
题目：5亿个int，从中找出第k大的数
算法：之后补上。。。
实现：
#include <assert.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/stat.h>
ty ...
题目：100亿个整数，求最大的1万个数，并说出算法的时间复杂度
算法：如果把100亿个数全部读入内存，需要100 0000 0000 * 4B 大约40G的内存，这显然是不现实的。
我们可以在内存中维护一个大小为10000的最小堆，每次从文件读一个数，与最小堆的堆顶元素比较，若比堆顶元素大，
则替换掉堆顶元素，然后调整堆。最后剩下的堆内元素即为最大的1万个数，算法复杂度为O(NlogN)
实现：从文件读数据有讲究，如果每次只读一个数，效率太低，可以维护一个输入缓冲区，一次读取一大块数据到内存，
用完了又从文件接着读，这样效率高很多，缓冲区的大小也有讲究，一般要设为4KB的整 ...
KMP算法曾被我戏称为看毛片算法，当时笑喷......大三那个时候硬着头皮把算法导论的kmp算法啃完，弄懂了kmp算法
的原理，甚至还写出了代码，这几天再次温习的时候，发现忘得比较彻底。我总结，学算法不能只对着书本学理论，而应该
用自己的理解去看清算法的本质，最好用文字把你的理解记录下来，这样才能做到活学活用，而且不容易忘。写这篇博客就是想把自己这几天的思路记下来。
一 kmp算法为什么比传统的字符串匹配算法快
假设文本T = y1y2y3....yn， 模式 P = p1p2p3...pm， 传统的匹配算法把位移为0,1,...n-m时的文本依次跟P比较，每次比较最多花费 ...
一 外部排序的基本思路
假设有一个72KB的文件，其中存储了18K个整数，磁盘中物理块的大小为4KB，将文件分成18组，每组刚好4KB。
首先通过18次内部排序，把18组数据排好序，得到初始的18个归并段R1~R18，每个归并段有1024个整数 ...