|
锁定老帖子 主题：最新的百度笔试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-10-24
最后修改：2010-10-24
今天在成电百度的运维方向的笔试题，去之前没想多的，就是去学习的心态。凭记忆写下，不是很全，大家见谅，但基本题意还是不会记错的。想请有兴趣的大哥们看看并说下思路。
简答 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----->程序、数据 然后问： 针对每一层谈一谈需要增加的监控，原因，如何做到； 监控信息的相互影响 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2010-10-25
第一题我用
（a%8）^（b%8）不知道可不可以？？ |
| 返回顶楼 | |
|
发表时间：2010-10-25
搞错啦，(*^__^*) 嘻嘻…… 是求幂，
|
| 返回顶楼 | |
|
发表时间：2010-10-25
|
| 返回顶楼 | |
|
发表时间：2010-10-25
和sdu这边的笔试题差不多，sdu这边最后一个是关于微博的数据库的设计
|
| 返回顶楼 | |
|
发表时间：2010-10-25
fwoncn 写道 1.0<a,b<100000，求幂a^b结果的最后三位数 3.判断一个括号字符串是否正确匹配，比如什么({})<[(())]>之类的 2.仅用O(1)的空间复杂度，把int数组分为2部分，奇数靠左，偶数靠右 其它还考了网页抓取队列最优的算法。 |
| 返回顶楼 | |
|
发表时间：2010-10-25
最后修改：2010-10-25
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)。
|
| 返回顶楼 | |
|
发表时间：2010-10-26
TNN SB TM
|
| 返回顶楼 | |
|
发表时间：2010-10-26
chinpom 写道
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的解法不会越界的吧 - -# 可以优化倒是肯定的
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;
}
|
| 返回顶楼 | |
|
发表时间：2010-10-26
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;
}
|
| 返回顶楼 | |
这些题目貌似都不简单哪，笔试运维的也考这么难的吗？LZ答得怎样？今年贵庚，看了这些题目自己好有鸭梨。
LZ那样求幂a^b结果的最后三位数的话，就算是long型都会很快越界的。比如 20^15 就已经超过64位有符号的最大long值了，而且大量的乘法的效率低。原问题的形式可以用 x^y mod N 来表示，这在RSA加密算法中是属于基础的准备算法，可以这样来求：
