Подходит ли Ruby для структур данных и алгоритмов?
Да, для обучения и для собеседований в компаниях, которые пишут на Rails: код такой же короткий, как на Python, а благодаря блокам обходы читаются как сам алгоритм. Стоит знать о двух слабых местах. В стандартной библиотеке нет кучи, очереди с приоритетом, связного списка и дерева, так что их вы пишете сами; а Array#sort не обещает устойчивости, поэтому, когда равные элементы должны сохранить порядок, сортируйте по паре: sort_by.with_index { |x, i| [x, i] }.
Какие классы Ruby каким структурам данных соответствуют?
Array представляет собой динамический массив, который служит стеком (push, pop) и очередью (push, shift); Hash является хеш-таблицей, которая помнит порядок вставки; а Set из стандартной библиотеки представляет собой множество на основе хеш-таблицы. Вот и весь список. Кучи, очереди с приоритетом, связного списка, дерева, префиксного дерева и графа нет, так что их вы пишете сами, на первом и втором шагах.
Как написать очередь с приоритетом на Ruby?
В Ruby её так и не добавили, поэтому честных ответов три: сортировать массив после каждой вставки, O(n log n) на добавление; поддерживать его отсортированным с помощью bsearch_index и insert, O(n) на добавление; или написать двоичную кучу на Array, O(log n) и на добавление, и на извлечение. Именно третий вариант ждёт интервьюер, и его вы пишете на втором шаге.
Почему порядок вставки в Hash Ruby важен для алгоритмов?
Потому что он превращает некоторые классические конструкции в несколько строк. LRU-кэш, любимая задача собеседований, представляет собой Hash, в котором чтение удаляет ключ и вставляет его заново, чтобы переместить в конец, а вытеснение выполняет shift, который удаляет самую старую запись. В большинстве языков для этого нужны хеш-таблица и двусвязный список, то есть структуры, которые вы пишете на первом и втором шагах, так что вы сможете объяснить, что Ruby делает за вас.
Какие курсы этого пути не преподаются на Ruby?
Три: динамическое программирование и серия по интервью на Python преподаются на Python, а битовые операции на C++. Они перечислены после шагов, каждый со ссылкой, которая открывает курс на его собственном языке. Таблицей мемоизации в Ruby может служить Hash с блоком по умолчанию, как в Hash.new { |h, n| h[n] = n < 2 ? n : h[n - 1] + h[n - 2] }, а n[i] напрямую читает бит i целого числа там, где в C++ пишут (n >> i) & 1.
Нужно ли знать Ruby, прежде чем начинать этот путь?
Как минимум методы, блоки, массивы, хеши и классы. Если это для вас новое, курс Ruby от Coddy сначала бесплатно доведёт вас до этого уровня, а этот путь начинается там, где он заканчивается.
