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

admin |
15 августа, 2023 |
23:42 |
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++) { ...

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

  1. Использовать смысловое имя функции, например reverseArray или flipArray.

  2. Убрать передачу аргумента по ссылке в ф-ю: function flipA($arr)

  3. Добавить проверку типа аргумента — убедиться, что передан массив.

  4. Использовать переменную с длиной массива $arrayLength вместо многократного вызова count($arr) для оптимизации.

  5. Заменить цикл на алгоритм с использованием указателей для повышения производительности.

  6. Добавить документирование функции в виде комментариев.

  7. Вынести логику переворота массива в отдельную функцию для повторного использования.

  8. Добавить проверки индексов массива на выход за границы.

  9. Вернуть измененный массив вместо использования ссылки для упрощения использования.

  10. Добавить обработку ошибок и возможных исключительных ситуаций.

  11. Покрыть функцию юнит-тестами для проверки корректности работы.

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

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

/**
 * 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, имеет смысл добавить следующие индексы:

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

CREATE INDEX idx_from_user_id ON table(from_user_id);

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

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

CREATE INDEX idx_to_user_id ON table(to_user_id);

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

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

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;
    }
}

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

Category
phpВсе заметкиИМПОРТРАЗНОЕ
Tags
develwikiimport

Нет Ответов

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *

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

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *

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

Рубрики


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

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