Connect with us

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

Как решить задачу 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, но, что важнее, вы лучше знакомы с общим алгоритмическим мышлением. Этот алгоритм представляет хороший функциональный подход, который можно использовать для разных проблем в нашей работе.

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

You must be logged in to post a comment Login

Leave a Reply

Мероприятия

ВКонтакте открывает регистрацию на чемпионат по программированию VK Cup 2018

ВКонтакте анонсировал ежегодный чемпионат по программированию VK Cup 2018. К участию приглашаются программисты от 14 до 23 лет. В одной команде может быть один или два человека.

AppTractor

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

/

Автор:

Призовой фонд VK Cup 2018 составляет 2,5 млн руб.:

  • 1 место – 1 048 576 руб.
  • 2 местo – 524 288 руб.
  • 3 местo – 262 144 руб.
  • 4-8 места – 131 072 руб.

Соревнование пройдёт в несколько этапов на площадке Codeforces. Начать свой путь к чемпионскому кубку можно с одного из квалификационных раундов 24 февраля или 2 марта.

В финале VK Cup 2018, который состоится в августе в Санкт-Петербурге, сразятся 20 команд, прошедших все этапы предварительных отборов. ВКонтакте покроет расходы на проезд и проживание финалистов.

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

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

Создание анимации в 7 строк кода

Android-разработчик Леонардо Пирро рассказывает, как создать простую анимацию при помощи ConstraintLayout и ConstraintSet.

Анна Гуляева

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

/

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

ConstraintLayout + ConstraintSet

Я хочу поделиться с вами новым способом создания анимаций в приложении при помощи всего семи строк кода, используя Keyframe Animations, ConstraintLayout и ConstraintSet. Эта концепция заключается в создании двух разных макетов: одного для начальной точки и одного для конечной точки анимации. Давайте посмотрим, что мы хотим создать: наша цель — создать плавную анимацию детали, которая будет появляться при нажатии пользователем на экран.

Анимация создается при помощи двух файлов макета: circuit.xml and circuit_detail.xml. Эти макеты очень похожи и различаются только тем, что на первом элементы вынесены за экран, а на втором — находятся в нужной позиции.

Поэтому давайте создадим анимацию и увидим, как просто создавать анимацию при помощи ConstraintLayout и ConstraintSet.

Пусть магия произойдет

Сначала создадим отдельный ConstraintSet, куда мы скопируем ограничения второго макета, вызвав метод clone():

val constraintSet = ConstraintSet()
constraintSet.clone(this, R.layout.circuit_detail)

Теперь создадим объект перехода, используемый для установки интерполятора и продолжительности анимации:

val transition = ChangeBounds()
transition.interpolator = AnticipateOvershootInterpolator(1.0f)
transition.duration = 1200

Сейчас вызовем TransitionManager.beginDelayedTransition(), который используется для осуществления перехода на следующий кадр рендеринга. Затем мы вызываем applyTo(), чтобы начать анимацию.

TransitionManager.beginDelayedTransition(constraint, transition)

constraintSet.applyTo(constraint)

Это действительно семь строк кода. Вот и все! Вы можете посмотреть полный пример в моем репозитории GitHub по этой ссылке.

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

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

Как начать работать с Flutter

Урок по созданию простого приложения при помощи Flutter. Flutter — это проект от Google, который позволит вам создавать нативные приложения.

Анна Гуляева

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

/

JavaScript развился достаточно хорошо и мы увидели много фреймворков для создания гибридных мобильных приложений – возьмите, например, Ionic и Angular. Затем на сцене появились React Native и NativeScript, которые позволяют вам создавать нативные мобильные приложения без знания Java или Swift.

Можем ли мы создать приложения без этих фреймворков? Да! Эта статья позволит вам создать первое приложение на Flutter. Flutter — это проект от Google в альфа-версии, который должен позволить вам создавать нативные приложения.

Наша цель: создать приложение для списка покупок на Flutter и Firebase.

Что вам нужно установить

Flutter: установите Flutter по этой ссылке. Не забудьте пройти все шаги установки, включая плагины.

Xcode: если вы работаете с Mac, вам нужна будет Xcode, которую вы можете скачать из App Store.

Android Studio: Она вам будет нужна для создания Android-версии вашего приложения.

IDE: Я использую VSCode как основной редактор текста и для него существуют ещё плагины Flutter и Dart, но я рекомендую Intellij IDEA для Flutter-разработки. Скачайте его здесь.

Запустите тестовое приложения

Запустите IDE и нажмите «Создать новый проект», затем выберите слева Flutter.

Если вы пропустили некоторые шаги в установке, то,возможно, вы не увидите эту опцию 💀. Если же вы все сделали правильно, то давайте продолжим.

Заполните все остальное по своему желанию.

Java по умолчанию используется для Android, но я переключился на Swift для iOS, потому что ничего не знаю о, Objective-C – вы можете сделать, как хотите.

Теперь у вас есть каркас приложения. Уберите все комментарии, потому что они бесполезны. Также уберите методы floatingActionButton, body content и _incrementCounter.

Создание интерфейса

