Решения задач для подготовки к интервью SWE.

Задача 1

Какие ошибки присутствуют в этом коде? Какое поведение можно ожидать при его выполнении? Как можно устранить эти ошибки?

сhar* ptr = new char[10];
delete ptr; 
delete[] ptr;

Решение:

Ошибки:

1. Неверное использование delete вместо delete[] для указателя на память, выделенную при помощи new[] – UB.

2. Двойное удаление – UB.

Исправленный код:

char* ptr = new char[10];
delete[] ptr; // корректно удаляем массив

Чтобы избежать double-free:

ptr = nullptr;

Задача 2

Что выведет код? Объясните смысл ключевого слова mutable.

#include <iostream>
int main () {
  int a, &j = a;
  [=] () mutable {
    std::cout << std::is_same_v<decltype((j)), int&>;
  }();
  [=] (){
    std::cout << std::is_same_v<decltype((j)), int&>;
  }();
  return 0;
}

Решение:

Код выведет: 1 0

Объяснение:

В обоих случаях у нас вызывается лямбда-функция с захватом переменных по значению. Мы оборачиваем переменную j в скобки внутри decltype для того, чтобы получить тип выражения (j), так как decltype(j) в обоих случаях будет int& без информации о const.

1. Первое лямбда-выражение с mutable: копирует все переменные по значению. Однако, благодаря mutable, значения можно изменять внутри лямбды. При этом j копируется как int, а не как ссылка, поэтому тип выражения (j) в decltype((j)) будет int&, что соответствует true (выводит 1).

2. Второе лямбда-выражение без mutable: ссылка копируется, но нам запрещено изменять ее значение в теле лямбды. В этом можно убедиться, добавив внутрь тела лямбды j++; – это приведет к ошибке компиляции. Лямбду можно представлять как простой класс с объявленным operator(), и по умолчанию operator() имеет квалификатор const. Тип decltype((j)) внутри operator() будет равен const int&, что приводит кstd::is_same_v == false (выводит 0).

В случае лямбды mutable – спецификатор, который позволяет модифицировать объекты, захваченные по значению и вызывать их неконстатные методы.
Еще слово mutable может использоваться как квалификатор поля класса. Такие поля могут быть модифицированы константными методами. Это ключевое слово часто используется для мьютексов.

Задача 3

Решите проблему производитель-потребитель: у вас есть два потока и 256 байт буферной памяти. Поток A записывает непрерывный поток данных, а поток B читает данные из буфера. Синхронизируйте запись данных потоком A и чтение данных потоком B.

Решение:

Данная задача в большей степени посвящена дизайну.

Здесь возможны несколько вариантов:

Простой буфер с мьютексом
Значение sizeof(std::mutex) зависит от компилятора и используемой реализации stdlib. Например, для GCC 14.2 оно составляет 40 байт. Следовательно, в буфере достаточно места для мьютекса. Это позволяет сделать самую тривиальную реализацию – производитель захватывает владение, проверяет, что читатель прочитал данные, производит запись, обновляет информацию о том, сколько данных можно прочитать из буфера и уведомляет читателя при помощи std::condition_variable. Аналогично, читатель ожидает поступления данных, после чего уведомляет о возможности новой записи. Такое решение сильно уменьшает доступный объем буфера, так как sizeof(std::condition_variable) может составлять 48 байт, а так же снижает производительность – синхронизация происходит после каждой записи.
Циклический буфер
Если к мьютексу и condition_variable добавить указатели на текущее место записи и место чтения, то можно избежать явной синхронизации после каждого действия производителя/потребителя. Будем использовать пространство для данных как циклический буфер. Потребитель может читать данные вплоть до указателя записи и наоборот – запись может производиться вплоть до текущего указателя чтения. Для того, чтобы понять, может ли потребитель читать данные (при использовании циклического буфера это нельзя понять по взаимному расположению указателей), можно завести счетчик необработанных данных. Альтернативный подход – счетчик количества эпох. Оба этих подхода требуют дополнительной памяти, поэтому возможен третий вариант – хранить счетчик записанных и прочитанных данных. Тогда эпоху можно определить с помощью деления на длину буфера.
lock-free буфер
Заметим, что размер мьютекса и condition_variable довольно большой в сравнении с указателями. При этом указателей достаточно для того, чтобы понять, что любой из потоков может начать работу. Можно сделать эти указатели атомарными и считать, что изменение значения указателя является триггером для начала работы с данными.
Такой подход сильно увеличивает нагрузку на процессор из-за busy-wait, но позволяет снизить задержку между записью и чтением и выделить больше места для передаваемых данных.

Еще следует учитывать проблему false-sharing. Если данные, которые используются разными потоками, попадают в одну линию кэша, то происходит много лишних синхронизаций и производительность снижается.

Задача 4

Даны две строки s и f (начальная и конечная) и словарь D (набор слов). Нужно определить, можно ли преобразовать s в f, используя только слова из словаря D. При этом каждое преобразование должно менять только один символ, а длина слова должна оставаться неизменной. Если преобразование возможно, нужно найти кратчайшую последовательность таких преобразований и вернуть ее длину. Если преобразование невозможно, вернуть "Преобразование невозможно". Оцените асимптотическую сложность, укажите, какие структуры данных могут быть полезны для решения задачи.

Пример Ввода 1:

D =  ["cat", "cot", "dot", "dog", "bat", "dag"]
s = "cat"
t = "dog"

Вывод: Минимальное количество шагов для преобразования 'cat' в 'dog': 3

Пример Ввода 2:

D =  ["cat", "cot", "bat"]
s = "cat"
t = "dog"

Вывод: Минимальное количество шагов для преобразования 'cat' в 'dog': Преобразование невозможно

Решение:

Исходный словарь можно представить в виде графа, где вершины это слова, а ребра соединяют слова, отличающиеся лишь одной буквой. Количество шагов равно кратчайшему пути в данном графе, который можно найти при помощи обхода в ширину (верно, что вес всех ребер равен 1). При этом строить граф заранее не обязательно.

Пусть L – длина слова, а N – количество слов, K - длина алфавита. Тогда на каждом шаге поиска в ширину мы будем перебирать O(K*L) вариантов. В худшем случае придется перебрать все N слов, общая сложность – O(K * N * L) ~ O(N * L) (K - const).

Для того, чтобы упростить поиск, можно использовать BK-дерево. Построение BK-дерева потребует O(N*L) операций, но это позволит производить поиск соседей с расстоянием 1 за O(log N). Это будет иметь смысл в том случае, если для одного и того же словаря у нас будет много различных запросов.

Еще одной оптимизацией может быть использование очереди с приоритетом. На каждом новом этапе BFS будем начинать с того слова, которое ближе всего к целевому по расстоянию Хэмминга. Это эмпирическое улучшение не влияет на общую асимптотическую сложность, но может улучшить производительность (см. A*).

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

struct Node {
  std::string word;
  int g; // стоимость от начальной точки
  int h; // эвристическая оценка
  int f; // общая стоимость

  Node(const std::string &w, int g_val, int h_val)
      : word(w), g(g_val), h(h_val) {
    f = g + h;
  }

  // Переопределение оператора для приоритетной очереди (минимальная очередь)
  bool operator>(const Node &other) const { return f > other.f; }
};

// Функция для вычисления расстояния Хэмминга между двумя словами
int hammingDistance(const std::string &a, const std::string &b) {
  int dist = 0;
  for (size_t i = 0; i < a.size(); ++i) {
    if (a[i] != b[i])
      ++dist;
  }
  return dist;
}

int bidirectionalAStar(const std::string &s, const std::string &f,
                       const std::unordered_set<std::string> &D) {
  if (s == f)
    return 0;
  if (D.find(f) == D.end())
    return -1;

  std::unordered_set<std::string> visited_s, visited_f;
  std::unordered_map<std::string, int> g_s, g_f;

  auto cmp = [](const Node &a, const Node &b) { return a.f > b.f; };
  std::priority_queue<Node, std::vector<Node>, decltype(cmp)> open_s(cmp);
  std::priority_queue<Node, std::vector<Node>, decltype(cmp)> open_f(cmp);

  int h_s = hammingDistance(s, f);
  int h_f = hammingDistance(f, s);

  open_s.emplace(s, 0, h_s);
  open_f.emplace(f, 0, h_f);

  g_s[s] = 0;
  g_f[f] = 0;

  while (!open_s.empty() && !open_f.empty()) {
    // Расширение из прямого поиска
    {
      Node current = open_s.top();
      open_s.pop();
      visited_s.insert(current.word);

      for (size_t i = 0; i < current.word.size(); ++i) {
        std::string neighbor = current.word;
        for (char c = 'a'; c <= 'z'; ++c) {
          if (neighbor[i] == c)
            continue;
          neighbor[i] = c;
          if (D.find(neighbor) == D.end())
            continue;
          if (visited_s.find(neighbor) != visited_s.end())
            continue;

          int tentative_g = g_s[current.word] + 1;
          if (g_s.find(neighbor) == g_s.end() || tentative_g < g_s[neighbor]) {
            g_s[neighbor] = tentative_g;
            int h = hammingDistance(neighbor, f);
            open_s.emplace(neighbor, tentative_g, h);
          }
          if (visited_f.find(neighbor) != visited_f.end()) {
            return g_s[neighbor] + g_f[neighbor];
          }
        }
      }
    }

    // Расширение из обратного поиска
    {
      Node current = open_f.top();
      open_f.pop();
      visited_f.insert(current.word);

      for (size_t i = 0; i < current.word.size(); ++i) {
        std::string neighbor = current.word;
        for (char c = 'a'; c <= 'z'; ++c) {
          if (neighbor[i] == c)
            continue;
          neighbor[i] = c;
          if (D.find(neighbor) == D.end())
            continue;
          if (visited_f.find(neighbor) != visited_f.end())
            continue;

          int tentative_g = g_f[current.word] + 1;
          if (g_f.find(neighbor) == g_f.end() || tentative_g < g_f[neighbor]) {
            g_f[neighbor] = tentative_g;
            int h = hammingDistance(neighbor, s);
            open_f.emplace(neighbor, tentative_g, h);
          }
          if (visited_s.find(neighbor) != visited_s.end()) {
            return g_s[neighbor] + g_f[neighbor];
          }
        }
      }
    }
  }

  return -1; // Преобразование невозможно
}

int main() {
  std::unordered_set<std::string> D = {"cat", "cot", "dot",
                                       "dog", "bat", "dag"};
  std::string s = "cat";
  std::string f = "dog";

  int result = bidirectionalAStar(s, f, D);
  if (result != -1) {
    std::cout << "Минимальная длина преобразования: " << result << std::endl;
  } else {
    std::cout << "Преобразование невозможно" << std::endl;
  }

  return 0;
}