Две задачи с собеседования в amazon
Некоторое время назад мне на linkedin'e написала hr из амазона, я согласился попытаться решить несколько задач. Задачи вроде решил корректно, но следующий этап собеседования не состоялся. Не знаю почему, но мы просто не смогли созвониться. В этом посте расскажу о двух задачах. Я вроде бы их верно решил.
Первая задача
Первая задача - написать функцию, которая принимает на вход 6 чисел, и надо из них составить наименьшее возможное время. Время должно быть в формате %H:%M:%S, если составить его невозможно, то следует вернуть строку "NOT POSSIBLE".
Примеры того как функция может вызываться, и что она должна возвращать:
task1(1, 2, 3, 4, 5, 6) -> "12:34:56"
task1(9, 9, 9, 9, 9, 9) -> "NOT POSSIBLE"
Поскольку время на задания было ограничено, то я решил пойти по самому простому и очевидному пути - решать эту проблему полным перебором. Есть в стандартной библиотеке модуль itertools. Также, в нем есть функция permutations, с помощью которой можно получить все перестановки списка, пример:
Python 3.6.8 (default, Jan 14 2019, 11:02:34)
[GCC 8.0.1 20180414 (experimental) [trunk revision 259383]] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import itertools
>>> itertools.permutations([1,2,3])
<itertools.permutations object at 0x7f0d2ada3db0>
>>> for var in itertools.permutations([1,2,3]):
... print(var)
...
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
Если я правильно помню, то математика нам говорит о том, что перестановок должно быть n!, как видно, именно 6 перестановок списка из 3 элементов мы и получили.
Тогда алгоритм решения может быть таким:
- Сортируем все 6 чисел по возрастанию.
- Если после сортировки из чисел складывается валидное время - то это и есть минимальное время.
- Если же сортированное время невалидно, то применяем полный перебор.
У меня получилось это сделать так (не утверждаю, что данное решение оптимальное):
1from datetime import datetime 2import itertools 3 4 5def task1(A, B, C, D, E, F): 6 # сортирую список чисел 7 sorted_list = sorted([A, B, C, D, E, F]) 8 # первые два числа - часы 9 h = str(sorted_list[0]) + str(sorted_list[1]) 10 # минуты 11 m = str(sorted_list[2]) + str(sorted_list[3]) 12 # секунды 13 s = str(sorted_list[4]) + str(sorted_list[5]) 14 # если время не валидно, то применяю полный перебор 15 if int(h) > 23 or int(m) > 59 or int(s) > 59: 16 # задаю две переменных - минимальное время и текущее 17 min_variant_date, variant_date = None, None 18 # список всех перестановок 6-ти чисел 19 for var in itertools.permutations(sorted_list): 20 try: 21 # пытаюсь сформировать дату из текущей перестановки 22 variant_date = datetime.strptime( 23 '{0}{1}:{2}{3}:{4}{5}'.format(*var), 24 '%H:%M:%S') 25 except Exception: 26 pass 27 # если нет ошибки 28 else: 29 # если мы в самом начале перебора или нашли меньшее время 30 if not min_variant_date or variant_date < min_variant_date: 31 # устанавливаем меньшее время 32 min_variant_date = variant_date 33 # если минимальное время было найдено 34 if min_variant_date: 35 return min_variant_date.strftime('%H:%M:%S') 36 else: 37 return 'NOT POSSIBLE' 38 # отсортированное время валидно, возвращаю его 39 else: 40 return h+':'+m+':'+s
Проверю себя с помощью assert:
1assert task1(1, 2, 3, 4, 5, 6) == '12:34:56' 2assert task1(1, 2, 3, 4, 7, 7) == '12:37:47' 3assert task1(1, 2, 3, 4, 8, 9) == '12:38:49' 4assert task1(9, 9, 9, 9, 1, 2) == 'NOT POSSIBLE'
Вроде правильно. Может быть, я не учел все граничные случаи, но в какой-то степени решение рабочее.
Вторая задача
Во второй задаче надо определить минимальное количество лучей, выпущенных из начала координат, и проходящих через все точки на плоскости. То есть у нас есть система координат и несколько точек:
В данном случае у нас 4 точки, поэтому количество лучей - 4. Если же у нас есть 5 точек:
То в этом случае у нас в первом квадранте три точки, и по одной точке во втором и третьем, соответственно, нам понадобится 3 луча. То есть, решить задачу можно, разбивая плоскость на 4 квадранта. Для задачи задается класс Point2D:
1class Point2D(object): 2 3 def __init__(self, x, y): 4 self.x = x 5 self.y = y
Примеры того, как функция должна работать, на вход задается массив точек:
task2([Point2D(1, 1), Point2D(1, 2)]) -> 2
task2([Point2D(1, 1), Point2D(2, 2), Point2D(3, 3)]) -> 1
Я решил данную задачу так:
1def task2(alist): 2 quadrant_first = {} 3 quadrant_second = {} 4 quadrant_third = {} 5 quadrant_fourth = {} 6 # y = kx; k = y/x 7 for elem in alist: 8 k = elem.y / elem.x 9 if elem.x > 0 and elem.y > 0: 10 quadrant_first[k] = True 11 elif elem.x < 0 and elem.y > 0: 12 quadrant_second[k] = True 13 elif elem.x < 0 and elem.y < 0: 14 quadrant_third[k] = True 15 else: 16 quadrant_fourth[k] = True 17 return len(quadrant_first) + len(quadrant_second) + len(quadrant_third) + len(quadrant_fourth)
Проверяю себя:
1assert task2([Point2D(1, 1), Point2D(1, 2)]) == 2 2assert task2([Point2D(1, 1), Point2D(2, 2), Point2D(3, 3)]) == 1 3assert task2([Point2D(1, 1), Point2D(2, 2), Point2D(3, 3), Point2D(-1, 2)]) == 2
Хоть я решил эти две задачи (надеюсь что правильно), но второй этап собеседования не состоялся. Если хотите, предлагайте свои решения, наверняка есть лучшие способы.