Подборка тем для повторения по алгоритмам и структурам данных

Подборка тем для повторения по алгоритмам и структурам данных

Структуры данных

1. Linked List
2. Skip List
3. Бинарное дерево, алгоритмы балансировки
4. Hashtable
5. Куча
6. Графы

Алгоритмы

1. Динамическое программирование
2. BIT Manipulation
3. Сортировка: quick sort, merge sort, heap sort, radix sort
4. Алгоритмы на графах
1. Остовное дерево‎
2. Алгоритм Прима
3. Алгоритм Флойда — Уоршелла
4. Алгоритм поиска A*
5. Топологическая сортировка
6. BFS
7. DFS
8. Поиск максимального потока
5. *

Небольшая шпаргалка по алгоритмам от Robert Sedgewick:

Математика для программиста

Какие разделы математики желательно знать хорошему программисту:

1. Комбинаторика (сочетания, перестановки, биномиальные коэффициенты, целочисленные последовательности, основы теории графов)
2. Теория вероятностей (зависимые и независимые события, условные вероятности, формула полной вероятности, математическое ожидание)
3. Математическая логика (отображения и отношения, эквивалентность, отношения порядка, логика высказываний, кванторы, метод математической индукции)
4. Алгебра и теория чисел (группы, факторизация, идеал, алгоритм Евклида, теоремы Эйлера и Ферма, кольцо многочленов, линейные пространства и операторы, базис, размерность, ранг)
5. Математический анализ (предел, обозначения O( ) и o( ), умение корректно доказывать и применять асимптотические оценки, непрерывность, производная, первообразная, определенный интеграл, нахождение экстремума функции, формула Тейлора)

Отладка сборок .Net framework

Процесс настройки Visual Studio 2013 для отладки сборок .Net framework хорошо описан здесь Configure Visual Studio 2013 for debugging .NET framework.

Почему это может не работать и как можно попробовать побороть проблему обсуждалось на stackoverflow здесь. В данной ветке в конечном счете пришли к тому, что некоторые security updates для windows перезаписали файлы сборок .Net framework, сделав невозможным отлаживаться в них с помощью символов, загружаемых с соответствующих серверов Microsoft.

Вопросы многопоточности

Последние пару недель читаю книгу Concurrent Programming on Windows by Joe Duffy, в которой тема многопоточности раскрыта на очень глубоком уровне. Особенно мне показались интересными главы "Windows Kernel Synchronization" и "Control and Data Synchronization", в которых описываются всевозможные средства синхронизации в Windows вцелом и в .Net в частности. Так, например, я не знал, что за Monitor.Wait и Monitor.Pulse стоят condition variables, и как они работают.
Далее я составил план изучения темы многопоточности и синхронизации в Windows.
Если у вас есть хорошее понимание по каждому пункту, то наверное вместо книжки Джо Даффи можно почитать что-нибудь другое.

1. Модели ассинхронного программирования
2. Как работает Monitor
3. Monitor.Wait, Monitor.Pulse, Condition variables, написание блокирующей очереди с использованием методов класса Monitor
4. Ключевое слово volatile, какие проблемы позволяет решить, MemoryBarrier, VolatileRead, VolatileWrite
5. ManualResetEvent, AutoResetEvent, чем отличаются, по какому принципу выбираются потоки для пробуждения при переводе евента в сигнальное состояние
6. Семафоры vs Мьютексы
7. ReadWriteLockSlim и три режима работы
8. Многопоточность и GUI
9. Что такое Livelock
10. Что такое Deadlock, какие существуют подходы для устранения дэдлоков: порядок захвата и освобождения ресурсов, создание метода для поиска подходящего ресурса по id, захват ресурса с таймаутом, подход с использованием WaitHandle.WaitAll
11. Lock-free programming
12. TLS, Dynamic and Static thread local storage

Что нужно помнить про работу Garbage Collector в .Net

На прошлой неделе я решил освежить в памяти то, как устроена сборка мусора в .Net Framework. Эта животрепещущая тема однозначно стоит того, чтобы потратить некоторое время для ее углубленного изучения. Кроме того, стоит отметить, что практически ни одно интервью на позицию .Net developer сегодня не обходится без вопросов по Garbage Collector.

После прочтения нескольких книг и статей решил написать список вопросов на тему Garbage Collector, по которым можно будет в дальнейшем освежать в памяти аспекты его работы. Если вы не смогли разобраться по любому из пунктов, пишите в комментариях, будем разбираться вместе.

1. Алгоритм работы Garbage Collector
2. Как определяется, где будет размещен в памяти вновь создаваемый объект?
3. В каких случаях запускается сборка мусора
4. Какие объекты классифицируются как roots
5. LOH. Фрагментация памяти. Когда объекты попадают в LOH? Когда массив double попадают в LOH?
6. Поколения
7. Finalization list и freachable queue
8. Resurrection
9. Dispoze pattern
10. GC.SuppressFinalize
11. GC.ReRegisterForFinalize
12. GC.WaitForPendingFinalizers
13. Параметры в app.config: gcServer и gcConcurrent. Сколько в серверном режиме выделяется куч и как изменяются лимиты поколений. GC LatencyMode
14. CriticalFinalizerObject class
15. SafeHandle Class
16. WeakReference: short and long
17. GC.RegisterForFullGCNotification
18. Card Table
19. GCHandle, Pinned, fixed

Вопросы для интервью .Net developer

Моя личная подборка вопросов для проведения интервью на позицию .Net developer.

Общие вопросы
1. Что такое делегат? Чем отличается событие от делегата? Что можно включить в интерфейс (делегат, событие)? Можно ли вызвать эвент из другого класса? Почему нет?
2. Что из себя представляет лямбда функция?
3. Какие средства синхронизации потоков в .Net вам известно? Что такое Monitor? (какие методы кроме Enter и Exit там есть).
4. Что такое замыкание в .Net?
5. Что такое volatile?
6. Что такое кластерный и не кластерный индекс?

Топ 10 книг для .Net разработчика

Составил список книг по программированию, которые однозначно стоит прочитать.

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

Примерно по той же причине здесь отсутствует упоминания томов Кнута. Конечно, если вы работаете алгоритмистом, то без Кнута вам не обойтись, но если вы не занимаетесь непосредственно разработкой алгоритмов, то на мой взгляд вполне достаточно прочтения Скиены, Кормена и прохождению курсов по алгоритмам на курсере.

Итак, хорошие книжки по программированию:

1. Чистый код. Роберт Мартин 
   
2. Рефакторинг. Улучшение существующего кода. Мартин Фаулер
   
3. Шаблоны корпоративных приложений. Мартин Фаулер
   
4. Паттерны проектирования. Фримен
   
5. CLR via C#. Джеффри Рихтер
   
6. Concurrent Programming on Windows. Joe Duffy
   
7. Under the Hood of .NET Memory Management. Chris Farrell
   
8. Эффективное использование С++. Скотт Мэйерс
   
9. The Art of Unit Testing. Roy Osherove
   
10. Алгоритмы. Руководство по разработке. Скиена