Практические задачи на C#
Практическая задачка на собеседовании редко проверяет знание хитрого алгоритма. Она проверяет базовые рефлексы: умеете ли вы пройти массив, не промахнувшись на единицу; понимаете ли, почему конкатенация строк в цикле квадратична; замечаете ли, что HashSet превращает поиск за O(n) в поиск за O(1). Ошибки здесь стоят дёшево на бумаге, но именно они отличают уверенный код от «вроде работает».
Эта тема — набор повторяющихся приёмов, из которых складывается большинство простых задач: как обходить массив, как работать со строкой, когда брать рекурсию, а когда итерацию, чем помогает хеширование и что значит «на месте». Каждый слой ниже разбирает один приём на маленьком примере с явной оценкой сложности.
Карта темы
- Обход массивов — индексный цикл, ошибка на единицу, встречные указатели.
- Работа со строками —
stringнеизменяем,char.IsLetter/ToLower, проверка на палиндром двумя указателями. - Рекурсия — базовый случай, шаг, факториал и ловушка переполнения.
- Итеративные алгоритмы — свёртка рекурсии в цикл, скользящая пара, Фибоначчи за O(1) памяти.
- Хеширование —
HashSet/Dictionaryдля поиска за O(1), удаление дубликатов за один проход. - Алгоритмы на месте — O(1) дополнительной памяти, разворот и обмен без временной переменной.
Частые ошибки и ловушки
| Ошибка | Последствие |
|---|---|
| Ошибка на единицу в границах цикла | Пропущенный или лишний элемент, IndexOutOfRangeException на Length |
| Разворот массива до самого конца | Каждая пара переставляется дважды — массив возвращается к исходному виду |
Конкатенация + в цикле для строки | O(n²) работы и поток одноразовых строк для GC вместо O(n) со StringBuilder |
Базовый случай факториала возвращает 0 | Всё произведение обнуляется — n! всегда 0 |
Считать, что long не переполняется | 21! уже переполняет long тихо — без checked ошибка проходит незамеченной |
| Наивная двойная рекурсия для Фибоначчи | Экспоненциальные O(2ⁿ) вместо O(n): одни и те же значения пересчитываются |
| Вложенный цикл для поиска дубликатов | O(n²) там, где HashSet даёт O(n) с проверкой за O(1) |
| XOR- или арифметический обмен | Обнуляет элемент при i == j, а арифметика ещё и переполняет int |
Значение для собеседований
Такие задачи почти всегда идут в начале собеседования как разминка и фильтр: важен не «правильный ответ», а то, как вы рассуждаете о границах, сложности и памяти. Кандидат, который вслух проговаривает инвариант цикла и оценку O(·), проходит их спокойно; тот, кто пишет наугад, спотыкается на пустом входе или i == j.
Что обычно проверяют:
- Аккуратный обход массива без ошибки на единицу и корректная обработка пустого/одноэлементного входа.
- Понимание неизменяемости
stringи стоимости конкатенации. - Верный базовый случай рекурсии и осознание переполнения.
- Умение переписать рекурсию в итерацию с O(1) памяти.
- Когда
HashSet/Dictionaryснимают квадратичную сложность. - Разницу между «на месте» (O(1)) и решением с дополнительной памятью.
Типичный неверный ответ: свести всё к одной строке через LINQ (s.Reverse(), set.ToArray()) и заявить O(1). Это открывает разговор о реальной стоимости — скрытых аллокациях, потерянном порядке и о том, чем требование «на месте» отличается от «в одну строку».