标签归档:面试题

百度招聘的一道题

在烂叶的blog上看到一篇关于百度招聘的一道题
地址:百度招聘的一道试题

有些兴趣,自己实现了下,使用了类蒙地卡罗方法实现。

【题目】
2009百度实习笔试题
要求用PHP,shell或c完成
输入:N(整数)
输入:数据文件A.txt,不超过6条记录,字符串长度不超过15个字节
文件格式如下:
字符串\t数字\n

说明:
每行为1条记录;字符串中不含有\t。
数字描述的是该字符串的出现概率,小于等于100的整数。
多条记录的出现概率之和为100,如果A.txt不满足该条件,程序则退出;
如果文件格式错误,程序也退出。

要求:
编写一个程序,输入为N(正整数),读入文件A.txt,按照字符串出现概率随机地输出字符串,输出N条记录

例如:
输入文件A.txt
abc20
a30
de50
输入为:10

即 abc有20%的概率输出,a有30%的概率输出,de有50%的概率输出,输出10条记录
以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
de
abc
de
a
de
a
de

【算法】
先将数据从文件中取出存放到数组,然后将概率空间分割为所给字符串个数个部分,然后生成N个1-100的随机数,然后看每个随机数落在哪一个区间,就将该区间对应的字符串输出。

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
$filename = "A.txt";
 
/**
* 数据初始化 读取文件内容,拆分字符串形成数据,
* @param <type> $filename  数据文件名
* @return <type> 如果文件打开错误或文件错误返回FALSE                                                      
*/
function data_init($filename) {
    $lines = file($filename);
 
    if ($lines === FALSE) {
       return FALSE;
    }
 
    $data = array();
    foreach ($lines as $row) {
       $row = rtrim($row, "\r\n");
 
       $index = strpos($row, "\t");
       $key = substr($row, 0, $index);
 
       if (strlen($key) > 15) {
           return FALSE;
       }
 
       $data[$key] = (int) substr($row, $index + 1);
    }
 
    return $data;
}
 
$data = data_init($filename);
 
if ($data === FALSE) {  //  输入文件错误
    die('Input File Error!');
}
 
if (array_sum($data) != 100) {  //  输入数据错误
    die('Input Data Error!');
}
 
/* 以类蒙地卡罗方法实现 */
$map = array();
$k = 0;
 
/* 概率空间分割 */
foreach ($data as $key => $row) {                                                 
    $i = $row;
    for ($i = 1; $i <= $row; $i++) {
       $map[$k + $i] = $key;
    }
    $k += $row;
}
 
/* 随机输出 */
$count = 10;
for ($i = 0; $i < $count; $i++) {
    $rand_num = rand(1, 100);
    echo $map[$rand_num], '<br />';
}

关于蒙特卡洛方法请猛击:蒙特卡洛方法

一些sina面试题目的解答

一些sina面试题目的解答
在phpchina上看到了这些题目,看完解答后,很纠结!

1. echo count(“abc”); 输出什么?
答案:出1
解释:在PHP的源码中可以看到,仅对IS_NULL,IS_ARRAY,IS_OBJECT有特殊处理,其它所有的类型都返回1(RETURN_LONG(1);)

2. 用PHP写出显示客户端IP与服务器IP的代码
答案:
“SERVER_ADDR” 当前运行脚本所在的服务器的 IP 地址。
“REMOTE_ADDR” 正在浏览当前页面用户的 IP 地址。

3. error_reporting(2047)什么作用?
答案:error_reporting(E_ALL)
显示所有PHP错误和警告

4. echo,print()和print_r()有什么区别?
答案:echo, print是语言结构,并不是一个真正的函数,print_r是函数打印变量信息
解释:print() is not actually a real function (it is a language construct) so you are not required to use parentheses with its argument list.
这个问题看别人的答案后最纠结

5. 打开php.ini中的Safe_mode,会影响哪些函数?至少说出6个。
1:用户输入输出函数(fopen() file()require(),只能用于调用这些函数有相同脚本的拥有者)
2:创建新文件(限制用户只在该用户拥有目录下创建文件)
3:用户调用popen() systen()exec()等脚本,只有脚本处在safe_mode_exec_dir配置指令指定的目 录中才可能
4:加强HTTP认证,认证脚本拥有者的UID的划入认证领域范围内,此外启用安全模式下,不会设置PHP_AUTH
5:mysql服务器所用的用户名必须与调用mysql_connect()的文件的拥有者用户名相同
6:受影响的函数变量以及配置命令达到40个

6. 写个函数来解决多线程同时读写一个文件的问题。
答案:锁

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 文件写入函数
 * @param     string    $data    需要写入文件的数据
 * @param    string    $filename    文件名
 * @param    string    $type    文件访问类型
 */
function write_file($data, $filename, $type='a') {
    $fp = @fopen($filename, $type);
    flock($fp, LOCK_EX) ;
    fwrite($fp, $data);
    flock($fp, LOCK_UN);
    fclose($fp);
}

