<input id="suquq"><acronym id="suquq"></acronym></input>
  • <input id="suquq"></input>
    <input id="suquq"></input>
  • <menu id="suquq"><u id="suquq"></u></menu>
    <object id="suquq"><acronym id="suquq"></acronym></object>
  • <input id="suquq"></input>
  • <menu id="suquq"></menu>
    <menu id="suquq"></menu>
  • <input id="suquq"><u id="suquq"></u></input>
    <menu id="suquq"><tt id="suquq"></tt></menu>

    2021年百度公司 C语言开发工程师面试题

    小编:管理员 493阅读 2021.06.17

    第1题:


     用 C 语言写一个函数来执行一串任务。任务是互相依赖的。比如 B 任务依赖 A 任 务,则 A 完成 B 才能执行。不考虑并发限制,假设所有的任务都能一次执行成功, 所有的任务执行时间都相等。任务数据结构原型为:



     

    typedef struct {

        //该任务的 ID

        int id;

        //该任务依赖的任务的 ID

        int *child;

        //该任务依赖的任务个数

        int child_num;

    } task;

     

    // 函数原型:

    bool doschedule(task*pask,inttask_num);

     

    //以下函数可以直接调用:

    void dotask(int id); //执行一个进程

     

    //等待 timeout 时间,并返回一个执行成功的任务的 id,如果没有任务在时间片内完成,则返回-1

    int waittask(int timeout);

     

    bool killtask(int id); //杀掉一个进程


    第2题:


     阐述栈和堆在生命周期、速度、内存性能等方面的不同点。假如现在有一个缓冲 区域绝大多数只需要 1KB 空间,极少数极端情况下需要 100MB,怎么样合理分配内 存?



     栈:栈存在于RAM中。栈是动态的,它的存储速度是第二快的。stack

    堆:堆位于RAM中,是一个通用的内存池。所有的对象都存储在堆中。heap


    2 申请方式

    stack【栈】: 由系统自动分配。 例如,声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间 。

    heap【堆】: 需要程序员自己申请,并指明大小,在c中malloc函数 如p1 = (char *)malloc(10); 在C++中用new运算符 如p2 = (char *)malloc(10); 但是注意:p1、p2本身是在栈中的。


    3 申请后系统的响应

    栈【stack】:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。

    堆【heap】:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序;另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。


    4 申请大小的限制

    栈【stack】:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。

    堆【heap】:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。


    5 申请效率的比较

    栈【stack】:由系统自动分配,速度较快。但程序员是无法控制的。

    堆【heap】:是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便.  另外,在WINDOWS下,最好的方式是用VirtualAlloc分配内存,他不是在堆,也不是在栈是直接在进程的地址空间中保留一快内存,虽然用起来最不方便。但是速度快,也最灵活。

    6 堆和栈中的存储内容

    栈【stack】:在函数调用时,第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址,然后是函数的各个参数,在大多数的C编译器中,参数是由右往左入栈的,然后是函数中的局部变量。注意静态变量是不入栈的。  当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中的下一条指令,程序由该点继续运行。

    堆【heap】:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。 7 存取效率的比较 char s1[] = "aaaaaaaaaaaaaaa";  char *s2 = "bbbbbbbbbbbbbbbbb";  aaaaaaaaaaa是在运行时刻赋值的; 而bbbbbbbbbbb是在编译时就确定的; 但是,在以后的存取中,在栈上的数组比指针所指向的字符串(例如堆)快。


    第3题:


     说明以下包含 const 修饰符的语句的意义

    a). double * ptr=&value;

    b). const double * ptr=&value;

    c). double *constptr =&value;

    d).const double *const ptr=&value;



     const在前内容不能变,const在指针后则指针不能变


    第4题:


     请问 c 语言中怎么去除 const 修饰? 比如:
    const double value=0.2f; double *ptr;
    ptr 怎么样获取 value 的值?



     Ptr=(int *)&value;


    第5题:


     在一维坐标轴上存在许多条线段, 用最简单的算法找出重合长度最长得两条线段。 比如线段 A(1,5)、B(2,8)、C(3,9),则 B 和 C 的重合长度最长,为 5。



     这个问题可以转换成一个动态规划问题:
    比如我们想求Sn(Sn表示从求从第一个segment开始,总共有n个元素的子问题,求这个子问题的最大重合线段。),首先我们要证明这是一个动态规划问题:
    我们要求Sn问题的最大重合线段,那么它只有可能有两种来源:
    (1)Sn-1问题的最大重合线段,即Sn的最大重合线段出自前n-1个线段;
    (2)第n个线段Segment[n-1](注意:我是从0开始计数的,所以下标为n-1的就是第n个线段)和前n-1个线段的重合线段中最长的那一个。
    所以,问题的解法如下:
    (1)首先按照所有线段的end值对所有线段进行排序;
    (2)递归的从后往前求解,比如求Sn的最大重合线段,先通过递归求出Sn-1的最大重合线段(tmpMaxSeg),再求出Segment[n-1]和前n-1个线段的重合线段中最长的那一个(currMaxSeg),比较tmpMaxSeg和currMaxSeg的长度,选出最长的作为Sn的返回值。
    (3)注意:递归出口:size==2时,只有两个线段,通过简单比较就可以得出最大覆盖线段;
    至于这块儿:是为了应对原本传入的线段数组的大小小于等于1的情况,算是边界条件处理了,不是递归的出口。
    假如传入数组大小为3,递归执行到数组大小为2时就可以返回了。

    #include <iostream>

    #include <cstdlib>

    #include <algorithm>

    const int LEN = 3;

    using namespace std;

    struct segment

    {

        int start;

        int end;

    };

    // assume a.end < b.end

    segment commonSeg(const segment & a, const segment & b)

    {

        segment CommonSeg;

        if(a.end < b.start)

        {

            CommonSeg.end = 0;

            CommonSeg.start = 0;

        }

        else

        {

            CommonSeg.end = a.end;

            CommonSeg.start = b.start;

        }

        return CommonSeg;

    }

    int findMaxSegment(int size, segment * Segment, segment & maxSeg)

    {

        if(NULL == Segment)

        {

            cerr << "the segment array is NULL" << endl;

            return -1;

        }

        else if(1 == size)

        {

            maxSeg = Segment[0];

            return maxSeg.end-maxSeg.start;

        }

        else if(2 == size)

        {

            if(Segment[0].end <= Segment[1].start)

            {

                maxSeg.start = 0;

                maxSeg.end = 0;

                return maxSeg.end-maxSeg.start;

            }

            else

            {

                maxSeg.end = Segment[0].end;

                maxSeg.start = Segment[1].start;

                return maxSeg.end-maxSeg.start;

            }

        }

        else

        {

            segment tmpMaxSeg, tmpSeg,currMaxSeg;

            int currMaxLen = 0;

            findMaxSegment(size-1, Segment, tmpMaxSeg);

            for(int i=0; i<size-1; i++)

            {

                tmpSeg=commonSeg(Segment[i], Segment[size-1]);

                if(tmpSeg.end - tmpSeg.start > currMaxLen)

                {

                    currMaxLen = tmpSeg.end - tmpSeg.start;

                    currMaxSeg = tmpSeg;

                }

            }

            if(tmpMaxSeg.end - tmpMaxSeg.start > currMaxLen )

            {

                maxSeg = tmpMaxSeg;

            }

            else

            {

                maxSeg = currMaxSeg;

            }

            return maxSeg.end - maxSeg.start;

        }

    }

     

     

    bool isShorter(const segment & s1, const segment & s2)

    {

        return s1.end < s2.end;

    }

    int main()

    {

        segment * Segment = new segment[LEN];

        Segment[0].start = 1;

        Segment[0].end = 5;

        Segment[1].start = 2;

        Segment[1].end = 8;

        Segment[2].start = 3;

        Segment[2].end = 9;

        sort(Segment, Segment + LEN, isShorter);

        segment maxSeg;

        findMaxSegment(LEN, Segment, maxSeg);

        cout << maxSeg.start << endl;

        cout << maxSeg.end << endl;

        delete [] Segment;

        return 0;

    }


    第6题:


     百度的某服务机制类似于 CS(customer-server),有时候大量用户访问服务器 S, 导致 S 运行效率缓慢。 为了提升效率, 拟在 C 上利用一些空余的结果空间作为缓存。 已知在 C 的一台客户机上,每天接收 1000w query,其中 500w uniq query,每个 query 5KB,客户机内存 3GB,硬盘 500GB。做出一个方案,说明系统结构、存储结 构、性能优化等方面的设计。



     1.所有的query结果都放在硬盘

    2.所有query到query结果的映射存储在内存

    3.多余内存作为缓存,缓存淘汰机制为查询次数和LRU


    第7题:


     判断一个括号字符串是否匹配正确,如果括号有多种,怎么做?如(([]))正确,[[(()错误。



     用栈来出现,凡是左括号就压栈,凡是右括号就出栈,最后如果栈为空就匹配正确


    第8题:


     搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万
    要统计最热门的10条查询串. 内存<1G. 字符串长 0-255
    (1) 主要解决思路
    (2) 算法及其复杂度分析



     分俩部门,第一部分建立 索引树,数据遍历索引树,数据在树中存在的话,count++,数据不存在 就加到索引树上,第二部分建立个含有十个数据的最小堆,将数据的count与堆顶比较,大于堆顶的话,将其加入,同时删除堆顶元素,加入后重新调整堆的位置。


    关联标签:
    微彩