Last active
February 24, 2024 18:54
-
-
Save vudaltsov/ed246caaef9e8ef4c46a328075d38e72 to your computer and use it in GitHub Desktop.
Задачи и решения с собеседования https://youtu.be/ZPGjJDIZm4Y, https://youtu.be/Wa9hUi8NeTs
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?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)); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?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)'); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
На 188 стр вроде не
$quotasSum -= $queueQuotas[$x];должно же быть, а
$totalQuotas -= $queueQuotas[$x];