Задачи и решения с собеседования https://youtu.be/ZPGjJDIZm4Y, https://youtu.be/Wa9hUi8NeTs

php_point_interview_1.php

<?php

/**
 * Дано: последовательность натуральных чисел (потенциально бесконечная).
 *
 * Требуется:
 * 1. Написать функцию, которая принимает на вход эту последовательность
 *    и после обработки n элементов выдаёт не более m наибольших чисел
 *    среди уже обработанных отсортированных в порядке возрастания или убывания.
 * 2. Оценить временную сложность алгоритма как O(f(n, m)).
 *
 * Можно считать что n > 0 и m > 0, a также n >> m.
 */
 
 // Последовательность длины $n
function seq(int $n): Generator
{
    while ($n > 0) {
        yield mt_rand(1, 1000);
        $n--;
    }
}

function solution(Generator $seq, int $m): array
{
    $heap = new SplMinHeap();
    foreach($seq as $el) {
        if($heap->count() === $m) {
            if ($heap->top() >= $el ){
                continue;
            }
            $heap->extract();
        }
        $heap->insert($el);
    }
    $res = array_fill(0, $heap->count(), 0);
    
    for($i=0; !$heap->isEmpty(); $i++){
        $res[$i] = $heap->extract();
    }
    
    return $res;
}

// O((n + m)*log2(m)) - оптимально

// O(n*m + m*log(m) - неоптимально

print_r(solution(seq(1000), 10));

php_point_interview_2.php

<?php

/**
 * Дано: арифметическое выражение заданное в форме AST (Abstract Syntax Tree) в префиксной нотации.
 *
 * AST может быть вещественным числом либо массивом, в котором первый элемент это всегда строка обозначающая
 * арифметическую операцию, а все последующие элементы - аргументы этой операции (тоже в формате AST):
 * AST = float | ['operation', arg1, arg2, ..., argN], где arg1, arg2, ..., argN это AST
 *
 * Поддерживаются следующие арифметические операции:
 * унарный (-)
 * унарный (+)
 * сложение (+)
 * вычитание (-)
 * умножение (*)
 * деление (/).
 *
 * Допустимо считать, что входные данные всегда корректны.
 *
 * Требуется написать функцию astToCode которая бы принимала на вход AST и конвертировала бы его в строку кода.
 */
 
function astToCode(array|float $ast): string
{
    if (!is_array($ast)) {
        return (string)$ast;
    }
    if (count($ast) === 2) {
        if(is_array($ast[1]) && $ast[1][0] === $ast[0]) {
            return $ast[0]."(".astToCode($ast[1]).")";
        }
        return $ast[0].astToCode($ast[1]);
    }
    
    $ops = [];
    for($i=1; $i<count($ast); $i++){
        if(!is_array($ast[$i])) {
            $ops[]= astToCode($ast[$i]);
            continue;
        }
        if(pr($ast[0]) > pr($ast[$i][0])){
            $ops[] = "(".astToCode($ast[$i]).")";
            continue;
        }
        if($ast[0] === "-" &&  $i > 1 && pr($ast[$i][0]) === 1){
            $ops[] = "(".astToCode($ast[$i]).")";
            continue;
        }
        
        $ops[] = astToCode($ast[$i]);
    }

    
    return join($ast[0], $ops);
}

function pr($op):int {
    if ($op === "*" || $op === "/") {
        return 2;
    }
    return 1;
}

function test(array|float $ast, string $expectedCode): void
{
    $actualCode = astToCode($ast);
    echo $actualCode === $expectedCode ? 'OK' : "FAIL [$actualCode]";
    echo ": $expectedCode" . PHP_EOL;
}

test(5, '5');
test(['-', ['+', ['+', 3]]], '-+(+3)');
test(['+', ['-', ['-', ['+', 1]]]], '+-(-+1)');
test(['*', ['+', 1, 2], ['-', 3, 1]], '(1+2)*(3-1)');
test(['/', ['*', 2, 5, 7], ['-', 8, ['+', 5, 6]]], '2*5*7/(8-(5+6))');
test(['-', ['+', 1, 2], ['-', 3, 4], ['+', 5, 6]], '1+2-(3-4)-(5+6)');

php_point_interview_3.php

<?php

/**
 * Дано:
 * 1. Канал для отправки сообщений (полезная нагрузка) с заданной пропускной способностью n определяемой как
 *    максимальное количество сообщений которые можно отправить в него за один раз.
 * 2. Произвольное количество очередей с сообщениями (m). Сообщения поступают в очереди асинхронно и в разных количествах.
 *    Могут появляться новые очереди с сообщениями.
 * 3. Каждая очередь имеет идентификатор (целое число).
 * 5. Для каждой очереди известно количество сообщений в ней (на момент запроса).
 * 6. С каждой очередью ассоциировано вещественное положительное число (квота, вес), представляющее собой минимальную
 *    долю в пропускной способности канала (см. примеры ниже).
 *
 * Требуется составить алгоритм который бы на каждой итерации рассчитывал сколько необходимо взять сообщений из
 * каждой очереди для отправки в канал так, чтобы выполнялись следующие условия:
 * 1. Work-conserving: утилизация канала должна быть максимальной. Например, если общее количество сообщений по всем
 *    очередям превышает пропускную способность канала, то количество отправляемых сообщений равно пропускной
 *    способности канала.
 * 2. Starvation free: не должно быть resource starvation относительно очередей с малой долей. Например, отправка идёт
 *    с двух очередей: у одной пропускная способность 1000, а у другой 0.00001. В этом случае, хоть пусть и редко,
 *    но сообщения должны браться из второй очереди.
 * 3. Fairness: гарантия того, что каждая очередь получает доступ к каналу согласно своей квоте.
 *
 * Допустим пропускная способность канала равна 10. Вот несколько примеров того как мог бы работать алгоритм на
 * произвольной итерации:
 * 1. Одна очередь с квотой пропускной способности 0.5 В очереди 100 сообщений. Раз очередь всего одна, то весь канал в
 *    нашем распоряжении и независимо от квоты просто шлём в канал по 10 сообщений за раз.
 * 2. Две очереди с квотой пропускной способности 0.5 В каждой очереди по 100 сообщений. Берём по 5 сообщений из каждой
 *    очереди и отправляем в канал.
 * 3. Две очереди. Квота одной 0.2, а второй 0.8. В каждой очереди по 100 сообщений. Берём из первой по 2 сообщения, а из
 *    второй по 8 сообщений.
 * 4. Две очереди. Квота одной 0.25, а второй 1. Берём из первой очереди по 2 сообщения, а из второй по 8 сообщений.
 * 5. 100 очередей. Все с квотой в 1. В очередях по 100 сообщений. Берём по одному сообщения из каждой десятой очереди,
 *    затем из каждой десятой со смещением на 1 и т.д.
 */

