Connect with us

Программирование

10 сайтов с задачами и соревнованиями для программистов 2018

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

Леонид Боголюбов

Опубликовано

/

     
     

1. Coderbyte

Сложность: начинающие – среднего уровня

Задачи и туториалы по JavaScript, Python, Ruby, PHP, Java, Swift, Go, C++, C# и C. Плюс подготовка к интервью и задачи от компаний.

2. Codewars

Сложность: начинающие – среднего уровня

Двадцать языков, онлайновое решение задач и мировой рейтинг программистов.

3. CodeFights

Сложность: начинающие – среднего уровня

Аркадное программирование, турниры, интервью, программирование с ботом или наперегонки с напарником – и все это для нескольких десятков языков.

4. CodinGame

Сложность: начинающие – среднего уровня

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

5. TopCoder

Сложность: среднего уровня – продвинутые

Алгоритмические задачи для самостоятельного решения или в соревновании с другими.

6. HackerRank

Сложность: среднего уровня – продвинутые

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

7. LeetCode

Сложность: среднего уровня – продвинутые

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

8. CodeChef

Сложность: среднего уровня – продвинутые

Индийский сайт с задачами, руководствами, соревнованиями и сообществом.

9. GeeksforGeeks

Сложность: среднего уровня – продвинутые

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

10. Codeforces

Сложность: продвинутые

Российские соревнования и олимпиады по программированию.

Комментарии
Если вы нашли опечатку - выделите ее и нажмите Ctrl + Enter! Для связи с нами вы можете использовать info@apptractor.ru.
Advertisement
Click to comment

You must be logged in to post a comment Login

Leave a Reply

Исследования

Какие эмодзи больше всего используют программисты

Эваристо Карабайо  проанализировал около 3,5 гигабайтов логов, чтобы узнать о том, какой эмодзи самый популярный у разработчиков.

AppTractor

Опубликовано

/

Автор:

Эмодзи радикально изменили способ общения в соцсетях. Существует множество исследований, в которых указывается на различия в том, как люди используют их на разных платформах. Например, списки топ-эмодзи в Instagram, Twitter или Facebook имеют некоторое сходство, но также много в чем различаются. Эти различия становятся все больше при движении дальше по списку социальных сетей.

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

В этой статье я рассматриваю то, как новые разработчики используют эмодзи, в частности, в Gitter Main Chat Room на платформе freeCodeCamp.

Есть как минимум два способа рендеринга эмодзи в Gitter:

  • с использованием псевдонимов (например, таких);
  • с использование UTF-8 путем написания эмодзи непосредственно ключевым словом или копированием/вставкой символа из онлайн-ресурса.

Оба по-разному рендерется в сообщении, причем первый визуализируется существующими изображениями Gitter, а второй показывается в соответствии с настройками вашего компьютера. Первый метод – «использования псевдонимов» – является самым популярным и будет основным предметом обсуждения.

Чтобы дать вам краткое представление о том, чем я интересовался, я хотел бы быстро осветить ответы на такие вопросы, как:

  • Есть ли явный шаблон в использовании эмодзи?
  • Каковы самые популярные эмодзи?
  • Сколько людей использует эмодзи?
  • Насколько люди разбираются в словаре эмодзи?

Поэтому давайте начнем и ответим на эти вопросы.

Поговорим об эмодзи

Проведя свой анализ чата freeCode, я узнал, что около 23% вовлеченных в разговоры в чате также были и любителями эмодзи. Я определяю слово «вовлеченный» как человека, который отправил не менее 10 сообщений. Если мы сравним вовлеченных и невовлеченных любителей эмодзи с обычными ценителями чатов, эта цифра возрастет до 45%.

Количество «эмодзионеров» в чате freeCode может показаться маленьким по сравнению с другими чатами и платформами. Однако важно отметить, что:

  • Многие пользователи чата очень скоро выходили из него.
  • Были пользователи, которые предпочли консервативное общение.
  • Некоторые пользователи могли и не знать о существовании эмодзи.

В целом, наши эмодзионеры отослали по крайней мере 753,000 эмодзи (или 600,000, если считать не общее количество эмодзи, а количество сообщений, в которых они появлялись) со средним значением 32 эмодзи для каждых 100 сообщений.

