返回

2021年百度公司普通程序员面试题

第1题:


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



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


第2题:


 百度Spider如何在不超过抓取限额的情况下使得抓取的网页价值之和最大,要求一个最佳抓取方案。请详细描述你的算法思路(可以用伪代码),并分析时间复杂度和空间复杂度。



 假设每个网页有价值为wi.

wi的值为浮点数,通过堆实现.

wi为整数,则通过桶式排序记录每个价值对应的网页数量


第3题:


 仅用O(1)的空间,将整数数组按奇偶数分成2部分,数组左边是奇数、右边是偶数。(要求:给出完整代码,尽量高效,简洁)



 #两个指针,分别从头和从尾遍历数组,详见代码,已测试通过

#include <stdio.h>

#include <stdlib.h>

#define bool int

#define false 0

#define true 1

void Reorder(int *pData, unsigned int length, bool (*func)(int));

bool isEven(int n);

void ReorderOddEven_1(int *pData, unsigned int length)

{

    if(pData == NULL || length == 0)

        return;

    int *pBegin = pData;

    int *pEnd = pData + length - 1;

    while(pBegin < pEnd)

    {

        // 向后移动pBegin,直到它指向偶数

        while(pBegin < pEnd && (*pBegin & 0x1) != 0)

            pBegin ++;

        // 向前移动pEnd,直到它指向奇数

        while(pBegin < pEnd && (*pEnd & 0x1) == 0)

            pEnd --;

        if(pBegin < pEnd)

        {

            int temp = *pBegin;

            *pBegin = *pEnd;

            *pEnd = temp;

        }

    }

}

void Reorder(int *pData, unsigned int length, bool

  (*func)(int))

{

    if(pData == NULL || length == 0)

        return;

    int *pBegin = pData;

    int *pEnd = pData + length - 1;

    while(pBegin < pEnd)

    {

        //向后移动pBegin

        while(pBegin < pEnd &&!func(*pBegin))

            pBegin ++;

        // 向前移动pEnd

        while(pBegin < pEnd &&func(*pEnd))

            pEnd --;

        if(pBegin < pEnd)

        {

            int temp = *pBegin;

            *pBegin = *pEnd;

            *pEnd = temp;

        }

    }

}

bool isEven(int n)

{

    return (n & 1) == 0;

}


第4题:


 给定两个数A、B(0,<a,b<100000),求A^B中最后三位数是多少。请简要描述你的思路。



 

//二分法求解

//a^b = (a ^ (b/2))^2

int GetPow(int a, int b) {

    if (b == 1 || b == 0) {

        return a;

    }

    if (b % 2) {

        return ((int) (pow((float) GetPow(a, b / 2), 2) * a) % 1000);

    } else {

        return ((int) (pow((float) GetPow(a, b / 2), 2)) % 1000);

    }

}


第5题:


 微博上,每个用户可以发送一条消息,可以 follow 另一个用户, 当用户发送消息时,所有 follow 他的用户都能看见这条消息。如 A follow B,则 B 的消息,A 都能看见。

实现一个微博客消息存储系统,可以使用多台机器来满足性能要求, 可以再海量的用户和消息下,快速的实现以下两种查询:

a)给定一个用户,查询他发送的消息,按消息发送时间排序,新 的消息在前。

b)给定一个用户,查询他 follow 的所有人的消息,按消息发送时 间排序,新的消息在前.



 (a):根据uid,msg分库记录用户的消息.直接通过sql查询实现


(b):A follow B, B发消息的时候主动发送消息id到A的新鲜事列表.

如果A是僵死用户就通过拉的方式,登陆后获取所有关注用户的微薄


相关知识