This is my test code from the interview with Ivan

test_code.dart

import 'dart:math';

class Patient {
  final int id;
  final List<Record> records;

  Patient({required this.id, required this.records});
}

class Record {
  final int id;

  Record({required this.id});
}

/// return list of patiences with at least 1 record from records list
// Розлянемо алгорит за складністю
// P - кількість пацієнтів
// R - кількість записів у списку records
// M - кількість записів у пацієнта
// C - кількість пацієнтів у returnedPatients

// Загальна складність (мого варіанту, де я не робив returnedPatients Set, а залишив List): O(R) + O(P * M * C)
// Оскільки C буде наближатись до P, то можна сказати що складність буде O(R) + O(P * M * P) ≈ O(P^2 × M)
// Відповідно загальна складність буде O(P^2 × M) ≈ O(n^2). А при умові якщо M ≈ n буде O(n^3). В результаті щось середнє між квадратичною та кубічною.

// з використанням Set для returnedPatients складність O(R) + O(P * M) ≈ O(n^2). Якщо беремо з реальності, що M є відносно малою константою, то можна вважати що складність буде близька до лінійної O(n).
List<Patient> getPatients({
  required List<Patient> patients,
  required List<Record> records,
}) {
  final Set<Patient> returnedPatients = {};

  final Map<int, Record> mapRecords = {}; // O(R) щоб створити мапу (лінійна)
  for (final r in records) {
    mapRecords[r.id] = r;
  }

  for (final patient in patients) {
    // O(P)
    for (final record in patient.records) {
      // O(M) записи пацієнта
      bool patientHasRecord = mapRecords.containsKey(record.id); // O(1)

      if (patientHasRecord) {
        returnedPatients.add(patient); // O(1)
        // break; // Можна додати для оптимізації, щоб не перевіряти далі записи пацієнта
      }
    }
  }
  return returnedPatients.toList();
}

/// return list of patiences with at least 1 record from records list

List<Patient> getPatientsOptimized({
  required List<Patient> patients,
  required List<Record> records,
}) {
  final Set<int> targetRecordIds = records.map((r) => r.id).toSet(); // Лінійна

  return patients.where(
    (patient) {
      // P ітерацій
      return patient.records.any(
        // M ітерацій
        (record) =>
            targetRecordIds.contains(record.id), // O(1) операція пошуку в сеті
      );
    },
  ).toList(); // В цілому складність: O(P * M), що є O(n) за умови що M є меншою, але в даному випадку можна вважати "вкладеним" циклом, тому представляємо як O(n^2)
}

List<Record> generateRecords(int count) {
  return List.generate(count, (index) => Record(id: index + 1));
}

List<Patient> generatePatients(
  int patientsCount,
  int recordsPerPatient,
  List<Record> records,
) {
  final random = Random(1); // Встановлений seed для отримання однакових значень

  return List.generate(patientsCount, (patientIndex) {
    final patientRecords = List.generate(recordsPerPatient, (_) {
      final recordIndex = random.nextInt(records.length);
      return records[recordIndex];
    });
    return Patient(id: patientIndex + 1, records: patientRecords);
  });
}

void main() {
  final records = generateRecords(10000);
  final patients = generatePatients(20000, 20, records);
  final searchForRecords = records.sublist(0, 500);

  final stopwatch = Stopwatch();
  print("Перший варіант...");
  stopwatch.start();
  final result = getPatients(patients: patients, records: searchForRecords);
  stopwatch.stop();
  print(
    'Виконано за: ${stopwatch.elapsedMilliseconds} мс. Результат: ${result.length} паціентів знайдено.',
  );

  stopwatch.reset();

  print("Другий варіант...");
  stopwatch.start();
  final optimizedResult = getPatientsOptimized(
    patients: patients,
    records: searchForRecords,
  );
  stopwatch.stop();
  print(
    'Виконано за: ${stopwatch.elapsedMilliseconds} мс. Результат: ${optimizedResult.length} паціентів знайдено.',
  );
}