Рубрика «рекурсия»

Анализ задачи с собеседования в Google: конь и телефонные кнопки - 1


Для начала я должен заявить: хотя собеседование кандидатов — это одна из моих профессиональных обязанностей, в этой статье представлены лишь личные наблюдения, истории и мнения. Они ни в коем случае не являются официальными заявлениями Google, Alphabet или любых других лиц или организаций.

Это была первая задача, которую я использовал в своей карьере собеседующего, она же первая утекла и была запрещена к использованию. Мне она нравится потому, что обладает очень приятными свойствами:

  • Её легко сформулировать и понять.
  • У неё есть множество решений, каждое из которых требует разной степени знаний алгоритмов и структур данных. Кроме того, здесь важны логические рассуждения.
  • Каждое решение можно реализовать в относительно малом объёме кода, поэтому она идеальна для ограниченных по времени собеседований.

Если вы студент или ищете работу в технологической сфере, то, надеюсь, после прочтения статьи вы будете лучше понимать, чего ожидать от задач на собеседованиях. Если же вы проводите собеседования, то мне бы хотелось поделиться своим мыслительным процессом и стилистическим подходом к собеседованиям.Читать полностью »

Несколько алгоритмов на трех языках программирования

Возьмём несколько простых задач и посмотрим, как с ними справляются якобы умерший lisp и современные python и ruby. Сравнивать будем скорость работы, а также компактность и читаемость кода. Тестируем на компьютере с процессором Intel Core i3 2.93 GHz и памятью 14 ГБ. Используем интерпретаторы Lisp SBCL 2.3.2,  Python 3.12.4, Ruby 3.3.3. Автор сразу  хочет заметить: он не пытался придумать или найти самые эффективные алгоритмы; целью являлось именно сравнение работы одинаковых алгоритмов на разных языках. Вот что получилось.

Действительные числа

Читать полностью »

В прошлый раз мы рассмотрели использование рекурсии на примере возведения в степень. В этот раз мы применим рекурсию для создания алгоритма сортировки слиянием.

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

Освежим в памяти суть сортировки слиянием:

Изначальный массив делится пополам до тех пор, пока длина "половинок" не станет равна 1Читать полностью »

Рафаэль Санти - фреска "Афинская школа"
Рафаэль Санти - фреска "Афинская школа"

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

Читать полностью »

SQL HowTo: решаем головоломку «Небоскрёбы» почти без перебора - 1

Многие знают правила этой головоломки (Skyscrapers):

Перед вами вид сверху на городской квартал. В каждой клетке стоит "небоскреб" высотой, равной числу в этой клетке. Числа с боков сетки означают количество "небоскребов", видимых из соответствующей строки или столбца, если смотреть от этого числа.

Читать полностью »

Бог — это вечная и бесконечная истина, не имеющая ценности и смысла.

Барух Бенедикт Спиноза

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

Все есть бит - 1

В поисках «теории всего»

Начиная с середины 20-ого века самой сложной и перспективной задачей теоретической физики является поиск так называемой «теории всего», которая объединит в себе общую теорию относительности и квантовую механику, тем самым дав точное объяснение всем наблюдаемым физическим явлениям. На роль такой теории претендуют многочисленные теории струн, теория квантовой петлевой гравитации и многие другие. Но мы будем говорить не о них. Мы сделаем шаг еще дальше.
Читать полностью »

В настоящей статье предложен разработанный автором метод нечеткой индукции как объединение положений нечеткой математики и теории фракталов, введено понятие степени рекурсии нечеткого множества, представлено описание неполной рекурсии множества как его дробной размерности для моделирования предметной области. В качестве сферы применения предлагаемого метода и созданных на его основе моделей знаний как нечетких множеств рассмотрено управление жизненным циклом информационных систем, включая разработку сценариев использования и тестирования программного обеспечения. Читать полностью »

Полгода назад Крис Пеннер опубликовал Beating C With 80 Lines Of Haskell: Wc. В предисловии говорится:

Задача состоит в том, чтобы построить более шустрый клон оптимизированной вручную реализации утилиты wc на C в нашем любимом высокоуровневом языке программирования со сборкой мусора — на Haskell! Звучит достаточно просто, не так ли?

Крис прошел весь путь от простой реализации при помощи ByteStrings, через моноиды, встроенные моноиды и, наконец, пришел к параллельной многоядерной версии вышеописанного, которой и удалось немного побить чистый C-код во время выполнения на четырех ядрах.

Несколько дней назад на Хабре была размещена еще одна заметка на ту же тему от 0xd34df00d Побеждая C двадцатью строками Haskell: пишем свой wc. Автор доказал возможность пользования идиоматического хаскеля и в 20 (двадцати) строках кода реализовал алгоритм, который почти в десять раз быстрее, чем идиоматическая реализация на C.

Читать полностью »

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

Наиболее «жизненный» пример — вывести 20 самых старых задач, числящихся на списке сотрудников (например, в рамках одного подразделения). Для различных управленческих «дашбордов» с краткими выжимками по участкам работы похожая тема требуется достаточно часто.

SQL HowTo: пишем while-цикл прямо в запросе, или «Элементарная трехходовка» - 1

В статье рассмотрим реализацию на PostgreSQL «наивного» варианта решения такой задачи, «поумнее» и совсем сложный алгоритм «цикла» на SQL с условием выхода от найденных данных, который может быть полезен как для общего развития, так и для применения в других похожих случаях.
Читать полностью »

Рисуем морозные узоры на SQL - 1

Немного SQL-магии под катом: математика, рекурсия, псевдографика.

Вспоминаем под Новый год формулу угла между векторами:
Рисуем морозные узоры на SQL - 2
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js