Online PHP editor | rfc for CKs1i

<?php /** * Тестовое задание для кандидатов на должность PHP-разработчика * * Файл представляет собой шаблон для выполнения тестового задания. Все объявленные * методы должны быть реализованы непосредственно здесь. Создание дополнительных * собственных методов допускается. * * Код должен соотвестсовать стандартам кодирования Zend Framework (http://framework.zend.com/manual/ru/coding-standard.html) * и работать без генерации предупреждений при включенном режиме error_reporting=E_ALL. * * После выполнения всех задач файл должен быть переименован в следующий формат: * <Date>-<LastName>.php * * Например, 20131216-Ivanov.php * * ВНИМАНИЕ! * - На выполнение задания вы не должны тратить более двух-трех дней. * - Файл должен содержать только класс. */ class PetrosoftCandidate { const DIRECTION_TOP = 'top'; const DIRECTION_BOTTOM = 'bottom'; const DIRECTION_LEFT = 'left'; const DIRECTION_RIGHT = 'right'; /** * Задание 1 * * Во входной строке переставить слова в обратном порядке. Например строка * «one two three four» должна быть преобразована в «four three two one». * * @param string $str Входная строка * @return string Строка с переставленными словами */ public function task1($str) { return implode(' ', array_reverse(explode(' ', $str))); } /** * Задание 2 * * В неупорядоченном массиве целых положительных чисел определить положение * и длину наиболее длинной группы, представляющей собой перестановку элементов * отрезка натурального ряда чисел. * * Элементы массива * 6, 8, 5, 7, 18, 21, 20, 16, 19, 17 * * В нем перестановками являются * 6, 8, 5, 7 * и * 18, 21, 20, 16, 19, 17 * * Вторая группа является наибольшей. Индекс первого элемента второй группы равен 4, * длина группы равна 6. Метод должен вернуть * * array(4, 6) * * @param array $list Входной массив * @throws Exception * @return array Массив из двух * элементов. Первый — индекс первого элемента * самой длинной группы, второй — ее длина. */ public function task2($list) { if (!$list) { // для пустого входного массива невозможно рассчитать ответ throw new Exception("Illegal argument: list is empty"); } /* Пусть длина исходного массива N. Будем последовательно искать в нём перестановки длины N, N-1, N-2 и т.д. */ $listLength = count($list); for ($swapLength = $listLength; $swapLength > 0; $swapLength -= 1) { // ищем перестановки длины $swapLength, перебирая подмассивы for ($offset = 0; $offset <= $listLength - $swapLength; ++$offset) { $candidate = array_slice($list, $offset, $swapLength); if ($this->isSwap($candidate)) { // перестановка найдена! return array($offset, $swapLength); } } } } /** * @param $list array * @return bool является ли массив перестановкой */ private function isSwap($list) { sort($list); $previousValue = $list[0] - 1; // начальное значение этой переменной задаём сами foreach ($list as $value) { if ($value != ($previousValue + 1)) { return false; } $previousValue = $value; } return true; } /** * Задание 3 * * Элементы, расположенные на периметре прямоугольной матрицы, отсортировать по часовой * стрелке в порядке возрастания, начиная с элемента, расположенного в верхнем левом * углу матрицы. * * Например, для входной матрицы: * 1 2 3 4 * 5 6 7 8 * 9 0 1 2 * * Должен быть возвращен результат: * 0 1 1 2 * 9 6 7 2 * 8 5 4 3 * * @param array $matrix Прямоугольная матрица * @throws Exception * @return array Матрица с отсортированными по периметру элементами */ public function task3($matrix) { if (count($matrix) == 0 || count($matrix[0]) == 0) { throw new \Exception('Illegal argument: matrix is empty'); } $perimeter = array(); $cellsOnPerimeter = count($matrix[0]) * 2 + count($matrix) * 2 - 4; // количество клеток на периметре $helperMatrix = $this->createHelperMatrix($matrix); $cell = array('row' => 0, 'column' => 0); $counter = 0; do { // собираем числа с периметра $perimeter []= $matrix[$cell['row']][$cell['column']]; $cell = $this->iterateMatrixClockwise($cell, $helperMatrix); $counter += 1; } while ($counter < $cellsOnPerimeter); sort($perimeter); // сбрасываем вспомогательную матрицу перед новой итерацией $helperMatrix = $this->createHelperMatrix($matrix); $cell = array('row' => 0, 'column' => 0); $counter = 0; do { // возвращаем отсортированные числа на периметр $matrix[$cell['row']][$cell['column']] = $perimeter[$counter]; $cell = $this->iterateMatrixClockwise($cell, $helperMatrix); $counter += 1; } while ($counter < $cellsOnPerimeter); return $matrix; } /** * @param $direction string направление движения (константа класса) * @param $cell array * @param $helperMatrix array вспомогательная матрица для отслеживания уже посещённых клеток * @return mixed Если по указанному направлению можно перейти, то возвращается новая клетка, иначе false */ private function tryDirection($direction, $cell, &$helperMatrix) { switch ($direction) { case self::DIRECTION_RIGHT: $cell['column'] += 1; break; case self::DIRECTION_BOTTOM: $cell['row'] += 1; break; case self::DIRECTION_LEFT: $cell['column'] -= 1; break; case self::DIRECTION_TOP: $cell['row'] -= 1; break; } if ($this->cellCorrect($cell, $helperMatrix)) { return $cell; } else { return false; } } /** * @param $previousCell array массив с ключами row и column * @param $helperMatrix array вспомогательная матрица для отслеживания уже посещённых клеток * @return mixed массив с ключами row и column либо false, если обход завершён */ private function iterateMatrixClockwise($previousCell, &$helperMatrix) { // пробуем продвинуться в матрице по всем направлениям по очереди, начиная с приоритетного foreach (array_unique([$helperMatrix['direction'], self::DIRECTION_RIGHT, self::DIRECTION_BOTTOM, self::DIRECTION_LEFT, self::DIRECTION_TOP]) as $direction) { if ($newCell = $this->tryDirection($direction, $previousCell, $helperMatrix)) { $this->doMoveInHelperMatrix($newCell, $direction, $helperMatrix); return $newCell; } } return false; } /** * @param $cell array массив с ключами row и column * @param $helperMatrix array вспомогательная матрица для отслеживания уже посещённых клеток * @return bool принадлежит ли указанная клетка матрице */ private function cellCorrect($cell, &$helperMatrix) { $row = $cell['row']; $column = $cell['column']; return ($row >= 0) && ($row < $helperMatrix['totalRows']) && ($column >= 0) && ($column < $helperMatrix['totalColumns']) && (!$helperMatrix[$row][$column]); } /** * @param $cell array массив с ключами row и column * @param $direction string направление движения (константа класса) * @param $helperMatrix array вспомогательная матрица для отслеживания уже посещённых клеток */ private function doMoveInHelperMatrix($cell, $direction, &$helperMatrix) { $helperMatrix[$cell['row']][$cell['column']] = true; $helperMatrix['direction'] = $direction; } /** * Создаёт вспомогательную матрицу для отслеживания уже посещённых клеток во время обхода. * false означает, что клетка не посещалась. * Также в этой матрице есть специальный ключи: * 'direction' означает текущее направление движения, 'totalRows' и 'totalColumns' - размеры исходной матрицы * @param $matrix array исходная матрица, для которой нужно создать вспомогательную * @return array вспомогательная матрица, клетка [0, 0] уже помечена как посещённая */ private function createHelperMatrix($matrix) { $totalRows = count($matrix); $totalColumns = count($matrix[0]); $helper = array(); for ($row = 0; $row < $totalRows; ++$row) { $helper []= array_fill(0, $totalColumns, false); } $helper[0][0] = true; /* вся эта группа вспомогательных методов посвящена обходу по часовой стрелке => из начального положения движение идёт направо */ $helper['direction'] = self::DIRECTION_RIGHT; $helper['totalRows'] = count($matrix); $helper['totalColumns'] = count($matrix[0]); return $helper; } /** * Задание 4 * * Сформировать одномерный массив, получающийся при чтении квадратной матрицы по спирали, начиная * с верхнего левого элемента матрицы (против часовой стрелки). * * Например, для входной матрицы: * 1 2 3 4 * 5 6 7 8 * 9 10 11 12 * 13 14 15 16 * * Должен быть возвращен результат: * 1 5 9 13 14 15 16 12 8 4 3 2 6 10 11 7 * * @param array $matrix Входная квадратная матрица * @return array Одномерный массив */ public function task4($matrix) { /* Заметим, что обход матрицы против часовой стрелки аналогичен обходу транспонированной матрицы по часовой стрелке. Поэтому транспонируем исходную матрицу и воспользуемся существующим кодом для задания 3 */ $this->transpose($matrix); $helperMatrix = $this->createHelperMatrix($matrix); $cell = array('row' => 0, 'column' => 0); $elements = array(); do { // собираем числа по спирали $elements []= $matrix[$cell['row']][$cell['column']]; } while ($cell = $this->iterateMatrixClockwise($cell, $helperMatrix)); return $elements; } /** * Транспонирует матрицу * @param $matrix array */ private function transpose(&$matrix) { $totalRows = count($matrix); $totalColumns = count($matrix[0]); for ($row = 0; $row < $totalRows; ++$row) { for ($column = $row + 1; $column < $totalColumns; ++$column) { $temp = $matrix[$row][$column]; $matrix[$row][$column] = $matrix[$column][$row]; $matrix[$column][$row] = $temp; } } } } var_dump(get_class(new PetrosoftCandidate()));

3v4l.org

Active branches

Archived branches