Вопросы по спискам и коллекциям на собеседованиях по C#

// ArrayList может хранить элементы разных типов
ArrayList arrayList = new ArrayList();
arrayList.Add(100);              // int
arrayList.Add("Строка");         // string
arrayList.Add(3.14);             // double
arrayList.Add(true);             // bool
 
// List<T> хранит элементы только указанного типа
List<int> intList = new List<int>();
intList.Add(100);                // OK
// intList.Add("Строка");        // Ошибка компиляции!

ArrayList numbers = new ArrayList();
numbers.Add(42);  // Boxing: int → object
 
int num = (int)numbers[0];  // Unboxing: object → int

List<int> numbers = new List<int>();
numbers.Add(42);  // Нет boxing!
 
int num = numbers[0];  // Нет unboxing и приведения типов!

// Тест производительности
const int iterations = 10000000;
 
// Тест ArrayList
var startTime = DateTime.Now;
ArrayList arrayList = new ArrayList();
for (int i = 0; i < iterations; i++)
{
    arrayList.Add(i);  // Boxing
}
for (int i = 0; i < iterations; i++)
{
    int x = (int)arrayList[i];  // Unboxing и приведение
}
Console.WriteLine($"ArrayList: {(DateTime.Now - startTime).TotalMilliseconds} мс");
 
// Тест List<T>
startTime = DateTime.Now;
List<int> list = new List<int>();
for (int i = 0; i < iterations; i++)
{
    list.Add(i);  // Нет boxing
}
for (int i = 0; i < iterations; i++)
{
    int x = list[i];  // Нет unboxing и приведения
}
Console.WriteLine($"List<int>: {(DateTime.Now - startTime).TotalMilliseconds} мс");

// Массив с фиксированным размером
int[] array = new int[5];
// array[5] = 6;  // Ошибка: выход за границы массива
 
// Динамический список
List<int> list = new List<int>();
for (int i = 0; i < 100; i++)
{
    list.Add(i);  // Автоматическое расширение емкости
}

List<int> list = new List<int>(10);  // Начальная емкость 10
Console.WriteLine($"Capacity: {list.Capacity}, Count: {list.Count}");
 
for (int i = 0; i < 11; i++)
{
    list.Add(i);
    // На 11-м элементе емкость увеличится примерно вдвое
}
Console.WriteLine($"Capacity: {list.Capacity}, Count: {list.Count}");

ArrayList arrayList = new ArrayList();
arrayList.Add(1);
arrayList.Add(2);
arrayList.Add(3);
// arrayList.Add("четыре"); // Это вызовет проблемы при преобразовании
 
// Вариант 1: Явное преобразование каждого элемента
List<int> list1 = new List<int>();
foreach (object item in arrayList)
{
    list1.Add((int)item);
}
 
// Вариант 2: Использование LINQ
List<int> list2 = arrayList.Cast<int>().ToList();

List<int> list = new List<int> { 1, 2, 3, 4, 5 };
 
// Преобразование List<int> в ArrayList
ArrayList arrayList = new ArrayList(list);

public abstract class Item { }
public class IntItem : Item { public int Value; }
public class StringItem : Item { public string Value; }
 
// Теперь можно использовать типизированную коллекцию
List<Item> itemsList = new List<Item>();
itemsList.Add(new IntItem { Value = 42 });
itemsList.Add(new StringItem { Value = "текст" });

// Измерение использования памяти
using System.Diagnostics;
 
var process = Process.GetCurrentProcess();
long memoryBefore = process.PrivateMemorySize64;
 
// Создание коллекции
const int count = 10000000;
 
// Для ArrayList (с boxing)
ArrayList arrayList = new ArrayList();
for (int i = 0; i < count; i++)
{
    arrayList.Add(i);
}
 
long memoryAfterArrayList = process.PrivateMemorySize64;
long arrayListMemory = memoryAfterArrayList - memoryBefore;
 
// Очистка
arrayList = null;
GC.Collect();
GC.WaitForPendingFinalizers();
 
// Для List<T> (без boxing)
memoryBefore = process.PrivateMemorySize64;
List<int> list = new List<int>();
for (int i = 0; i < count; i++)
{
    list.Add(i);
}
 
long memoryAfterList = process.PrivateMemorySize64;
long listMemory = memoryAfterList - memoryBefore;
 
Console.WriteLine($"Приблизительное использование памяти ArrayList: {arrayListMemory / 1024 / 1024} МБ");
Console.WriteLine($"Приблизительное использование памяти List<int>: {listMemory / 1024 / 1024} МБ");

// Метод, ожидающий необобщенный интерфейс (старый API)
public void ProcessItems(IList items) 
{
    foreach (object item in items)
    {
        // Обработка элементов с необходимостью проверки и приведения типов
    }
}
 
