Skip to content

Instantly share code, notes, and snippets.

@vudaltsov

vudaltsov/php_point_interview_1.php

Last active February 24, 2024 18:54
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save vudaltsov/ed246caaef9e8ef4c46a328075d38e72 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save vudaltsov/ed246caaef9e8ef4c46a328075d38e72 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. vudaltsov revised this gist Feb 23, 2024. No changes.
  2. vudaltsov revised this gist Feb 23, 2024. 1 changed file with 196 additions and 0 deletions.
    196 changes: 196 additions & 0 deletions php_point_interview_3.php
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,196 @@
    <?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());
  3. vudaltsov revised this gist Feb 17, 2024. 2 changed files with 0 additions and 0 deletions.
    0 1.php → php_point_interview_1.php
    View file
    File renamed without changes.
    0 2.php → php_point_interview_2.php
    View file
    File renamed without changes.
  4. vudaltsov revised this gist Feb 17, 2024. 1 changed file with 76 additions and 0 deletions.
    76 changes: 76 additions & 0 deletions 2.php
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,76 @@
    <?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)');
  5. vudaltsov created this gist Feb 17, 2024.
    49 changes: 49 additions & 0 deletions 1.php
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,49 @@
    <?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));