В целом, наши эмодзионеры показали коллективную грамотность, отослав около 800 самых разных эмодзи, то есть около 25% от полного списка. Я отобразил появление новых эмодзи с помощью D3.js, показав, что многие из них были впервые представлены в чате в период с июля 2015 года по июль 2016 года с темпом роста от 10 до 20 новых эмози в неделю.

В среднем один человек использовал около трех разных эмодзи. Такое число получилось потому, что были у нас и настоящие профессионалы эмодзи – так, один использовал около 500 различных эмодзи.

Нетипичные эмодзи в чате?

Чтобы лучше понять, как люди обменивались эмодзи в чате, я сравнил свои выводы с докладом, подготовленным SwiftKey в 2015 году. Эти данные немного устарели, поэтому я добавил данные unicod.org. Объединил их и вот что получилось.

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

Поскольку сравнения, основанные на категоризации высокого уровня, обычно слишком непонятные, я попробовал другое сравнение, сосредоточившись на 25 наиболее используемых эмодзи с 2015 по 2017 год, используя их подкатегории. Вместе эти 25 эмодзи составляли около 15% всех, отправленных в течение этого периода смайликов.

Список эмодзи и их подкатегорий показывает, что наши эмодзионеры все равно хорошо вписываются в типичную модель пользователя эмодзи. Широкое использование иконок категории «Позитивные лица» совпало с подкатегорией «Счастливые лица» SwiftKey.

То же самое было и с подкатегорией «Негативные лица», подобной категории «Печальные лица» SwiftKey. Немного обособленно было использование «: trollface:», которое является доступным значком в GitHub, и обычно оно связано со спам-сообщениями и вредительством, но также используется как шутка в чат-комнате freeCodeCamp. «Какашка» 💩 также была в числе 25 самых используемых эмодзи.

Наиболее часто используемые значки жестов в чате freeCodeCamp являются положительными, связанными с приветствием, поддержкой, доверием и признанием успеха. Еще одно отличие заключается в меньшем использовании значков, таких как «сердца» ♥️ или «поцелуи» 💋, что говорит о том, что поиск партнера не был главной целью этого чата. В чате находится обычно около 70-80% мужчин, что может объясняться тем, что они использовали иконки с оружием 🔫.

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

И награду получает…

В качестве бонуса я написал код с графиком, который показывает Топ-5 наиболее часто используемых эмодзи на freeCodeCamp. Что интересно, некоторые эмодзи набирают постепенно популярность, в то время как другие постепенно сдают позиции. Это очень похоже на «Тур де Франс». Сегодня эмодзи является самым востребованным, а завтра о нем забывают.

Итак, вот самый популярный смайлик:

Честно говоря, я не ожидал, что 😄 («: smile:») станет самым популярным эмодзи. Я думал, что им будет 😂 («: joy:») , учитывая, что Apple недавно назвала его самым популярным за 2017 год.

Следующие 8 эмодзи также появлялись в чате freeCodeCamp. Угадайте, как называется каждый из них.

Я использовал Python и Gitter API, чтобы получать сообщения из основной комнаты чата freeCodeCamp. Библиотеки Python, такие как мультипроцесс и эмодзи, использовались для преобразования данных.

Часть преобразований также требовала данных, доступных в интернете, для которых я сделал настраиваемые скребки, также с библиотеками Python (запросы, urllib, BeautifulSoup4).

Для анализа данных я использовал простой Python и некоторые панды. Визуализация была сделана с использованием matplotlib, а интерактивные графики — в D3.js.

Версии кода доступны в моем репозитории GitHub вместе с несколькими конечными наборами данных. Что касается необработанных наборов данных, используемых для этого проекта, они теперь доступны в Kaggle freeCodeCamp.

Комментарии
Продолжить чтение

Обучение

Истории разработчиков, получивших первую работу после 30, 40 и 50 лет

Куинси Ларсон, преподаватель в freeCodeCamp, собрал более 300 историй разработчиков, которые доказывают, что начинать учиться программированию никогда не поздно.

Анна Гуляева

Опубликовано

/

Почему я это сделал

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

