O(1) 的小乐

Job Hunting

公告

记录我的生活和工作。。。
<2012年6月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

统计

  • 随笔 - 182
  • 文章 - 1
  • 评论 - 41
  • 引用 - 0

留言簿(10)

随笔分类(70)

随笔档案(182)

文章档案(1)

如影随形

搜索

  •  

最新随笔

最新评论

阅读排行榜

评论排行榜

2010百度校园招聘试题 R D-C-2

2010百度校园招聘试题  R D-C-2
第一题 简答 (30分)
1,    定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素,要求min、push以及pop的时间复杂度都是0(1),请简要描述你的思路。 (10分)
2,    阅读代码,说明输出的含义并挑错  (10分)
问题1. 写出下列代码的运行结果的前7行并说明数列的含义。
问题2. 代码中是否有不安全的隐患?原因是?
#include <stdio.h>
#include <string.h>

const int MAX_LEN = 128;
const int MAX_LINE = 20;
int main(int argc, char* argv[])
{
    char str[MAX_LEN] = "1";
    char tmp_str[MAX_LEN] = "";
    char buf[MAX_LEN] = "";

    printf("%s\n",str);
    for (int line = 1;line <= MAX_LINE;++line)
    {
        strcpy(tmp_str,str);
        str[0] = '\0';
        for (int i=0;tmp_str[i] != 0;++i)
        {
            char ch = tmp_str[i];
            int count = 1;
            for (;tmp_str[i+1] == tmp_str[i];++i)
            {
                ++count;
            }
            sprintf(buf,"%d%c",count,ch);
            strcat(str,buf);
        }
        printf("%s\n",str);
    }
    return 0;
}

3,    分别才要线性表、二叉平衡树和哈希表存储数据,请分析它们各有什么优劣?(10分)

第二题 算法与程序设计(40分)
1,    有一串首尾相连的珠子,总共m颗,每颗珠子都有自己的颜色,全部颜色总共有n(n<=10)种。现在要在里面截取一段,要求包含所有不同的颜色,并且长度越短越好。求如何截取。
请详细描述你的算法思路(如需要,可给出伪代码来辅助描述),并分析其时间复杂度和空间复杂度。(20分)
2,    设计一个strnumcmp函数,对比普通的strcmp函数,差别在于,当字符串中遇到数字时,以数字大小为准。对于只有其中一个字符串为数字的情况,仍然沿用原来的strcmp方式。 (20分)
举例说
   strnumcmp的判定结果:”abc”<”abc#”<”abc1”<”abc2”<”abc10”<”abcd”
一般的strcmp的判定结果:”abc”<”abc#”<”abc1”<”abc10”<”abc2”<”abcd”
要求:请给出完整代码,在达到目标的情况下尽量高效,简洁。

第三题 系统设计题(30分)
在大规模数据处理中经常会用到大规模字典。现需要处理一个词搭配的字典。条件为:
1)    字典中存在的项是两个词的搭配,例如:字典中有“今天”和“晚上”是两个词,那么它们组成的搭配为“今天|晚上”和“晚上|今天”
2)    词的集合很大,约为10万量级
3)    一个词并不会和其他所有词搭配,通常只会和不超过1万个其他此搭配
4)    对字典的使用读操作很大,通常每秒有上千次请求,几乎没有写入需求。
请设计一个字典服务系统,当请求是两个词的搭配时,能够快速返回搭配的相关信息。请使用尽可能少的资源,并估算出需要使用的机器资源。

posted on 2010-10-18 12:12 Sosi 阅读(1029) 评论(0)  编辑 收藏 引用 所属分类: Courses


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


统计系统