class Source
{
    private const QUEUE_MAX_COUNT = 15;

    /**
     * @var array<int, int>
     */
    private array $queueSizes = [];

    /**
     * @var array<int, float>
     */
    private array $queueQuotas = [];

    /**
     * @var array<int, float>
     */
    private array $quotas = [];

    public function __construct()
    {
        for ($i = 0; $i < self::QUEUE_MAX_COUNT; $i++) {
            $this->quotas[] = mt_rand(1, 10000) / 100;
        }
    }

    /**
     * @return array<int, int>
     */
    public function queueSizes(): array
    {
        return $this->queueSizes;
    }

    /**
     * @return array<int, float>
     */
    public function queueQuotas(): array
    {
        return $this->queueQuotas;
    }

    /**
     * @param int $queueId
     * @param int $batchSize
     * @return int[]
     */
    public function extractMessagesFromQueue(int $queueId, int $batchSize): array
    {
        if (empty($this->queueSizes[$queueId])) {
            return [];
        }
        $size = $this->queueSizes[$queueId];
        $this->queueSizes[$queueId] -= $batchSize;
        if ($this->queueSizes[$queueId] <= 0) {
            unset($this->queueSizes[$queueId]);
            unset($this->queueQuotas[$queueId]);
        }
        $messages = [];
        for ($i = min($size, $batchSize); $i > 0; $i--) {
            $messages[] = mt_rand(0, 1000000);
        }
        return $messages;
    }

    public function next(): void
    {
        sleep(1);
        $queueCount = mt_rand(1, (int)(2 * self::QUEUE_MAX_COUNT / 3));
        while ($queueCount > 0) {
            $queueId = mt_rand(0, self::QUEUE_MAX_COUNT - 1);
            $messageCount = mt_rand(1, 5);
            if (isset($this->queueSizes[$queueId])) {
                $this->queueSizes[$queueId] += $messageCount;
            } else {
                $this->queueSizes[$queueId] = $messageCount;
                $this->queueQuotas[$queueId] = $this->quotas[$queueId];
            }
            $queueCount--;
        }
        $this->printStats($this->queueSizes);
    }

    public function printStats(array $sizes): void
    {
        foreach ($sizes as $queueId => $size) {
            echo "$queueId: [$size, {$this->queueQuotas[$queueId]}]; ";
        }
        echo PHP_EOL;
    }
}

function sendMessages(array $messages): void
{
    echo count($messages) . ' messages sent' . PHP_EOL;
} 
 
// Основная цикл отправки сообщений, на каждой итерации которого вычисляется
// нужное количество сообщений по каждой очереди.
function dispatcher(Source $source) {
    $messages = [];
    $n = 100;
    while (--$n) {
        // Имитируем поступление сообщений в очереди
        $source->next();
        // Рассчитываем количество сообщений которое нужно извлечь из каждой очереди
        $batchSizes = calculateMessageBatchSizes($source->queueSizes(), $source->queueQuotas());
        $source->printStats($batchSizes);
        // Извлекаем нужное количество сообщений из каждой очереди и складываем их в общий массив
        foreach ($batchSizes as $queueId => $batchSize) {
            if ($batchSize <= 0) {
                continue;
            }
            $messages = array_merge(
                $messages,
                $source->extractMessagesFromQueue($queueId, $batchSize)
            );
        }
        // Отправляем сообщения если они есть
        if ($messages) {
            sendMessages($messages);
            $messages = [];
        }
    }
}

/**
 * @param array<int, int> $queueSizes
 * @param array<int, float> $queueQuotas
 * @param int $bandwidth
 * @return array
 */
function calculateMessageBatchSizes(array $queueSizes, array $queueQuotas, int $bandwidth = 20): array
{
    if(array_sum($queueSizes) <= $bandwidth){
        return $queueSizes;
    }
    $res = [];
    $totalQuotas = array_sum($queueQuotas);
    for(; $bandwidth; $bandwidth--) {        
        $z = $totalQuotas*mt_rand() / mt_getrandmax();        
        $quotasSum = 0;
        foreach($queueQuotas as $x=> $quota){
            $quotasSum += $quota;
            if($quotasSum>=$z){
                break;
            }
        }        
        $res[$x] = 1 + $res[$x]??0;
        $queueSizes[$x]--;
        if($queueSizes[$x] === 0) {
            $quotasSum -= $queueQuotas[$x];
            unset($queueQuotas[$x]);
        }
    }
    
    return $res;
}

dispatcher(new Source());

На 188 стр вроде не
$quotasSum -= $queueQuotas[$x];
должно же быть, а
$totalQuotas -= $queueQuotas[$x];