Мне __ лет. Мне уже поздно учиться разработке?

Это один из самых распространенных вопросов в разработке в целом. Чтобы показать вам, сколько разработчиков волнует их возраст, я зашёл на Quora. Конечно, я нашел людей всех возрастов, которые переживают из-за того, что они «слишком старые», чтобы учиться программированию и становиться разработчиком: 60, 59585756555453, 52, 51504948474645444342414039383534333231, 29282726252423222120191817161514.

Что вы скажете кому-то, кто переживает, не слишком ли уже поздно? Многие люди ограничатся старой цитатой Уолта Диснея: «Если вы можете представить это, вы можете сделать это!»

Но я понимаю эти переживания. Я работал учителем и не умел программировать до 30 лет. До этого возраста я не мог написать даже простой код на JacaScript. Я не мог установить Linux. Да, я даже не мог настроить роутер без помощи жены.

Я получил первую работу в качестве разработчика в 31. И, конечно, я верю, что возраст — это просто число. И что все, кто могут вложить в обучение свои силы, могут научиться программировать и получить работу.

Но как мне убедить всех этих людей, задающих этот вопрос каждый день? Просто говорить «не переставайте верить» — неэффективно.

Я собрал доказательства, чтобы убедить людей расслабиться по поводу возраста

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

Например, одна моя подруга была учительницей французского за 50. После бесплатных университетских онлайн-курсов она получила работу разработчика в Apple. Поэтому я знал, что это возможно.

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

Поэтому однажды, после очередной попытки успокоить тревоги людей, я пересмотрел свой подход. Я подумал: «Возможно, я смогу найти список разработчиков, которые получили первую работ в 30, 40 или больше лет. Может быть, это убедит людей перестать так беспокоиться о возрасте».

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

Оказалось, что многие разработчики получили первую работу в 30, 40 или 50 лет. Вот несколько историй:

https://twitter.com/mikleane/status/949452946600730626?ref_src=twsrc%5Etfw&ref_url=https%3A%2F%2Fmedium.freecodecamp.org%2Fmedia%2F2215e9cee7ade93a7ffbf76c00f6702a%3FpostId%3D64306eb6bb27

https://twitter.com/americanwombat/status/949486088325799937?ref_src=twsrc%5Etfw&ref_url=https%3A%2F%2Fmedium.freecodecamp.org%2Fmedia%2Ff3305f7a1f903b59e7c4c9a9c6edd974%3FpostId%3D64306eb6bb27

https://twitter.com/jefflazerus/status/949457462939205632?ref_src=twsrc%5Etfw&ref_url=https%3A%2F%2Fmedium.freecodecamp.org%2Fmedia%2Fc3053bd231b0056db2839f8c57f3828d%3FpostId%3D64306eb6bb27

https://twitter.com/peterdaily/status/949453856127307776?ref_src=twsrc%5Etfw&ref_url=https%3A%2F%2Fmedium.freecodecamp.org%2Fmedia%2F054d685fc2fed0e12bfc45634abf6296%3FpostId%3D64306eb6bb27

https://twitter.com/gillessew/status/950138976655912960?ref_src=twsrc%5Etfw&ref_url=https%3A%2F%2Fmedium.freecodecamp.org%2Fmedia%2F48799b09a4826507d15624371e46bf60%3FpostId%3D64306eb6bb27

https://twitter.com/amwcodes/status/949581047808716800?ref_src=twsrc%5Etfw&ref_url=https%3A%2F%2Fmedium.freecodecamp.org%2Fmedia%2F46ff7a793cd12eb3273696b47e4f17f3%3FpostId%3D64306eb6bb27

https://twitter.com/dbriesz/status/949483215256825856?ref_src=twsrc%5Etfw&ref_url=https%3A%2F%2Fmedium.freecodecamp.org%2Fmedia%2F5daccc8369b60bb9807d39e133237d74%3FpostId%3D64306eb6bb27

https://twitter.com/jessdelgrande/status/950163504773902342?ref_src=twsrc%5Etfw&ref_url=https%3A%2F%2Fmedium.freecodecamp.org%2Fmedia%2F700f10a61f7d7a18fd00ba8d9bc31ecf%3FpostId%3D64306eb6bb27