Создайте новую строку в классе и замените название приложения и виджета. Я также изменил цвет на красный. Мне так больше нравится!

В _MyHomePageState создайте TextEditingController, который является контроллером для редактируемого текстового поля.

final TextEditingController _textController = new TextEditingController();

Затем создайте метод _handleSubmitted

void _handleSubmitted(String text){
 
}

и добавьте этот код, чтобы создать контейнер ввода внизу.

Widget _createInputContainer() {
        return new Container(
          margin: const EdgeInsets.symmetric(horizontal: 16.0),
          child: new Row(
            children: <Widget>[
              new Flexible(
                child: new TextField(
                    controller: _textController,
                    onSubmitted: _handleSubmitted,
                    decoration: new InputDecoration.collapsed(
                        hintText: "Add something"),
                ),
            ),
            new Container(
                child: new IconButton(
                    color: Colors.red,
                    icon: new Icon(Icons.list),
                    onPressed: (){}),
            ),
            new Container(
                child: new IconButton(
                    color: Colors.red,                    
                    icon: new Icon(Icons.send),
                    onPressed: (){}),
            ),
        ],
    ),
);
}

Мы создали контейнер для элемента ввода, кнопку списка и кнопку “Отправить”. onPressed функции сейчас пустые, мы поработаем над этим позже.

Теперь вернемся к body нашего Scaffold. Измените код body следующим образом:

body: new Column(
  children: <Widget>[
      new Flexible(
          child: new ListView.builder(
              padding: new EdgeInsets.all(8.0),
              reverse: false,
              itemBuilder: (_, int index) => null,
              itemCount: 1,
          ),
      ),
      new Divider(height: 1.0),
      new Container(
          decoration: new BoxDecoration(
              color: Theme.of(context).cardColor),
          child: _createInputContainer(),
      ),
  ],
)

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

Что ещё нужно сделать

  1. Заполните метод _handleSubmitted.
  2. Добавьте текст как новый элемент списка и выведите его.
  3. Сделайте список интерактивным и понятным для пользователя.
  4. Добавьте в проект базу данных Firebase.

Давайте продолжим

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

void _handleSubmitted(String newItem){
    _textController.clear();
}

Модифицируйте кнопку “Отправить”:

new Container(
    child: new IconButton(
        color: Colors.red,
        icon: new Icon(Icons.send),
        onPressed: (){
            _handleSubmitted(_textController.text) //modify this
        }),
),

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

Теперь мы создадим свой виджет, который будет отображать предметы списка. Сначала сделаем виджет, который будет представлять отдельный элемент. Создадим StatelessWidget, назовем его ListItem и поместим снаружи _MyHomePageState.

class ListItem extends StatelessWidget {
    ListItem({this.itemName});
    final String itemName;
    @override
    Widget build(BuildContext context) {
    return new Container(
        margin: const EdgeInsets.symmetric(vertical: 10.0),
        
    );
}
}

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

child: new Row(
    crossAxisAlignment: CrossAxisAlignment.start, //its nice ;)
     children: <Widget>[
         new Column(
             crossAxisAlignment: CrossAxisAlignment.start,
              children: <Widget>[
                  new Container(
                      child: new Text(itemName), //this is item name
                   ),
              ],
          ),
     ],
),

Таким образом, весь код для виджета ListItem выглядит так:

class ListItem extends StatelessWidget {
    ListItem({this.itemName});
    final String itemName;
    @override
    Widget build(BuildContext context) {
        return new Container(
            margin: const EdgeInsets.symmetric(vertical: 10.0),
            child: new Row(
                crossAxisAlignment: CrossAxisAlignment.start,
                children: <Widget>[
                    new Flexible(
                        new Column(
                        crossAxisAlignment:CrossAxisAlignment.start,
                        children: <Widget>[
                            new Container(
                                child: new Text(itemName),
                            ),
                    ),
                        ],
                    ),
                ],
            ),
        );
    }
}

Теперь вернемся к _MyHomePageState и добавим эту строку:

final List<ListItem> _shopItems = <ListItem>[];

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

Уделим немного внимания методу _handleSubmitted.

void _handleSubmitted(String newItem){
    _textController.clear();
    if(newItem.trim().length > 0){ 
        ListItem listItem = new ListItem(
            itemName: newItem, //Initialize our ListItem widget and assign user's input as instance value.
        );
        setState(() {
            _shopItems.insert(0, listItem);
        });
        //Notify the framework that the internal state of this object has changed.
    }
}

В качестве финального шага перейдем к ListView в body нашего главного виджета.

child: new ListView.builder(
    padding: new EdgeInsets.all(8.0),
    reverse: false,
    itemBuilder: (_, int index) => _shopItems[index], //modify this
    itemCount: _shopItems.length, // modify this
),

До этого изменения функция itemBuilder была null. Теперь она создает запись в списке по индексу из _shopItems, и мы изменили itemCount на значение _shopItems.

Запустим приложение:

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

Почему мы выбрали Flutter

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

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

Применение Google Cloud Vision API в приложении для Android

Android-разработчик Леонардо Пирро рассказал об инструменте компьютерного зрения от Google и его применении в приложениях.