7. 请写一个函数验证电子邮件的格式是否正确(要求使用正则)

1
2
3
4
5
6
7
8
/**
 * 验证是否为字符串
 * @param string $email 需要验证的字符串
 * @return bool  返回0或1
 */
function isEmail($email) {
    return preg_match("/^\w+([-+.]\w+)*@\w+([-.]\w+)*\.[a-z]{1,4}$/", $email);
}

8. 考SQL语句的题,题太长了,实在不好回忆了。

9. MySQL数据库,一天一万条以上的增量,怎么优化?

10. 写出一种排序算法(要写出代码),并说出优化它的方法。
快速排序(Quicksort)是对冒泡排序的一种改进。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function qsort(&$array, $low, $high) {
    $i = $low;
    $j = $high;
    $x = $array[$low];
    while ($i < $j) {
 
        while($i < $j && $array[$j] >= $x) {
            $j--;
        }
        $array[$i] = $array[$j];
 
        while ($i < $j && $array[$i] <= $x) {
            $i++;
        }
        $array[$j] = $array[$i];
    }
 
    $array[$i] = $x;
 
    if ($low < $i - 1) {
        qsort($array, $low, $i - 1);
    }
 
    if ($i + 1 < $high) {
        qsort($array, $i + 1, $high);
    }
}
 
$array = array(3, 2, 4, 1, 4, 0, 11, 333, 444, 22, 111, 22, 2);
qsort($array, 0, count($array) - 1);
print_r($array);

11. 写个函数用来对二维数组排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 *  对二维数组进行排序
 *  @param  $array
 *  @param  $keyid  排序的键值
 *  @param  $order  排序方式 'asc':升序 'desc':降序
 *  @param  $type   键值类型 'number':数字 'string':字符串
 */
function sort_array($array, $keyid, $order='asc', $type='number') {
    if(is_array($array)) {
        foreach($array as $val) {
            $order_arr[] = $val[$keyid];
        }
 
        $order = ($order == 'asc') ? SORT_ASC: SORT_DESC;
        $type  = ($type == 'number') ? SORT_NUMERIC: SORT_STRING;
 
        array_multisort($order_arr, $order, $type, $array);
    }
}

12. 写5个不同的自己的函数,来截取一个全路径的文件的扩展名,允许封装php库中已有的函数。
写了5种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 取文件的后缀,通过字符串截取
 * @param string $filename  文件名
 * @return string   文件后缀
 */
function fileext($filename) {
    return strtolower(trim(substr(strrchr($filename, '.'), 1, 10)));
}
 
/**
 *正则
 */
function fileext2($filename) {
    preg_match_all("/^.*\.([^.]+)$/", $filename, $matches);
    return strtolower(trim(substr($matches[1][0], 0, 10)));
}
 
function fileext3($filename) {
    $filename = strtolower(trim(basename($filename)));
    return substr($filename, strrpos($filename, '.') + 1);
}
/**
 * 内置函数
 */
function fileext4($filename) {
    $pathinfo = pathinfo($filename);
    return strtolower($pathinfo['extension']);
}
/**
 * 数组
 */
function fileext5($filename) {
    $arr = explode('.', $filename);
    return strtolower(array_pop($arr));
}
$filename = "/usr/bin/file.txt";
echo fileext($filename);
echo fileext2($filename);
echo fileext3($filename);
echo fileext4($filename);
echo fileext5($filename);
die();

13. 一群猴子排成一圈,按1,2,…,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去…,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。
入门的题目,学C语言的时候都有做过的,貌似计算机三级考试中也有此题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
/**
 * 约瑟夫出圈问题
 * 模拟双向链表实现,没有考虑时间复杂度
 * @param int $m
 * @param int $n
 * @return 
 */
function josegh($m, $n) {
    if ($m < 1 || $n < 1) {
        return FALSE;
    }
 
    $link = array();
    /* 初始化数组值 */
    for ($i = 1; $i <= $n; $i++) {
        $link[$i]['value'] = $i;
    }
 
    /* 初始化下一元素 */
    $link[$n]['next'] = 1;
    for ($i = 1; $i < $n; $i++) {
        $link[$i]['next'] = $i + 1;
    }
 
    /* 初始化上一元素 */
    $link[1]['pre'] = $n;
    for ($i = 2; $i <= $n; $i++) {
        $link[$i]['pre'] = $i - 1;
    }
 
    $rest = $n;
    $index = 1;
    $count = 0;
    while ($rest > 1) {
        $count++;
 
        if ($count % $m == 0) {
            $pop_index = $index;
            $link[$link[$index]['pre']]['next'] = $link[$index]['next'];
            $link[$link[$index]['next']]['pre'] = $link[$index]['pre'];
            $index = $link[$index]['next'];
            $rest--;
            unset($link[$pop_index]);
 
            $count = 0;
        }else{
            $index = $link[$index]['next'];
        }
    }
 
    $rs = array_pop($link);
    return $rs['value'];
}
 
echo josegh(2, 3);