Я создал список из 300 разработчиков, которые начали после 30, чтобы показать, сколько людей начали переход к разработке ПО в более старшем возрасте. Я буду и дальше вести этот список. Поэтому, если вы разработчик, получивший первую работу после 30, твитните мне с хэштегом #DevAfter30, и я добавлю вас в список.

И если вы учитесь программировать позже, чем другие, не сдавайтесь. Знайте, что такое бывает часто. И знайте, что вы в хорошей компании.

Комментарии
Продолжить чтение

Программирование

50 вопросов и ответов для собеседования iOS-разработчиков: часть 1

iOS-разработчик Дурул Далканат собрал распространенные вопросы с собеседования iOS-разработчиков и, конечно, дал ответы на них.

Анна Гуляева

Опубликовано

/

1. Как настроить Live Rendering?

Атрибут @IBDesignable позволяет Interface Builder обновлять конкретные элементы.

2. Чем отличаются синхронная и асинхронная задача?

Синхронная: ждет, пока задача завершится. Асинхронная: завершает задачу в фоновом режиме и уведомляет вас о завершении.

3. Что такое b-деревья?

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

4. Что такое объект NSError?

Существует три части объекта NSError: домен, код ошибки и словарь с пользовательской информацией. Домен — это строка, которая идентифицирует, к какой категории относится эта ошибка.

5. Что такое Enum?

Enum – это тип, который в основном содержит группу связанных значений.

6. Что такое ограничивающий параллелепипед?

Ограничивающий параллелепипед — это термин, используемый в геометрии; он означает наименьшую меру (площадь или объем), в пределах которой находится набор точек.

7. Почему мы не используем strong для enum в Objective-C?

Поскольку enum не являются объектами, мы не указываем здесь strong или weak.

8. Что такое @synthesize в Objective-C?

Synthesize генерирует методы getter и setter для вашего свойства.

9. Что такое @dynamic в Objective-C?

Мы используем dynamic для подклассов NSManagedObject. @dynamic сообщает компилятору, что геттер и сеттеры реализованы где-то в другом месте.

10. Почему мы используем synchronized?

Synchronized гарантирует, что только один поток может выполнять этот код в блоке в любой момент времени.

11. В чем разница strong, weak, read only и copy?

Атрибуты свойства strong, weak, assign определяют, как будет управляться память для этого свойства.

Strong означает, что в сгенерированном сеттере счетчик ссылок на присваиваемый объект будет увеличен и ссылка на него будет поддерживаться в течение жизни объекта.

Weak означает, что мы указываем на объект, но не увеличиваем счетчик ссылок. Он часто используется при создании родительских-дочерних отношений. Родитель имеет сильную ссылку на ребенка, но ребенок имеет только слабую ссылку на родителя.

Read only —  мы можем установить свойство изначально, но затем его нельзя будет изменить.

Copy означает, что мы копируем значение объекта при его создании. Также предотвращает изменение его значения.

Больше подробностей вы можете узнать здесь.

12. Что такое Dynamic Dispatch?

Dynamic Dispatch — это процесс выбора реализации полиморфной операции, которая является методом или функцией для вызова во время выполнения. Это происходит, когда мы хотим вызывать наши методы как метод объекта. Swift по умолчанию не выполняет Dynamic Dispatch.

13. Что такое покрытие кода?

Покрытие кода — это метрика, которая помогает нам измерять ценность наших юнит-тестов.

14. Что такое обработчик завершения?

Обработчики завершения очень удобны, когда наше приложение вызывает API, и нам нужно что-то сделать, когда эта задача будет выполнена: например, обновить пользовательский интерфейс, чтобы отобразить данные из вызова API. Обработчики завершения можно найти в API Apple, например, dataTaskWithRequest, и они могут быть очень полезными в вашем коде.

Обработчик завершения принимает код с тремя аргументами: (NSData?, NSURLResponse?, NSError?), который ничего не возвращает: void. Это означает завершение.

Обработчики завершения должны быть помечены @escaping, так как они выполняются после выполнения функции.

15. Как определить место юзабилити в дизайне?

