最新的百度笔试题

今天在成电百度的运维方向的笔试题，去之前没想多的，就是去学习的心态。凭记忆写下，不是很全，大家见谅，但基本题意还是不会记错的。想请有兴趣的大哥们看看并说下思路。

简答
1.0<a,b<100000，求幂a^b结果的最后三位数
我的做法比较傻，大概是(伪代码)：
result = a % 1000
for 1...b
    result *= a
    result %= 1000
return result

2.主要是考对C/C++的一些理解
C/C++中存储区域分为？
new分配内存失败的结果？
delete、free的区别、用法
等等

3.判断一个括号字符串是否正确匹配，比如什么({})<[(())]>之类的
我答的用了编译原理的递归向下法

算法（算法题我都有瞎做的成分，就不写我的解法了）
1.写个函数用于对变形的递增数组进行二分查找，比如这样的[7, 8, 9, 1, 2, 3]从1开始循环地看是递增的，但事先你不知道从哪一位开始递增。并且分析时间复杂度。

2.仅用O(1)的空间复杂度，把int数组分为2部分，奇数靠左，偶数靠右

最后是个开放性的题，考系统设计的能力
先画了个图：
用户---->ISP（网通、电信）---->网络设备---->server、OS----->程序、数据
然后问：
针对每一层谈一谈需要增加的监控，原因，如何做到；
监控信息的相互影响

第一题我用
（a%8）^（b%8）不知道可不可以？？

搞错啦，(*^__^*) 嘻嘻…… 是求幂，

  这些题目貌似都不简单哪，笔试运维的也考这么难的吗？LZ答得怎样？今年贵庚，看了这些题目自己好有鸭梨。

和sdu这边的笔试题差不多，sdu这边最后一个是关于微博的数据库的设计

fwoncn 写道


1.0<a,b<100000，求幂a^b结果的最后三位数


3.判断一个括号字符串是否正确匹配，比如什么({})<[(())]>之类的


2.仅用O(1)的空间复杂度，把int数组分为2部分，奇数靠左，偶数靠右


这三道题在南京考点，web研发方向中，题目是一样的。

其它还考了网页抓取队列最优的算法。

  LZ那样求幂a^b结果的最后三位数的话，就算是long型都会很快越界的。比如 20^15 就已经超过64位有符号的最大long值了，而且大量的乘法的效率低。原问题的形式可以用 x^y mod N 来表示，这在RSA加密算法中是属于基础的准备算法，可以这样来求：
Java代码  
public class PowerQuestion {   
  
    public static int modeXp(int x, int y, int n) {   
        if (y == 0)  return 1;   
  
        int z = modeXp(x, y >> 1, n);  //把y除以2并取整   
        if ((y & 1) == 0) {  //如果y为偶数   
            return (z * z) % n;   
        } else {   
            return (x * z * z) % n;   
        }   
    }   
  
    public static void main(String[] args) {   
        System.out.println(modeXp(9, 9, 1000));   
    }   
}  

public class PowerQuestion {

        public static int modeXp(int x, int y, int n) {
                if (y == 0)  return 1;

                int z = modeXp(x, y >> 1, n);  //把y除以2并取整
                if ((y & 1) == 0) {  //如果y为偶数
                        return (z * z) % n;
                } else {
                        return (x * z * z) % n;
                }
        }

        public static void main(String[] args) {
                System.out.println(modeXp(9, 9, 1000));
        }
}  假设N为 x,y,n 三个数中最长的二进制位数，则算法的时间复杂度为O(N^3)。

TNN SB  TM

chinpom 写道
  LZ那样求幂a^b结果的最后三位数的话，就算是long型都会很快越界的。比如 20^15 就已经超过64位有符号的最大long值了，而且大量的乘法的效率低。原问题的形式可以用 x^y mod N 来表示，这在RSA加密算法中是属于基础的准备算法，可以这样来求：
Java代码  
public class PowerQuestion {   
  
    public static int modeXp(int x, int y, int n) {   
        if (y == 0)  return 1;   
  
        int z = modeXp(x, y >> 1, n);  //把y除以2并取整   
        if ((y & 1) == 0) {  //如果y为偶数   
            return (z * z) % n;   
        } else {   
            return (x * z * z) % n;   
        }   
    }   
  
    public static void main(String[] args) {   
        System.out.println(modeXp(9, 9, 1000));   
    }   
}  

public class PowerQuestion {

        public static int modeXp(int x, int y, int n) {
                if (y == 0)  return 1;

                int z = modeXp(x, y >> 1, n);  //把y除以2并取整
                if ((y & 1) == 0) {  //如果y为偶数
                        return (z * z) % n;
                } else {
                        return (x * z * z) % n;
                }
        }

        public static void main(String[] args) {
                System.out.println(modeXp(9, 9, 1000));
        }
}  假设N为 x,y,n 三个数中最长的二进制位数，则算法的时间复杂度为O(N^3)。


lz的解法不会越界的吧 - -# 可以优化倒是肯定的
Java代码  
public static int foo(int a, int b) {   
    a = a % 1000;   
    int res = a;   
    int i = 1;   
    for (; i * 2 < b; i *= 2) {   
        res *= res;   
        res %= 1000;   
    }   
    for (; i < b; i++) {   
        res *= a;   
        res %= 1000;   
    }   
    return res;   
}  

public static int foo(int a, int b) {
        a = a % 1000;
        int res = a;
        int i = 1;
        for (; i * 2 < b; i *= 2) {
                res *= res;
                res %= 1000;
        }
        for (; i < b; i++) {
                res *= a;
                res %= 1000;
        }
        return res;
}  

Java代码  
public static int foo(int a, int b) {   
    int res = a % 1000;   
    int i = 1, j = 1, k = 1;   
    int[] bar = new int[17];          // 2^17 > 100,000   
    bar[j] = res;                     // bar 保存 a^(2^index) % 1000 的结果   
    for (; i * 2 < b; i *= 2) {   
        res *= res;   
        res %= 1000;   
        bar[++j] = res;           // j: index   
        k *= 2;                   // k: 2^index   
    }   
    for (i = b-i; i > 0; ) {   
        if (i < k) {   
            k /= 2;   
            j--;   
        } else {   
            res *= bar[j];   
            res %= 1000;   
            i -= k;   
        }   
    }   
    return res;   
}  

public static int foo(int a, int b) {
        int res = a % 1000;
        int i = 1, j = 1, k = 1;
        int[] bar = new int[17];          // 2^17 > 100,000
        bar[j] = res;                     // bar 保存 a^(2^index) % 1000 的结果
        for (; i * 2 < b; i *= 2) {
                res *= res;
                res %= 1000;
                bar[++j] = res;           // j: index
                k *= 2;                   // k: 2^index
        }
        for (i = b-i; i > 0; ) {
                if (i < k) {
                        k /= 2;
                        j--;
                } else {
                        res *= bar[j];
                        res %= 1000;
                        i -= k;
                }
        }
        return res;
}

很久都没有看到这样的题了