其实问题在于，在空项目中不生成调试文件pdb，所以无法调试。
要让项目生成pdb文件，需要更改：
项目属性，configuration properties->linker->Generate Debug Info 从 no 改为 yes
2008年4月25日星期五
vc2005 不能调试错误
VC 2005 不能调试 vc2005 无法找到调试信息 未使用调试信息生成二进制文件
2008年4月14日星期一
2008年3月24日星期一
sizeof and -- 测试
#include <stdio.h>
int main()
{
int a=1;
a=a-=a--;
printf("a=%d\n",a);
int size=sizeof(a=2);
printf("size=%d a=%d\n",size,a);
return 0;
}
输出
a=-1;
size=4 a=-1
int main()
{
int a=1;
a=a-=a--;
printf("a=%d\n",a);
int size=sizeof(a=2);
printf("size=%d a=%d\n",size,a);
return 0;
}
输出
a=-1;
size=4 a=-1
2008年3月15日星期六
baidu笔试题 IP段问题
Security公司的网络管理工程师Mr. leak最近发现有不少来自公司外部IP的请求，试图非法访问公司内部资源，为了不影响数据访问流程。
他不得不写一个高效的程序――一个工作在Ipv4上的防火墙，如果请求来自非授权的ip地址，则将请求丢弃。为了便于管理，通过文本文件IP.TXT
他不得不写一个高效的程序――一个工作在Ipv4上的防火墙，如果请求来自非授权的ip地址，则将请求丢弃。为了便于管理，通过文本文件IP.TXT
162.105.91.163
59.66.105.0 59.66.105.255
211.71.0.0 211.71.255.255
限制：IP段的起止地址间以空格隔开。文件不超过10万行，内存不超过4M字节。
要求：请编写一个程序，读入IP.TXT文件。并从标准输入接受一个IP地址。如果该地址在授权范围内，则在标准输出上打印Y,否则打印N.如果输入为一个空行，程序结束。
请给出思路（文字描述），完成代码，分析你采用算法的优劣。
请列举测试方法和思路
发信人: Curvelet (小曲线), 信区: Algorithm
标 题: Re: 谈一条网上的百度笔试题
发信站: 水木社区 (Mon Oct 15 20:59:18 2007), 站内
ip 段是可以合并的，
不需要用 trie 或者 interval tree，
用个数组+二分查找即可。
先把 ip 段改写成 ip 区间形式 [ip_a, ip_b]，
ip_a 是起始 ip 地址， ip_b 是结束 ip 地址。
现对所有 ip 区间按 ip_a 排序，
扫描一遍排序结果，
合并相交的 ip 区间，
结果存在一个数组中。
对于给定的 ip_c，
用二分查找在数组中找到最大的 ip_a <= ip_c，
然后看 ip_c 是否在查找到的区间中即可。
最多 10万行数据，每行对应两个 ip 共 8 字节，
最多 0.8MB。
ps:以ip_a升序排序，顺序扫描ip_b,并记录ip_b的最大值，若当前项的ip_a>以上ip_b 的最大值，则生成一个区间段，以下类似。
------------------------------------------------------------------------------------------------------------------------
2005年百度之星有道求重叠区间大小的题目，和上面的解题思路类似，上面是求并，这里是求交：
题目描述：请编写程序，找出下面"输入数据及格式"中所描述的输入数据文件中最大重叠区间的大小。
对一个正整数n，如果n在数据文件中某行的两个正整数（假设为A和B）之间，即A<=n<=B或A>=n>=B，则n属于
该行；如果n同时属于行i和j，则i和j有重叠区间；重叠区间的大小是同时属于行i和j的整数个数。
例如，行（10 20）和（12 25）的重叠区间为[12 20]，其大小为9；行（20 10）和（12 18）的重叠区间为
[12 18]，其大小为7；行(20 10)和（20 30）的重叠区间大小为1。
输入数据：程序读入已被命名为input.txt的输入数据文本文件，该文件的行数在1到1,000,000之间，每行有
用一个空格分隔的2个正整数，这2个正整数的大小次序随机，每个数都在1和2^32-1之间。（为便于调试，
您可下载测试input.txt文件，实际运行时我们会使用不同内容的输入文件。）
输出数据：在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出0。
评分标准：程序输出结果必须正确，内存使用必须不超过256MB，程序的执行时间越快越好。
思路：按起点降序排序，扫描一遍，维护当前线段之前的线段对后面造成的最远阴影
代码如下：
#include <stdio.h>
#include <stdlib.h>
struct node{
unsigned x;
unsigned y;
}a[1000000];
int compare(const void *a,const void *b)
{
struct node *da=(struct node*)a;
struct node *db=(struct node*)b;
return (da->x)<(db->x);
}
int main()
{
unsigned i,j;
unsigned n=0;
freopen("qujian.txt","r",stdin);
while(scanf("%u%u",&i,&j)!=EOF)
{
if(i<j)
{
a[n].x=i;
a[n].y=j;
}
else
{
a[n].x=j;
a[n].y=i;
}
n++;
}
qsort(a,n,sizeof(struct node),compare); //以x 降序排序
unsigned max;
unsigned tmp;
unsigned ans=0;
max=a[0].y;
for(i=1;i<n;i++)
{
if(a[i].y>max)
{
tmp=max;
max=a[i].y;
}
else
tmp=a[i].y;
if((tmp-a[i].x+1)>ans) //以本节点x为起点对后面造成的最远阴影
ans=tmp-a[i].x+1;
}
printf("%u\n",ans);
return 0;
}
59.66.105.0 59.66.105.255
211.71.0.0 211.71.255.255
限制：IP段的起止地址间以空格隔开。文件不超过10万行，内存不超过4M字节。
要求：请编写一个程序，读入IP.TXT文件。并从标准输入接受一个IP地址。如果该地址在授权范围内，则在标准输出上打印Y,否则打印N.如果输入为一个空行，程序结束。
请给出思路（文字描述），完成代码，分析你采用算法的优劣。
请列举测试方法和思路
发信人: Curvelet (小曲线), 信区: Algorithm
标 题: Re: 谈一条网上的百度笔试题
发信站: 水木社区 (Mon Oct 15 20:59:18 2007), 站内
ip 段是可以合并的，
不需要用 trie 或者 interval tree，
用个数组+二分查找即可。
先把 ip 段改写成 ip 区间形式 [ip_a, ip_b]，
ip_a 是起始 ip 地址， ip_b 是结束 ip 地址。
现对所有 ip 区间按 ip_a 排序，
扫描一遍排序结果，
合并相交的 ip 区间，
结果存在一个数组中。
对于给定的 ip_c，
用二分查找在数组中找到最大的 ip_a <= ip_c，
然后看 ip_c 是否在查找到的区间中即可。
最多 10万行数据，每行对应两个 ip 共 8 字节，
最多 0.8MB。
ps:以ip_a升序排序，顺序扫描ip_b,并记录ip_b的最大值，若当前项的ip_a>以上ip_b 的最大值，则生成一个区间段，以下类似。
------------------------------------------------------------------------------------------------------------------------
2005年百度之星有道求重叠区间大小的题目，和上面的解题思路类似，上面是求并，这里是求交：
题目描述：请编写程序，找出下面"输入数据及格式"中所描述的输入数据文件中最大重叠区间的大小。
对一个正整数n，如果n在数据文件中某行的两个正整数（假设为A和B）之间，即A<=n<=B或A>=n>=B，则n属于
该行；如果n同时属于行i和j，则i和j有重叠区间；重叠区间的大小是同时属于行i和j的整数个数。
例如，行（10 20）和（12 25）的重叠区间为[12 20]，其大小为9；行（20 10）和（12 18）的重叠区间为
[12 18]，其大小为7；行(20 10)和（20 30）的重叠区间大小为1。
输入数据：程序读入已被命名为input.txt的输入数据文本文件，该文件的行数在1到1,000,000之间，每行有
用一个空格分隔的2个正整数，这2个正整数的大小次序随机，每个数都在1和2^32-1之间。（为便于调试，
您可下载测试input.txt文件，实际运行时我们会使用不同内容的输入文件。）
输出数据：在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出0。
评分标准：程序输出结果必须正确，内存使用必须不超过256MB，程序的执行时间越快越好。
思路：按起点降序排序，扫描一遍，维护当前线段之前的线段对后面造成的最远阴影
代码如下：
#include <stdio.h>
#include <stdlib.h>
struct node{
unsigned x;
unsigned y;
}a[1000000];
int compare(const void *a,const void *b)
{
struct node *da=(struct node*)a;
struct node *db=(struct node*)b;
return (da->x)<(db->x);
}
int main()
{
unsigned i,j;
unsigned n=0;
freopen("qujian.txt","r",stdin);
while(scanf("%u%u",&i,&j)!=EOF)
{
if(i<j)
{
a[n].x=i;
a[n].y=j;
}
else
{
a[n].x=j;
a[n].y=i;
}
n++;
}
qsort(a,n,sizeof(struct node),compare); //以x 降序排序
unsigned max;
unsigned tmp;
unsigned ans=0;
max=a[0].y;
for(i=1;i<n;i++)
{
if(a[i].y>max)
{
tmp=max;
max=a[i].y;
}
else
tmp=a[i].y;
if((tmp-a[i].x+1)>ans) //以本节点x为起点对后面造成的最远阴影
ans=tmp-a[i].x+1;
}
printf("%u\n",ans);
return 0;
}
baidu笔试题 数据检索问题 from smth
三、 现有两个文件，
a)数据文件A，格式为：关键词、IP地址、时间
a)数据文件A，格式为：关键词、IP地址、时间
，记录条数为1000万左右，该文件是无序排列的。
b)数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。
要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。
请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。(至少要给出关键算法和设计思路)
简评：
如何对海量数据进行快速检索，这是搜索引擎的必需考虑的问题。这又涉及到数
b)数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。
要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。
请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。(至少要给出关键算法和设计思路)
简评：
如何对海量数据进行快速检索，这是搜索引擎的必需考虑的问题。这又涉及到数
据结构和算法。 因此，要想进入百度，就必须熟悉一些基本的算法和数据结构。
思路及解决方案如下：
1: 设计用TRIE树实现关键词到其对应id的快速词典查找
TRIE树的每一个节点为一个包含256个元素的数组，同时指针指向其下一级节点
节点定义如下：
struct trienode
{
int id;
struct trienode *child[256];
}TRIENODE;
如果TRIE树的某个节点的指针为NULL，说明从跟节点到当前节点的路径构成文件
B中的一个关键词，
在其节点的id保存该关键词的id;如果指针不为NULL，则id对应为0或者一个无穷
大的整数，标志从根节点
到当前节点的路径不是一个完整的关键词。
将关键词转化为二进制无符号char型数组，即对于汉字等双字节字符视为两个无
符号char型整数，
每个元素的取值范围在0到255之间。
2：生成文件b的TRIE树
步骤1：依次读取文件b的每一行，对每一行执行步骤2到步骤5
步骤2：读取关键词id和关键词，令为key
步骤3：依次读取key的每一个字符，对每一个字符，执行步骤4
思路及解决方案如下：
1: 设计用TRIE树实现关键词到其对应id的快速词典查找
TRIE树的每一个节点为一个包含256个元素的数组，同时指针指向其下一级节点
节点定义如下：
struct trienode
{
int id;
struct trienode *child[256];
}TRIENODE;
如果TRIE树的某个节点的指针为NULL，说明从跟节点到当前节点的路径构成文件
B中的一个关键词，
在其节点的id保存该关键词的id;如果指针不为NULL，则id对应为0或者一个无穷
大的整数，标志从根节点
到当前节点的路径不是一个完整的关键词。
将关键词转化为二进制无符号char型数组，即对于汉字等双字节字符视为两个无
符号char型整数，
每个元素的取值范围在0到255之间。
2：生成文件b的TRIE树
步骤1：依次读取文件b的每一行，对每一行执行步骤2到步骤5
步骤2：读取关键词id和关键词，令为key
步骤3：依次读取key的每一个字符，对每一个字符，执行步骤4
;
步骤4：如果该字符对应的指针为NULL，则创建其儿子节点;
步骤5：为当前节点的对应字符id置为关键词id
3：根据A文件生成C文件
步骤1：依次读取文件A的每一行，对每一行执行步骤2到步骤5
步骤2：分别获取当前行关键词、ip地址和时间
步骤3：令关键词key=c1c2...cm，对c1到cm每个字符，执行步骤4
步骤4：获取根节点的第c1个元素指针，转移到节点node1，
根据node1的第c2个元素指针，转移到node2...
根据nodem的第cm个元素，获取关键词的id
步骤5：往文件c中写入一行数据，格式为关键词的id、ip地址和时间
4：复杂度分析
生成文件B的TRIE树过程时间复杂度为O(n*m)，其中n为文件b行数，m为文件b关
键词的最大长度。TRIE的空间复杂度为O(n*m)，n和m含义同上，但由于实际应用中关
键词之间可能会有很多前缀相同现象，所以实际耗费空间并不会很高。
生成C文件的时间复杂度同样为O(n*m)，n为文件a行数，m为文件a关键词的最大
长度，因为有了TRIE树之后，给定一个关键词获得其id的时间复杂度为关键词长度。
生成C文件的过程除了TRIE树空间外基本不需要太多额外的空间，空间复杂度为O(1)
，由于系统有1G的可用内存，TRIE占用的空间在几十兆到200M之间(与关键词集合有
关)，因此本方法完全可行。
步骤4：如果该字符对应的指针为NULL，则创建其儿子节点;
步骤5：为当前节点的对应字符id置为关键词id
3：根据A文件生成C文件
步骤1：依次读取文件A的每一行，对每一行执行步骤2到步骤5
步骤2：分别获取当前行关键词、ip地址和时间
步骤3：令关键词key=c1c2...cm，对c1到cm每个字符，执行步骤4
步骤4：获取根节点的第c1个元素指针，转移到节点node1，
根据node1的第c2个元素指针，转移到node2...
根据nodem的第cm个元素，获取关键词的id
步骤5：往文件c中写入一行数据，格式为关键词的id、ip地址和时间
4：复杂度分析
生成文件B的TRIE树过程时间复杂度为O(n*m)，其中n为文件b行数，m为文件b关
键词的最大长度。TRIE的空间复杂度为O(n*m)，n和m含义同上，但由于实际应用中关
键词之间可能会有很多前缀相同现象，所以实际耗费空间并不会很高。
生成C文件的时间复杂度同样为O(n*m)，n为文件a行数，m为文件a关键词的最大
长度，因为有了TRIE树之后，给定一个关键词获得其id的时间复杂度为关键词长度。
生成C文件的过程除了TRIE树空间外基本不需要太多额外的空间，空间复杂度为O(1)
，由于系统有1G的可用内存，TRIE占用的空间在几十兆到200M之间(与关键词集合有
关)，因此本方法完全可行。
订阅：
博文 (Atom)