Для этого нужно разбить процесс дизайна на четыре шага:

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

Разница между UI и UX-дизайном

16. В чем разница между рамкой и границами (frame и bound)?

Границы в UIView — это прямоугольник, имеющий местоположение (x, y) и размер (ширина, высота) относительно собственной системы координат (0,0).

Рамка в UIView это прямоугольник, имеющий местоположение (x, y) и размер (высота, ширина) относительно элемента, в котором он содержится.

17. Что такое Responder Chain?

Responder Chain — это иерархия объектов, которые могут ответить на полученные события.

18. Что такое регулярные выражения?

Регулярные выражения — это специальные строки-шаблоны, которые описывают, как искать в строке.

19. Что такое перегрузка операторов?

Перегрузка операторов позволяет нам изменять взаимодействие существующих операторов с существующими типами.

20. Что такое TVMLKit?

TVMLKit — это связь между TVML, JavaScript и нативным tvOS-приложением.

21. Какие ограничения существуют у платформы tvOS?

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

Во-вторых, приложения tvOS не могут явно использовать локальное хранилище. При запуске продукта устройства поставляются с жестким диском либо на 32 ГБ, либо на 64 ГБ, но приложениям не разрешается напрямую сохранять файлы на устройство.

Бандл tvOS-приложения  не может превышать 4 ГБ.

22. Что такое функции?

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

Совет: хорошие функции принимают входные данные и возвращают выходные. Плохие функции устанавливают общие переменные и полагаются в работе на другие функции.

23. Что такое ABI?

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

24. Почему шаблон проектирования очень важен?

Шаблоны проектирования — это повторно используемые решения для распространенных проблем в создании приложений. Эти шаблоны созданы, чтобы помочь вам писать простой код, который можно будет использовать снова и снова. Самые распространенные шаблоны проектирования Cocoa:

  • порождающий — одиночка (Singleton);
  • структурные — декоратор (Decorator), адаптер (Adapter), фасад (Facade);
  • поведенческие — наблюдатель (Observer) и хранитель (Memento).

25. Что такое одиночка (Singleton)?

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

 

Комментарии
Продолжить чтение

Программирование

Как решить задачу Google про бросание яиц со здания

Марцин Москала рассказал об алгоритмическом подходе к решению любых задач на примере задачи с собеседования в Google.

Анна Гуляева

Опубликовано

/

На собеседованиях для программистов бывает много отличных задач. Моя любимая также нравится и рекрутерам Google:

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

Мы можем сделать несколько предположений:

  • Если при падении с конкретного этажа яйцо не разбивается, то оно не разобьется и при падении с более низких этажей.
  • Если яйцо не разбилось, его можно использовать снова.
  • Разбитое яйцо нужно исключить.
  • Эффект падения одинаков для всех яиц.
  • Если яйцо разбивается при падении, то оно разобьется и при падении с более высокого этажа.

Многие люди написали алгоритм для решения этой задачи (и мы напишем свой), но здесь есть простое решение.

Простой ответ

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

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

Интуитивный ответ

Наше первое яйцо нужно использовать, чтобы разделить сто этажей на более мелкие диапазоны как можно эффективнее. Тогда первое яйцо нужно бросить с 1/n этажа, например, ⅓. Тогда алгоритм будет выглядеть так:

  • Бросаем яйцо с 33 этажа. Если оно разбивается, проверяем первые 32 этажа вторым яйцом.
  • Если оно не разбивается, бросаем яйцо с 33 + (67 * ⅓) = 55 этажа. Если разбивается, проверяем этажи 34–55 вторым яйцом.

В худшем случае для ⅓ (33, 24,…) — это 33. Так мы можем найти идеальный n, который оптимизирует количество бросков при помощи динамического программирования. Это хорошее решение, которое показывает программистское мышление, но оно не является оптимальным.

Идеальное решение

Чтобы понять идеальное решение, нам нужно понять равенство, которое используется для вычисления количества бросков в худшем случае:

Где F(n) — это следующий этаж, с которого мы бросаем первое яйцо.

Если мы введем такую переменную:

То равенство будет выглядеть так:

