Изображение гика

Блог питониста

Две задачи с собеседования в amazon

29 сентября 2019 г.

Некоторое время назад мне на 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 элементов мы и получили.

Тогда алгоритм решения может быть таким:

  1. Сортируем все 6 чисел по возрастанию.
  2. Если после сортировки из чисел складывается валидное время - то это и есть минимальное время.
  3. Если же сортированное время невалидно, то применяем полный перебор.

У меня получилось это сделать так (не утверждаю, что данное решение оптимальное):

 1 def task1(A, B, C, D, E, F):
 2     sorted_list = sorted([A, B, C, D, E, F])
 3     h = str(sorted_list[0]) + str(sorted_list[1])
 4     m = str(sorted_list[2]) + str(sorted_list[3])
 5     s = str(sorted_list[4]) + str(sorted_list[5])
 6     if int(h) > 23 or int(m) > 59 or int(s) > 59:
 7         min_variant_date, variant_date = None, None
 8         for var in itertools.permutations(sorted_list):
 9             try:
10                 variant_date = datetime.strptime(
11                     '{0}{1}:{2}{3}:{4}{5}'.format(*var),
12                     '%H:%M:%S')
13             except Exception:
14                 pass
15             else:
16                 if not min_variant_date or variant_date < min_variant_date:
17                     min_variant_date = variant_date
18         if min_variant_date:
19             return min_variant_date.strftime('%H:%M:%S')
20         else:
21             return 'NOT POSSIBLE'
22     else:
23         return h+':'+m+':'+s

Проверю себя с помощью assert:

1 assert task1(1, 2, 3, 4, 5, 6) == '12:34:56'
2 assert task1(1, 2, 3, 4, 7, 7) == '12:37:47'
3 assert task1(1, 2, 3, 4, 8, 9) == '12:38:49'
4 assert task1(9, 9, 9, 9, 1, 2) == 'NOT POSSIBLE'

Вроде правильно. Может быть, я не учел все граничные случаи, но в какой-то степени решение рабочее.

Вторая задача

Во второй задаче надо определить минимальное количество лучей, выпущенных из начала координат, и проходящих через все точки на плоскости. То есть у нас есть система координат и несколько точек:

decart.png

В данном случае у нас 4 точки, поэтому количество лучей - 4. Если же у нас есть 5 точек:

decart2.png

То в этом случае у нас в первом квадранте три точки, и по одной точке во втором и третьем, соответственно, нам понадобится 3 луча. То есть, решить задачу можно, разбивая плоскость на 4 квадранта. Для задачи задается класс Point2D:

1 class 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

Я решил данную задачу так:

 1 def 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)

Проверяю себя:

1 assert task2([Point2D(1, 1), Point2D(1, 2)]) == 2
2 assert task2([Point2D(1, 1), Point2D(2, 2), Point2D(3, 3)]) == 1
3 assert task2([Point2D(1, 1), Point2D(2, 2), Point2D(3, 3), Point2D(-1, 2)]) == 2

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

Метки

python
Если вам понравился пост, можете поделиться им в соцсетях: