分享一道PHP引用相关的面试题

发表于 | 分类于

早几个月前，在杭面试，遇到一个实际项目中经常会遇到的问题，觉得还不错，在此分享一下。

首先这是一道上机题，数据部分我已经上传到github，点击这里获取。你可以直接将其导入到mysql内。

题目要求如下

1、操作category表（上万条数据），以层级(多级分类，3级及以上)的树状结构一次性显示全部商品分类

2、程序运行时间尽量短。

第1点中，需要的数据结构大致如下

1
2
3
4
5
6
7
8
9
10
11
12
女装
--T恤
----长袖T恤
----七分袖T恤
----中袖T恤
------第四级别
----短袖T恤
----无袖T恤
--小衫
----长袖小衫
----中袖小衫
----短袖小衫

有同学可能觉得很简单，这不就是常见的递归的例子嘛。大家可以自己先动手试一下。

本地连接的虚拟机数据库模拟发现，以下程序总耗时基本在0.1秒内，算是满足第2点要求了。

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
$t1 = microtime(true);

header("Content-type: text/html; charset=utf-8");
$mysql_server_name = "192.168.33.20";
$mysql_username = "root"; 
$mysql_password = ""; 
$mysql_database = "test"; 
$table_name = 'category';

$con = @mysqli_connect($mysql_server_name,$mysql_username,$mysql_password);
if (empty($con)){
  die('Could not connect: ' . mysqli_connect_error());
}
$db = mysqli_select_db($con, 'test');
mysqli_query($con, "set names 'utf8'"); 

/**
 * 生成树
 */
function generateTree($data){
    $items = [];
    foreach($data as $value){
        $items[$value['id']] = $value;
    }
    $tree = [];
    foreach($items as $k => $v){
        if(isset($items[$v['parent_id']])){
            $items[$v['parent_id']]['children'][] = &$items[$k];
        } else {
            $tree[] = &$items[$k];
        }
    }

    return $tree;
}

/**
 * 输出树
 */
function outputTree($data, $deep = 0){
    echo "<pre>";
    foreach ($data as $v) {
        printf("%s%s\n", str_repeat('--', $deep), $v['name']);
        if (!empty($v['children'])) {
            outputTree($v['children'], $deep + 1);
        }
    }
}

$allData = [];
$result = mysqli_query($con, "select id,name,parent_id from category"); 
while ($row = mysqli_fetch_assoc($result)){
    $allData[] = $row;
}
mysqli_free_result($result);

outputTree(generateTree($allData));

$t2 = microtime(true);
echo '程序运行时间' . round($t2 - $t1, 6) . '秒<br/>';

值得体会的地方，在于generateTree函数的实现，看不懂的可以输出一下 $items 和 $tree的结构，以便理解。