0 comments

/**/

Ниже рассмотрим 6 задачек, которые мне встретились на недавнем собеседовании. Задачки типовые: проверяют нания баз данных и языка программирования (php). Без “подвоха“, н требующие подобрать оптимальные алгоритмы/структуры данных таблиц. Что ж, начнем разбор …

Задача №1: оптимизация функции flipA

Что делает эта функция?

<?php

function flipA(&$arr)
{
    for ($i = 0; $i < count($arr); $i++) {
        $tmp = $arr[$i];
        $arr[$i] = $arr[count($arr) - $i - 1];
        $arr[count($arr) - $i - 1] = $tmp;
    }
    return $arr;
}

Анализ: это функция “переворачивания” массива (аналог array_reverse)

В тек реализации ф-я сработает не верно, т.к. перевернет массив дважды, нужно итерацию делать до середины массива:

for ($i = 0; $i < count($arr) / 2; $i++) { ...

Вот еще несколько способов улучшить данную функцию:

Использовать смысловое имя функции, например reverseArray или flipArray.
Убрать передачу аргумента по ссылке в ф-ю: function flipA($arr)
Добавить проверку типа аргумента — убедиться, что передан массив.
Использовать переменную с длиной массива $arrayLength вместо многократного вызова count($arr) для оптимизации.
Заменить цикл на алгоритм с использованием указателей для повышения производительности.
Добавить документирование функции в виде комментариев.
Вынести логику переворота массива в отдельную функцию для повторного использования.
Добавить проверки индексов массива на выход за границы.
Вернуть измененный массив вместо использования ссылки для упрощения использования.
Добавить обработку ошибок и возможных исключительных ситуаций.
Покрыть функцию юнит-тестами для проверки корректности работы.

Реализация этих улучшений сделает код функции более понятным, надежным и оптимизированным.

Мое итоговое решение:

/**
 * Flip array function (new)
 * @param array $arr
 * @return array
 */
function flipArray(array $arr): array {
    $arrayLength = count($arr);
    
    if(!$arrayLength) {
        return [];
    }
    
    for ($i = 0; $i < $arrayLength / 2; $i++) {
        swapArrayElements($arr, $i, $arrayLength - $i - 1);
    }
    
    return $arr;
}

/**
 * Swap 2 array elements
 * @param array $arr
 * @param int $i - index of first element
 * @param int $j - index of second element
 */
function swapArrayElements(&$arr, $i, $j) {
    $tmp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $tmp;
}

$arr2 = [1, 2, 3, 4, 5];
var_dump(flipArray($arr2));

см. тут: https://3v4l.org/ZL6eU

Задача №2: реализация ф-ии strstr

Напишите реализацию для ф-ии strstr:

<?php

function strstr(string $haystack, string $needle)
{
}

strstr('asdfgh', 'f') === 'fgh';

нельзя использовать встроенные ф-ии php: substr, strtok, ...

Мое решение:

<?php

/**
 * Find substring starting in string, starting from some symbol(s)
 * @param string $haystack
 * @param string $needle
 * @return string
 */
function my_strstr(string $haystack, string $needle): string
{
    for($i = 0; $i < strlen($haystack); $i++) {
        if($haystack[$i] == $needle[0]) {
            $eq = true;
            for($j = 0; $j < strlen($needle); $j++) {
                if($haystack[$i + $j] !== $needle[$j]) {
                    $eq = false;
                    break;
                }
            }
            if($eq) {
                return substr($haystack, $i);
            }
        }
    }
}

var_dump(my_strstr('asdfghend', 'fg')); // 'fghend';

Решение: https://3v4l.org/e2TB2

можно еще подумать, как оптимизировать скорость, чтобы работала быстрее чем О(n^2)

полагаю так: счетчик совпадений завести, т.о. избавиться от второй итерации:

<?php

/**
 * Напишите реализацию для ф-ии strstr:
 * function strstr(string $haystack, string $needle)
 * нельзя использовать встроенные ф-ии php: substr, strtok, ...
 * (*) это более удачная реализация, работает за О(n)
 */

/**
 * Find substring starting in string, starting from some symbol(s)
 * @param string $haystack
 * @param string $needle
 * @return string
 */
function my_strstr2(string $haystack, string $needle): string
{
    $isFound = false;
    $lenHaystack = strlen($haystack);
    $lenNeedle = strlen($needle);
    
    for($i = 0, $j = 0, $cnt = 0; $i < $lenHaystack, $j < $lenNeedle; $i++) {
        if($haystack[$i + $j] == $needle[$j]) {
            $j++;
        } else {
            $j = 0;
        }   
        
        if($j >= strlen($lenNeedle)) {
            $isFound = true;
            break;
        }
    }    
    
    return ($isFound ? substr($haystack, $i) : '');
}

var_dump(my_strstr2('asdfghend', 'fg')); // 'fghend';

Запуск решения: https://3v4l.org/XCanS

Задача №3: оптимизация запроса

Как оптимизировать запрос?

# id (pk)| from_user_id | to_user_id | text

select * 
from table 
where from_user_id = 987 
  or to_user_id = 987;

Какой индекс использовать тут: 2 простых или один составной?

Для ускорения данного запроса, где происходит фильтрация по полям from_user_id и to_user_id, имеет смысл добавить следующие индексы:

Индекс по полю from_user_id:

CREATE INDEX idx_from_user_id ON table(from_user_id);

Это позволит быстро находить записи по значению from_user_id.

Индекс по полю to_user_id:

CREATE INDEX idx_to_user_id ON table(to_user_id);

Для быстрого поиска по to_user_id.

Составной индекс по обоим полям:

CREATE INDEX idx_from_to_user_id ON table(from_user_id, to_user_id);

Такой индекс покроет оба варианта фильтрации в запросе.

При наличии этих индексов запрос будет выполняться эффективно за счет сужения сканируемого множества данных по индексированным полям.

в нашем случае составной индекс не сработает, т.к. операция OR а не AND, что эквивалентно запросу с UNION , где 2 индекса отработают независимо:

select * 
from table 
where from_user_id = 987 
UNION
select * 
from table
where to_user_id = 987;

Какой твой любимый тип индексов?

btree ~ “balanced tree index”

Помимо B-деревьев, в базах данных могут использоваться и другие структуры индексов:

Hash-индекс — индекс на основе хеш-таблицы, быстрый поиск по равенству.
R-дерево — пространственный индекс для геометрических данных.
Индексы на основе bitmask — устанавливают биты по определенным правилам.
Плоские файлы — простой индекс в виде отсортированного файла значений.
Индексы по триграммам — для поиска похожих текстовых значений.
Полнотекстовые индексы — инвертированные списки слов для поиска в тексте.
Multi-index — несколько вложенных индексов разных типов.
Индексы по выражениям — виртуальные индексы, зависящие от логики приложения.
Кластерные индексы — сортируют данные физически.

Выбор типа индекса зависит от типов данных, запросов и необходимой производительности.

Какие виды btree индексов есть?

Основные виды B-Tree индексов:

Обычный индекс (index) — наиболее распространенный вид, строится по одному или нескольким столбцам таблицы.
Уникальный индекс (unique index) — гарантирует уникальность значений индексированного столбца, не допускает дубликатов.
Составной индекс (composite index) — строится сразу по нескольким столбцам.
Кластерный индекс (clustered index) — физически сортирует записи таблицы по ключам индекса. Бывает только один кластерный индекс.
Покрывающий индекс (covering index) — содержит все столбцы, фигурирующие в запросе. Запрос выполняется только по индексу.
Частичный индекс (partial index) — строится только для части строк таблицы по некоторому условию.
Пространственный индекс (spatial index) — для работы с геоданными, например R-деревья.

Правильный подбор типов индексов позволяет оптимизировать работу СУБД для конкретных запросов.

Задача №4: поиск по словам

Как организовать поиск по точному соотв слов?

Название: Про маму

Текст:

Мама мыла раму в свой выходной. Папа работал в саду, подстригал траву. итд..

Необходимо составить структуру таблиц, используя которую можно быстро

организовать поиск документов, которые содержат определенные слова.

Словоформы не учитываем, то есть ищем точное совпадение: мама вместо маме, маму и т.п.

Мое решение: хеш-табл с индексами слов (верно):

phrase
-----------------
id (pk)
phrase (text)

words
--------------------------
id (pk)
word (char)

words_to_phrases
-------------------
word_id
phrase_id

Задача №5: система бронирования номеров

Задача:

Проектируется система бронирования номеров

Номер м.б. забронирован 1 чел на 1/неск суток

Как сделать интерфейс бронирования? (с точки зрения БД)

Решение:

users
--------------
user_id
name

rooms
--------------
room_id         # | 1   | 2   |
number          # | 101 | 102 | 

rooms_free_dates
--------------
room_id 
date_from       # '2023-08-08' 
date_to

bookings
--------------
booking_id
user_id
room_id
date_from
date_to

Как забронировать комнату на 1е и 3е число? — сделать 2 отд. бронирования (2 записи в bookings)

Как посмотреть список свободных номеров на 4е число все свободно?

SELECT room_id
FROM rooms_free_dates
WHERE :date >= date_from 
AND :date <= date_to

Как поправить запрос для выбора диапазона дат ? т.е. найти номера, свободные с даты1 по дату2

SELECT room_id
FROM rooms_free_dates
WHERE :date1 >= date_from     # date1 = 4 aug
AND :date2 <= date_to         # date2 = 16 aug

Учитываем существующие бронирования:

SELECT rfd.room_id
FROM rooms_free_dates rfd
WHERE :date1 >= rfd.date_from | date1 = 4 aug
AND :date2 <= rfd.date_to     | date2 = 16 aug
AND NOT EXISTS (
   SELECT 1
   FROM bookings
   WHERE date_from >= :date1
     AND date_from <= :date2
     AND room_id = rfd.room_id 
)

но видно, что приходится проверять 2 таблицы, что не верно;

На деле данные в rooms_free_dates будут обновляться после каждого бронирования, так что доп. проверять booking тут не нужно; но собеседующий советовал с диапазонов свободных дат (rooms_free_dates) перейти на слоты.

Задача №6: код ревью класса Mailer

Посмотреть код, сказать что не так, исправить …

Видим что не верная иерархия наследования, нарушение принципа SRP, и др. мелкие ошибки, исправляем.

Проверь код:

<?php

class Mailer
{
    public function send($to, $subject, $body)
    {
        // Код, производящий отправку письма
        //  коннект к mail серверу, авторизация, передача письма и т.д.
    }
     
     
}
 
class MailMessage extends Mailer
{
    protected $to;
    protected $template;
    protected $data;
     
    public function setTo($to)
    {
        // ...   
    }
     
    public function setTemplate($template)
    {
        // ...
    }
     
    public function setData($data)
    {
        // ...
    }
     
    public function send()
    {
        // Сборка параметров письма из переданных template и data
        //
        // $to = ...
        // $subject = ...
        // $body = ...
         
        parent::send($to, $subject, $body);
    }
}

Поправленный вариант:

<?php

class Mailer
{
    public function send(MailMessage $mailMsg): bool
    {
        // Код, производящий отправку письма
        // коннект к mail серверу, авторизация, передача письма и т.д.
    }
}
 
class MailMessage 
{
    protected string $to;
    protected string $template;
    protected array $data;
     
    public function setTo(string $to): void
    {
        // ...   
    }
     
    public function setTemplate(string $template): void
    {
        // ...
    }
     
    public function setData(array $data): void
    {
        // ...
    }
}

class MailingService
{
    public function send(): bool
    {
        // <calc $to, $tpl, $data>
        
        $mailMsg = new MailMessage();
        $mailMsg->setTo($to);
        $mailMsg->setTemplate($tpl);
        $mailMsg->setData($data);
        
        // ...
        $mailer = new Mailer();        
        $res = $mailer->send($mailMsg);
        
        return $res;
    }
}

Веб-разработчику PHP, готовящемуся к собеседованию, будет полезно ознакомиться с моим авторским пособием, в котором подробно разбираются актуальные вопросы и задачи по теме технических собеседований. Эти материалы основаны на реальном опыте прохождения интервью за последние 5+ лет и помогут качественно подготовиться к предстоящим собеседованиям. В книге вы найдете как популярные вопросы, которые часто задают на собеседованиях PHP-разработчикам, так и практические кейсы и задачи с подробными решениями и разбором.

Нет Ответов

Добавить комментарий Отменить ответ

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Добавить комментарий Отменить ответ

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Шесть простых задачек с собеседования

Задача №1: оптимизация функции flipA

Задача №2: реализация ф-ии strstr

Задача №3: оптимизация запроса

Какой твой любимый тип индексов?

Какие виды btree индексов есть?

Задача №4: поиск по словам

Задача №5: система бронирования номеров

Задача №6: код ревью класса Mailer

Category

Tags

Нет Ответов

Добавить комментарий Отменить ответ

Добавить комментарий Отменить ответ

Поиск по сайту

Последние заметки

Рубрики

Подпишись на новости

Есть вопросы?