Оптимальным решением является такое, когда все аргументы этой максимальной функции равны. Как этого достичь? Если смотреть с конца, последним D(n) должно быть 1, потому что так мы дойдем до точки, в которой для первого яйца останется только один этаж. Тогда D(n-1) должна быть равна 2, потому что она отличается одним броском первого яйца.

Если первое яйцо в последний раз сбросить с 99 этажа, то до этого мы получим 99-2=97, 97-3=94, 90, 85, 79, 72, 64, 55, 45, 34, 22 и 9 этажи. Это оптимальное решение! Так, в худшем случае, нам нужно будет сделать 14 бросков (меньшая разница равна 13, но нам нужно сделать ещё один бросок с 9 этажа).

Проверка

Ок, у нас есть решение, и мы можем вычислить его без посторонней помощи. Время проверить его правильность. Для этого мы напишем простую программу на Kotlin. Сначала выразим, как посчитать количество бросков для какого-либо решения. Когда у нас есть 2 или меньше этажей, нам нужно сделать столько бросков, сколько осталось этажей. В ином случае мы должны использовать уже представленное равенство:

fun maxThrows(floorsLeft: Int, nextFloor: Int): Int =
  if (floorsLeft <= 2) floorsLeft
  else maxOf(nextFloor, bestMaxThrows(floorsLeft - nextFloor) + 1)

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

fun bestMaxThrows(floorsLeft: Int): Int =
  maxThrows(floorsLeft, bestNextStep(floorsLeft))

Мы делегировали обязанность оптимизации следующего этажа функции bestNextStep. Она дает нам лучший следующий шаг. Мы можем определить её просто — когда осталось 2 этажа или меньше, мы бросим яйцо с первого этажа. В ином случае нам нужно проверить все варианты и выбрать оптимальный.

val bestNextStep(floorsLeft: Int): Int = 
  if (floorsLeft <= 2) 1
  else (1..floorsLeft)
        .toList()
        .minBy { maxThrows(floorsLeft, it) }!!

Эта функция использует maxThrows, поэтому у нас возникает повторение. Это не проблема, потому что, когда bestNextStep вызывает MaxThrows, она всегда вызывает ее со значением меньше, чем floorsLeft (потому что nextFloor всегда больше нуля). Перед использованием добавим буферизацию для ускорения вычислений:

val bestNextStep: (Int) -> Int = memorise { floorsLeft ->
  if (floorsLeft <= 2) 1
  else (1..floorsLeft)
        .toList()
        .minBy { maxThrows(floorsLeft, it) }!!
}

fun maxThrows(floorsLeft: Int, nextFloor: Int): Int =
  if (floorsLeft <= 2) floorsLeft
  else maxOf(nextFloor, bestMaxThrows(floorsLeft - nextFloor) + 1)


val bestMaxThrows: (Int) -> Int = memorise { floorsLeft ->
  maxThrows(floorsLeft, bestNextStep(floorsLeft))
}

fun <V, T> memorise(f: (V) -> T): (V) -> T {
    val map = mutableMapOf<V, T>()
    return { map.getOrPut(it) { f(it) } }
}

Теперь мы можем проверить, возвращает ли функция тот же результат, что мы вычислили:

fun main(args: Array<String>) {
    print(bestMaxThrows(100)) // Prints: 14
}

Хороший ответ. Проверим следующие шаги:

fun main(args: Array<String>) {
    var floor = 0
    while (floor < 100) {
        val floorsLeft = 100 - floor
        val nextStep = bestNextStep(floorsLeft)
        floor += nextStep
        print("$floor, ")
    }
}

Результат: 9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100, как мы и вычислили.

Большая перспектива

Теперь у нас есть хороший алгоритм для решения похожих проблем. Например, мы можем немного изменить его, чтобы вычислить количество бросков в самом вероятном сценарии. Мы можем проверить, как минимальное число бросков будет зависеть от высоты здания. Вот график с ответом на этот вопрос:

Заключение

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

Комментарии
Продолжить чтение

Наша рассылка

Каждому подписавшемуся - "1 час на UI аудит": бесплатный ускоренный курс для разработчиков!

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

Вакансии

Популярное

X

Спасибо!

Теперь редакторы в курсе.