Решение нескольких алгоритмических задачек на daScript
.
Задачки со старого собеса Nokia на C++ программиста (уже закрыли офис в России), разбор
Вычислить первые N простых чисел
.. и вернуть результат в качестве массива.
https://github.com/spiiin/dascript_trivial_examples/blob/main/primes/primes.das
Тривиальная версия:
- чуть более улучшенная формула перебора чисел-кандидатов (вместо всех нечётных — t*6+/-1) + проверка границы не корнем, а квадратом.
- не совсем понял, как хочет применить решето Эратосфена в варианте на C++ сама st_1ena, если нужны первые N простых чисел, а не “все числа меньшие N”, то возникает подзадача оценить минимальное натуральное число, меньше которого точно окажутся N простых чисел, что также нетривиально, или построить ленивых фильтров, что совсем нетривиально на C++, и требует оценки памяти под эти фильтры.
- вместо этого, версия решения, которая может вычислить первые N чисел в compile-time — в предположении, что у нас есть некоторое количество памяти, для сохранения решета эратосфена, эффективнее тогда потратить всю эту память на хранение предпросчитанных первых значений, и начинать рассчёт только сверх этих предпросчитанных чисел. На языках с макросами — предпросчёт в compile-time выполняется той же функцией, что в run-time, т.е. не требует написания дополнительного кода.
Версия, которая сохраняет первый числа в кеш (макрос [cached_primes (count=200)] - с параметром, сколько чисел будет предпросчитано заранее)
Посчитать статистику слов в тексте по длине слова
Задача на то, чтобы найти в стандартной библиотеке языка нужные функциии
Решение в лоб - прочитать файл построчно, разбить на символы split_by_chars
, обновляя в словаре значения количество слов. Дальше переложить значение в список пар, который отсортировать по первому элементу, и вывести на экран.
- Можно упороться по тому, чтобы выяснять у интервьюера, какие допустимы кодировки, разделители или что есть слова, как кажется подразумевали авторы задачи, которые потом расстроились, что ни один кандидат не учёл все возможные кейсы.
- Можно сохранять данные не в словаре, а сразу в списке пар
(длина слова, частота)
, не так то и много возможных длин слов. Сортировка такого списка пар в daScript - либо с помощью явной передачи функции сортировки, либо определением оператора < для своего типа.
Удалить из односвязного списка каждый пятый элемент
Интересно посмотреть на разницу в работе с памятью между C++ и daScript
- Раз мы “играем в C++”, то попробуем при удалении элемента из списка сразу же звать финализатор для него. Финализатор по умолчанию рекурсивно зовёт финализаторы для всех полей структуры. Это поведение можно изменить, если переопределить функцию
finalize
, или если пометить поле атрибутом[[do_not_delete]]
(так как мы вручную измененяем указатели при удалении элемента, то элемент списка не отвечает за удаление следующего элемента по ссылке next). - С помощью
options persistent_heap = true
, можно настроить также освобождение памяти после вызова финализатора (иначе за освобождение памяти отвечает хост-программа, один из паттернов быстрой работы с памятью — грохнуть всю выделенную в цикле работы скрипта память разом).
Вывести максимальное число, составленное из единиц двоичного представления заданного числа
Тоже без заморочек, в лоб.
В продакшен-варианте, если нужно действительно быстро, решение прокидывается в C++, где задействуются всевозможные интринсики компилятора для того, чтобы получать кол-во битов так, как умеет процессор, или другие трюки для минимизации количества инструкций (развернуть циклы, и наложить кучу масок — Hamming weight).
Вывести список всех самых длинных путей в дереве
Туповатое решение, с кучей лишних копирований путей.
Можно оптимайзить. Либо по памяти, разделив обход на 2 — сначала найти максимальную глубину, затем собрать только самые длинные пути. Либо в один проход, но сохраняя не полные копии путей, а альтернативное дерево с записью глубины каждой ветви рядом с указателем на оригинальные ноды left и right, по которому можно будет восстановить пути + обновляя максимальное значение глубины каждую итерацию.