Вчера вечером проходил кодинг-собеседование онлайн. Заключалось оно в решении 4 задач на платформе hackerrank.
Первый раз пробовал такое, в принципе понравилось. Уж куда удобнее, чем тащиться в офис компании и полтора часа сидеть с ноутбуком (привет, "одноклассники"). Еще из плюсов - есть тесты, можно сразу посмотреть, работает ли решение. Если тест валится, то входные данные и ответ скрываются, но в случае возникновения эксепшена (ошибки) указывается, в какой строке она случилась.
На выполнение всех задач отводилось 1,5 часа. Так как я там ставил галочку о нераспространении текста задач, привожу их в немного измененном/обобщенном/упрощенном виде, который, по идее, не меняет сути задачи. Курсивом выделил свои комментарии по задаче. Оценки О-большого могут быть некорректными :)
1. Найти количество "кружочков" в числе (неотрицательное, инт). Типа 88 -> 4 кружочка, 1111 -> 0 и т.д.
Я подобную задачу когда-то давно уже встречал, поэтому идею решения не пришлось искать с нуля. По идее, работает за О(n), где n это количество цифр в исходном числе
2. Есть массив строк, каждая из которых содержит только латинские буквы (a-z A-Z). Количество букв > 1 и порядок произвольный. Каждая буква в строке может встречаться от 0 до N раз. Нужно найти количество букв, которые встречаются в каждой строке.
Такое прежде не встречал, пришлось думать :) В итоге написал штуку, которая работает за О(n * l), где n - размер массива, а l - средняя длина строки в массиве. Дополнительной памяти нужно О(1)
3. Дан массив интов размером > 1. Надо найти 2 индекса k и j такие, что k < j, a[j] - a[k] > 0 и a[j] - a[k] максимально для всего массива. Если таких индексов нет, то вернуть -1 для каждого.
Тоже пришлось изобретать колесо и немного воспользоваться помощью гугла. Не уверен, что решил оптимально. По идее, у меня работает за О(n) и требует O(n) памяти. Отмечу, что лобовой способ работает за О(n^2) и тесты валятся по таймауту (долго работает, короче говоря)
4. Есть собака, которая стоит в некоторой исходной клетке и выполняет команды. Команда = 1 буква, которая означает, куда надо двигаться собаке (F - прямо, L - влево, R - направо, B - назад). Любое перемещение = переход на соседнюю клетку в заданном направлении.
На вход дается строка команд размером > 1.
Эта строка будет повторяться бесконечное количество раз. Нужно определить, будет ли собака бесконечно удаляться от начальной точки или нет (в виде строки YES или NO).
На эту задачу, к сожалению, времени не хватило. Сегодня с утра в автобусе решил ее и написал HRу письмо с просьбой сказать, правильно ли я сделал или нет, добавив идею решения и ссылку на код. Будем надеяться на позитивный ответ.
Возможно, на самом хакерранке эти задачи имеются и там можно их порешать.
Первый раз пробовал такое, в принципе понравилось. Уж куда удобнее, чем тащиться в офис компании и полтора часа сидеть с ноутбуком (привет, "одноклассники"). Еще из плюсов - есть тесты, можно сразу посмотреть, работает ли решение. Если тест валится, то входные данные и ответ скрываются, но в случае возникновения эксепшена (ошибки) указывается, в какой строке она случилась.
На выполнение всех задач отводилось 1,5 часа. Так как я там ставил галочку о нераспространении текста задач, привожу их в немного измененном/обобщенном/упрощенном виде, который, по идее, не меняет сути задачи. Курсивом выделил свои комментарии по задаче. Оценки О-большого могут быть некорректными :)
1. Найти количество "кружочков" в числе (неотрицательное, инт). Типа 88 -> 4 кружочка, 1111 -> 0 и т.д.
Я подобную задачу когда-то давно уже встречал, поэтому идею решения не пришлось искать с нуля. По идее, работает за О(n), где n это количество цифр в исходном числе
2. Есть массив строк, каждая из которых содержит только латинские буквы (a-z A-Z). Количество букв > 1 и порядок произвольный. Каждая буква в строке может встречаться от 0 до N раз. Нужно найти количество букв, которые встречаются в каждой строке.
Такое прежде не встречал, пришлось думать :) В итоге написал штуку, которая работает за О(n * l), где n - размер массива, а l - средняя длина строки в массиве. Дополнительной памяти нужно О(1)
3. Дан массив интов размером > 1. Надо найти 2 индекса k и j такие, что k < j, a[j] - a[k] > 0 и a[j] - a[k] максимально для всего массива. Если таких индексов нет, то вернуть -1 для каждого.
Тоже пришлось изобретать колесо и немного воспользоваться помощью гугла. Не уверен, что решил оптимально. По идее, у меня работает за О(n) и требует O(n) памяти. Отмечу, что лобовой способ работает за О(n^2) и тесты валятся по таймауту (долго работает, короче говоря)
4. Есть собака, которая стоит в некоторой исходной клетке и выполняет команды. Команда = 1 буква, которая означает, куда надо двигаться собаке (F - прямо, L - влево, R - направо, B - назад). Любое перемещение = переход на соседнюю клетку в заданном направлении.
На вход дается строка команд размером > 1.
Эта строка будет повторяться бесконечное количество раз. Нужно определить, будет ли собака бесконечно удаляться от начальной точки или нет (в виде строки YES или NO).
На эту задачу, к сожалению, времени не хватило. Сегодня с утра в автобусе решил ее и написал HRу письмо с просьбой сказать, правильно ли я сделал или нет, добавив идею решения и ссылку на код. Будем надеяться на позитивный ответ.
Возможно, на самом хакерранке эти задачи имеются и там можно их порешать.