Напишите PHP функцию для генерации HTML-дерева из таблицы рубрик с полями id, parent_id, title

Что проверяют

Умеете ли вы превратить плоский список с parent_id в дерево и не сделать при этом квадрат по времени и дыру в безопасности. Задача типовая для каталога, и решение видно сразу: кандидат либо индексирует данные по родителю, либо на каждом уровне заново обходит весь массив.

Как отвечать

Сначала один проход и группировка по родителю, потом рекурсивный обход уже по индексу:

function renderTree(array $rows, int $parentId = 0): string
{
    $byParent = [];
    foreach ($rows as $row) {
        $byParent[(int) $row['parent_id']][] = $row;
    }
    return renderLevel($byParent, $parentId);
}

function renderLevel(array $byParent, int $parentId): string
{
    if (empty($byParent[$parentId])) {
        return '';
    }
    $html = '<ul>';
    foreach ($byParent[$parentId] as $row) {
        $html .= '<li>' . htmlspecialchars($row['title'], ENT_QUOTES, 'UTF-8')
            . renderLevel($byParent, (int) $row['id'])
            . '</li>';
    }
    return $html . '</ul>';
}

Проговорите три вещи. Данные берутся одним запросом, а не запросом на каждый уровень. Экранирование через htmlspecialchars с флагами и кодировкой обязательно, иначе название рубрики становится вектором XSS. У листа вложенный список не открывается вовсе, поэтому пустых ul в разметке не будет. Если дерево большое и читается часто, упомяните материализованный путь или вложенные множества, а на стороне базы рекурсивный запрос.

Где спотыкаются

Оставляют наивную рекурсию с полным обходом массива на каждом вызове. На сотне рубрик незаметно, на десятках тысяч страница встаёт, и на уточняющий вопрос про сложность ответить нечего.

Второе: печатают пустой список у каждого листа. Это невалидная разметка, которая вдобавок ломает вёрстку лишними отступами, а ловится она только глазами в браузере.

Третье: забывают про защиту от цикла. Если parent_id ссылается на потомка или на сам узел, рекурсия уходит в бесконечность и падает по памяти. Достаточно ограничения глубины или отметки посещённых узлов.