Анна Гуляева

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

/

Искусственный интеллект и машинное обучение — это одни из самых популярных тем в бизнесе. Google, лидер области, разработала набор инструментов для разработчиков, которые позволят создать новый пользовательский опыт с безграничными возможностями. Сегодня мы исследуем Google Cloud Vision API и его применение в приложениях Android.

Google Cloud Vision API

Это интересный API, который позволяет разработчикам анализировать изображения и контекстуальные данные, используя самонаводящуюся модель машинного обучения в дальнейшей эволюции — все в простом REST API. Благодаря этому API, мы можем получать контекстуальную информацию о данном изображении, классифицировать изображения на категории и подкатегории, достигая глубокого уровня детализации информации.

Для примера возьмем это изображение:

Vision API удивителен, он может распознать основной субъект фото (животное), определить его вид (собака) и породу (бигль). Более того, вы можете получить дополнительные данные о траве и горах на фоне.

Давайте взглянем на все функции Google Cloud Vision API:

  • Обнаружение меток: обнаружение категорий внутри изображения (пример выше).
  • Обнаружение откровенного содержимого: обнаружение неприличного или жестокого содержимого в изображении.
  • Обнаружение популярных логотипов.
  • Обнаружение ориентиров: естественных и искусственных структур в изображении.
  • Оптическое распознавание символов: обнаружение и извлечение текста внутри изображения, API даже распознает язык текста
  • Обнаружение лица: обнаружение нескольких лиц внутри изображения, а также других атрибутов, таких как эмоциональное состояние или головные уборы.
  • Атрибуты изображения. Обнаружение общих атрибутов изображения, таких как доминирующие цвета.

В нашем примере мы используем две функции: обнаружение меток и оптическое распознавание символов. Давайте посмотрим, как интегрировать Vision API в приложение Android. Мы создадим пробный проект, который позволит пользователю выбирать изображение из галереи и получать о нем информацию.

Внедрение Google Cloud API

Чтобы использовать API, мы должны внедрить его в Google Cloud Developer Console. Вот как это сделать:

  1. Создайте проект в Google Cloud Console или используйте существующий.
  2. Включите в проекте Billing. Если это ваше первое использование Google Cloud Console, вы можете начать бесплатный пробный период использования. У вас могут попросить данные карты, но денег не спишут.
  3. Включите Google Cloud Vision API, используя эту ссылку.
  4. Откройте в боковом меню слева секцию Credentials.
  5. Выберите в меню OAuth Client ID: установите тип приложения Android, введите название приложения и отпечаток SHA1 (если у вас его нет или вы не знаете, как его сгенерировать, введите эту команду в терминале keytool -exportcert -keystore path-of-your-keystore -list -v). Затем введите имя пакета вашего приложения: оно должно совпадать с именем, указанным в файле build.gradle вашего приложения, в ключе applicationId. В моем случае —  com.lpirro.cloudvision.

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

Cloud Vision API в действии

Создайте новый проект в Android Studio и помните, что имя пакета должно совпадать с названием в проекте в Google Cloud Developer Console. Затем откройте build.gradle и добавьте зависимости Vision API.

Теперь откройте AndroidManifest.xml и добавьте необходимые разрешения для сетевых вызовов и получения информации об учетной записи, необходимой для запроса OAuth.

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

Файл макета нашей активности очень прост: у нас есть один ImageView, используемый для отображения выбранного изображения из галереи, два TextView для отображения результатов и одна Button, используемая для выбора изображения из галереи.

Вот файл с макетом нашей активности:

Теперь остановимся на Activity. В этом примере мы используем библиотеку Google API Client для Java, и так как мы используем OAuth request, нам нужно получить от Google токен аутентификации. Давайте определим класс, который позволит нам получить этот токен.

Примечание: для простоты мы будем использовать AsyncTask для сетевых операций, но если вы будете использовать этот API в реальном проекте, используйте библиотеку, например, Retrofit, возможно, вместе с RxJava.

Теперь у нас есть вся необходима информация, чтобы вызвать Cloud Vision API и получить результаты.

При помощи метода setType() мы определим тип функции, которую хотим использовать: в нашем случае это LABEL_DETECTION и TEXT_DETECTION. Формат изображения, переданного API, находится в Base64. Как только результаты будут получены, они передаются методу getDetectedText (), который будет форматировать строку и фильтровать информацию, после чего мы можем окончательно отобразить их в интерфейсе.

И искусственный интеллект, и машинное обучение быстро становятся основой для цифровых преобразований на ближайшие годы. С внедрением Cloud Vision API Google предлагает первоклассный инструмент для интеграции этих технологий в повседневный рабочий процесс как пользователей, так и разработчиков. Прямо сейчас, та же технология, что мы видели выше, уже является частью основных продуктов Google, таких как «Фотографии», используемых в качестве помощи для организации и классификации нашей коллекции воспоминаний. Благодаря общей доступности этих инструментов тысячи продуктов смогут интегрировать эту удивительную технологию.

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

Постеры для разработчиков

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

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

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

Вакансии

Популярное

X
X

Спасибо!

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