// Современный метод с обобщенным интерфейсом
public void ProcessItems<T>(IList<T> items) 
{
    foreach (T item in items)
    {
        // Безопасная обработка элементов без приведения типов
    }
}

// Создание словаря "сотрудник -> зарплата"
Dictionary<string, decimal> salaries = new Dictionary<string, decimal>
{
    {"Иванов", 50000m},
    {"Петров", 55000m},
    {"Сидоров", 60000m}
};
 
// Доступ по ключу
decimal ivanovSalary = salaries["Иванов"]; // 50000
 
// Безопасный доступ с проверкой
if (salaries.TryGetValue("Козлов", out decimal salary))
{
    Console.WriteLine($"Зарплата Козлова: {salary}");
}
else
{
    Console.WriteLine("Сотрудник не найден");
}

public class Employee
{
    public string Name { get; set; }
    public int Id { get; set; }
 
    // Ключевой момент: переопределение GetHashCode и Equals
    public override int GetHashCode()
    {
        return Id.GetHashCode();
    }
 
    public override bool Equals(object obj)
    {
        if (obj is Employee other)
            return Id == other.Id;
        return false;
    }
}
 
// Теперь можно использовать как ключ
Dictionary<Employee, decimal> employeeSalaries = new Dictionary<Employee, decimal>();

HashSet<string> uniqueNames = new HashSet<string>();
uniqueNames.Add("Алексей");
uniqueNames.Add("Борис");
uniqueNames.Add("Алексей"); // Дубликат будет проигнорирован
 
Console.WriteLine(uniqueNames.Count); // 2, не 3
Console.WriteLine(uniqueNames.Contains("Борис")); // true, быстрый поиск

HashSet<int> set1 = new HashSet<int> { 1, 2, 3, 4, 5 };
HashSet<int> set2 = new HashSet<int> { 4, 5, 6, 7, 8 };
 
// Объединение множеств
set1.UnionWith(set2);
// set1 теперь содержит {1, 2, 3, 4, 5, 6, 7, 8}
 
// Пересечение множеств
set1 = new HashSet<int> { 1, 2, 3, 4, 5 };
set1.IntersectWith(set2);
// set1 теперь содержит {4, 5}
 
// Разность множеств
set1 = new HashSet<int> { 1, 2, 3, 4, 5 };
set1.ExceptWith(set2);
// set1 теперь содержит {1, 2, 3}

Queue<string> printQueue = new Queue<string>();
printQueue.Enqueue("Документ1.pdf");
printQueue.Enqueue("Отчет.docx");
printQueue.Enqueue("Фото.jpg");
 
while (printQueue.Count > 0)
{
    string currentDocument = printQueue.Dequeue();
    Console.WriteLine($"Печать: {currentDocument}");
}
// Вывод будет в том же порядке, в котором добавляли

Stack<string> history = new Stack<string>();
history.Push("Главная");
history.Push("Каталог");
history.Push("Товар");
 
// Имитация нажатия кнопки "Назад" в браузере
while (history.Count > 0)
{
    string currentPage = history.Pop();
    Console.WriteLine($"Переход на: {currentPage}");
}
// Вывод будет в обратном порядке: Товар, Каталог, Главная

// Потокобезопасный словарь
ConcurrentDictionary<string, int> concurrentDict = new ConcurrentDictionary<string, int>();
 
// Параллельное заполнение
Parallel.For(0, 1000, i =>
{
    string key = $"key-{i}";
    concurrentDict.TryAdd(key, i);
});
 
// Атомарное обновление
concurrentDict.AddOrUpdate("counter", 1, (key, oldValue) => oldValue + 1);

using System.Collections.Immutable;
 
// Создание неизменяемого списка
ImmutableList<int> immutableList = ImmutableList.Create<int>(1, 2, 3);
 
// Операции не изменяют оригинал, а создают новый экземпляр
ImmutableList<int> newList = immutableList.Add(4);
 
Console.WriteLine(string.Join(", ", immutableList)); // 1, 2, 3
Console.WriteLine(string.Join(", ", newList));       // 1, 2, 3, 4

// Упрощенный взгляд на внутреннее устройство List<T>
public class SimpleList<T>
{
    private T[] _items;
    private int _size;
    private const int DefaultCapacity = 4;
 
    public SimpleList()
    {
        _items = new T[DefaultCapacity];
    }
 
    public void Add(T item)
    {
        if (_size == _items.Length)
            Resize();
        
        _items[_size++] = item;
    }
 
    private void Resize()
    {
        T[] newArray = new T[_items.Length * 2];
        Array.Copy(_items, newArray, _items.Length);
        _items = newArray;
    }
}

// Вместо этого
List<string> names = new List<string>();
for (int i = 0; i < 10000; i++)
    names.Add($"Name{i}");
 
// Делайте так
List<string> optimizedNames = new List<string>(10000);
for (int i = 0; i < 10000; i++)
    optimizedNames.Add($"Name{i}");

// Неоптимально - множество временных коллекций
var result = collection
    .Where(x => x > 10)
    .OrderBy(x => x)
    .Select(x => x * 2)
    .ToList();
 
// Лучше - одно перечисление, одна результирующая коллекция
var betterResult = collection
    .Where(x => x > 10)
    .OrderBy(x => x)
    .Select(x => x * 2)
    .ToList();

// Вместо
if (dictionary.ContainsKey(key))
{
    var value = dictionary[key];
    // Используем value
}
 
// Используйте
if (dictionary.TryGetValue(key, out var value))
{
    // Используем value
}

public class LruCache<TKey, TValue>
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<CacheItem>> _cacheMap;
    private readonly LinkedList<CacheItem> _cacheList;
 
    public LruCache(int capacity)
    {
        _capacity = capacity;
        _cacheMap = new Dictionary<TKey, LinkedListNode<CacheItem>>(capacity);
        _cacheList = new LinkedList<CacheItem>();
    }
 
    public TValue Get(TKey key)
    {
        if (!_cacheMap.TryGetValue(key, out var node))
            throw new KeyNotFoundException();
        
        // Перемещаем в начало списка (недавно использованный)
        _cacheList.Remove(node);
        _cacheList.AddFirst(node);
        
        return node.Value.Value;
    }
 
    public void Put(TKey key, TValue value)
    {
        if (_cacheMap.TryGetValue(key, out var existingNode))
        {
            // Обновляем существующий элемент
            _cacheList.Remove(existingNode);
            _cacheMap.Remove(key);
        }
        else if (_cacheMap.Count >= _capacity)
        {
            // Удаляем наименее используемый элемент
            var last = _cacheList.Last;
            _cacheMap.Remove(last.Value.Key);
            _cacheList.RemoveLast();
        }
        
        // Добавляем новый элемент в начало
        var cacheItem = new CacheItem(key, value);
        var newNode = _cacheList.AddFirst(cacheItem);
        _cacheMap.Add(key, newNode);
    }
 
    private class CacheItem
    {
        public TKey Key { get; }
        public TValue Value { get; }
 
        public CacheItem(TKey key, TValue value)
        {
            Key = key;
            Value = value;
        }
    }
}

// Гибкий метод, работает с любым источником элементов
public static int CountPositive(IEnumerable<int> numbers)
{
    return numbers.Count(n => n > 0);
}
 
// Ограниченный метод, работает только со списками
public static int CountPositiveRestricted(List<int> numbers)
{
    return numbers.Count(n => n > 0);
}

public static List<T> FindDuplicates<T>(T[] array)
{
    var seen = new HashSet<T>();
    var duplicates = new List<T>();
    
    foreach (var item in array)
    {
        if (!seen.Add(item)) // Add возвращает false, если элемент уже присутствует
            duplicates.Add(item);
    }
    
    return duplicates;
}
 
// Использование
int[] numbers = { 1, 2, 3, 1, 4, 3, 5 };
var dupes = FindDuplicates(numbers);
Console.WriteLine(string.Join(", ", dupes)); // Выведет: 1, 3

public static IEnumerable<T> MergeUnique<T>(params IEnumerable<T>[] collections)
{
    var uniqueItems = new HashSet<T>();
    
    foreach (var collection in collections)
    {
        foreach (var item in collection)
        {
            uniqueItems.Add(item);
        }
    }
    
    return uniqueItems;
}
 
// Использование
var list1 = new List<int> { 1, 2, 3 };
var list2 = new List<int> { 2, 3, 4, 5 };
var list3 = new List<int> { 3, 5, 6 };
 
var merged = MergeUnique(list1, list2, list3);
Console.WriteLine(string.Join(", ", merged)); // Выведет: 1, 2, 3, 4, 5, 6

public static IEnumerable<T> MergeUniqueLinq<T>(params IEnumerable<T>[] collections)
{
    return collections.SelectMany(x => x).Distinct();
}

public class FifoCache<TKey, TValue>
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, TValue> _cache;
    private readonly Queue<TKey> _keyQueue;
    
    public FifoCache(int capacity)
    {
        _capacity = capacity > 0 ? capacity : throw new ArgumentException("Емкость должна быть положительной");
        _cache = new Dictionary<TKey, TValue>(capacity);
        _keyQueue = new Queue<TKey>(capacity);
    }
    
    public void Add(TKey key, TValue value)
    {
        if (_cache.ContainsKey(key))
        {
            _cache[key] = value; // Обновляем существующее значение
            return;
        }
        
        // Если кэш полон, удаляем самый старый элемент
        if (_cache.Count >= _capacity)
        {
            var oldestKey = _keyQueue.Dequeue();
            _cache.Remove(oldestKey);
        }
        
        _cache.Add(key, value);
        _keyQueue.Enqueue(key);
    }
    
    public bool TryGetValue(TKey key, out TValue value)
    {
        return _cache.TryGetValue(key, out value);
    }
}

var cache = new FifoCache<string, int>(3);
cache.Add("один", 1);
cache.Add("два", 2);
cache.Add("три", 3);
cache.Add("четыре", 4); // "один" будет удален
 
if (cache.TryGetValue("один", out var value))
    Console.WriteLine($"один: {value}");
else
    Console.WriteLine("Ключ 'один' не найден"); // Это сработает

public static Dictionary<T, int> CountFrequency<T>(IEnumerable<T> items)
{
    var frequency = new Dictionary<T, int>();
    
    foreach (var item in items)
    {
        if (frequency.ContainsKey(item))
            frequency[item]++;
        else
            frequency[item] = 1;
    }
    
    return frequency;
}

public static Dictionary<T, int> CountFrequency<T>(IEnumerable<T> items)
{
    var frequency = new Dictionary<T, int>();
    
    foreach (var item in items)
    {
        if (!frequency.TryGetValue(item, out int count))
            count = 0;
            
        frequency[item] = count + 1;
    }
    
    return frequency;
}

string[] fruits = { "яблоко", "банан", "апельсин", "яблоко", "апельсин" };
var fruitCounts = CountFrequency(fruits);
 
foreach (var pair in fruitCounts)
    Console.WriteLine($"{pair.Key}: {pair.Value}");

public class MovingAverage
{
    private readonly int _windowSize;
    private readonly Queue<double> _window;
    private double _sum;
    
    public MovingAverage(int windowSize)
    {
        _windowSize = windowSize > 0 ? windowSize : throw new ArgumentException("Размер окна должен быть положительным");
        _window = new Queue<double>(windowSize);
        _sum = 0;
    }
    
    public double Next(double val)
    {
        _sum += val;
        _window.Enqueue(val);
        
        // Если размер окна превышен, удаляем самое старое значение
        if (_window.Count > _windowSize)
        {
            _sum -= _window.Dequeue();
        }
        
        return _sum / _window.Count;
    }
}

var ma = new MovingAverage(3);
Console.WriteLine(ma.Next(1)); // 1
Console.WriteLine(ma.Next(2)); // 1.5
Console.WriteLine(ma.Next(3)); // 2
Console.WriteLine(ma.Next(4)); // 3 (скользящее среднее 2, 3, 4)

// Код с ошибкой
var numbers = new List<int> { 1, 2, 3, 4, 5 };
foreach (var number in numbers)
{
    if (number % 2 == 0)
        numbers.Remove(number); // Выбросит исключение
}
 
// Правильный подход
var numbers = new List<int> { 1, 2, 3, 4, 5 };
var numbersToRemove = numbers.Where(n => n % 2 == 0).ToList();
foreach (var number in numbersToRemove)
{
    numbers.Remove(number);
}

// Небезопасный код
Dictionary<string, int> counters = new Dictionary<string, int>();
Parallel.ForEach(items, item =>
{
    if (counters.ContainsKey(item))
        counters[item]++;
    else
        counters[item] = 1;
});
 
// Безопасный код с ConcurrentDictionary
ConcurrentDictionary<string, int> concurrentCounters = new ConcurrentDictionary<string, int>();
Parallel.ForEach(items, item =>
{
    concurrentCounters.AddOrUpdate(
        item,             // ключ
        1,                // значение если ключ новый
        (key, oldValue) => oldValue + 1  // функция обновления существующего значения
    );
});

// Без предварительного выделения памяти
var list1 = new List<int>();
for (int i = 0; i < 10000; i++)
    list1.Add(i);  // Может вызвать несколько перераспределений
 
// С предварительным выделением
var list2 = new List<int>(10000);  // Сразу выделяем необходимую емкость
for (int i = 0; i < 10000; i++)
    list2.Add(i);  // Не будет перераспределений

// Пример потоковой обработки большого файла без загрузки всего в память
using (var reader = new StreamReader("hugeDataFile.txt"))
{
    string line;
    while ((line = reader.ReadLine()) != null)
    {
        // Обработка только одной строки за раз
        ProcessLine(line);
    }
}