Я сейчас активно ищу работу, прохожу собеседования и иногда работодатели присылают тестовые задания, прежде чем пригласить на интервью. В очередной раз мне прислали простенькое тестовое задание, в целом много таких похожих: из списка вершин построить дерево.
Тестовое задание
Write a python function that builds a tree based on a list of tuples of id (parent id, offspring id),
where None is the id of the root node.
How this should work:
source = [
(None, 'a'),
(None, 'b'),
(None, 'c'),
('a', 'a1'),
('a', 'a2'),
('a2', 'a21'),
('a2', 'a22'),
('b', 'b1'),
('b1', 'b11'),
('b11', 'b111'),
('b', 'b2'),
('c', 'c1'),
]
expected = {
'a': {'a1': {}, 'a2': {'a21': {}, 'a22': {}}},
'b': {'b1': {'b11': {'b111': {}}}, 'b2': {}},
'c': {'c1': {}},
}
assert to_tree(source) == expected
И мне вдруг подумалось, а как хайповый chatGPT мог бы справиться с таким полуреальным, но вполне полезным для меня, заданием? Мысль пришла, а руки уже искали информацию, как прорваться к chatGPT из России. Спустя какое-то время прорвался и прям в лоб, ничего не меняя в тексте задания, отправляю тестовое и с интересом жду.
Довольно быстро chatGPT пишет мне ответ со своим решением и даже что-то объясняет.
Самое первое решение
def to_tree(source): tree = {} for parent, offspring in source: if parent is None: tree[offspring] = {} else: tree[parent][offspring] = {} for parent, offspring in source: if parent is not None: tree[parent][offspring] = to_tree( [(p, o) for p, o in source if p == offspring] ) return treeВыглядит на первый поверхностный взгляд правдоподобно, смущают некоторые моменты, но это вполне код. Запускаю этот код в Python и естественно он не работает. С чувством превосходства человеческого интеллекта над бездушной машиной, пытаюсь выдавить еще что-то из chatGPT и прошу проаннотировать типы. Он более-менее справляется. Прошу оценить алгоритмическую сложность. В целом, он правильно оценивает, как O(n*n) и даже дает советы, как улучшить — используй, говорит, специализированные структуры данных.
Я тоже не промах, и прошу его самого улучшить код с точки зрения алгоритмической сложности. И это чудо выдает мне что-то очень странное.
Практически бессмысленный код
def to_tree(source: List[Tuple[str, str]]) -> Dict[str, str]: # Initialize an empty tree tree = {} # Iterate through the source list and add the nodes to the tree for parent, offspring in source: tree[offspring] = parent # Return the tree return treeПосле этого спешу к другу разработчику, чтобы за глаза песочить chatGPT за криворукость и тупость. В процессе снисходительного обсуждения мы приходим к мысли, что вообще-то работа разработчика на половину состоит из правильной постановки задачи. С этой мыслью и с чуть угасшим чувством собственного превосходства, я решил чуть поправить решение chatGPT используя его же совет по использованию специальных структур данных.
Мои правки
from typing import List, Tuple, Dict, Optional, Any def to_tree(data: List[Tuple[Optional[str], str]]) -> Dict[str, Any]: children: Dict[str, Any] = {o: {} for _, o in data} tree: Dict[str, Any] = {} for parent, offspring in data: if parent is None: tree[offspring] = children[offspring] else: children[parent][offspring] = children[offspring] return treeИ отправляю ему этот код. На что chatGPT замечает, что такое решение лучше и чуть ли не хвалит меня. Спасибо, конечно, chatGPT, но давай уж тогда работать дальше. После того, как этот сложный для задачи момент мы совместными усилиями решили, а моя спесь ушла, работа пошла гораздо легче.
Попросил написать тесты — он написал несколько неплохих. Попросил написать тесты с неформатными входными данными — тоже напридумывал кое-что. Попросил обновить решение, чтобы тесты с неформатными входными данными проходили — он снова дописал блоки кода. То же самое мы с ним провернули с разными другими пограничными условиями. Конечно, что-то приходилось ему подправлять по-дружески. Мы ж друзья стали. Ну и в конце попросил его подробно описать алгоритмическую сложность по времени и по памяти, с чем он тоже справился.
Конечный исходный код
from typing import List, Tuple, Dict, Optional, Any # Time complexity: # The time complexity of this function is O(n), where n is the number of tuples in the input list. The reason is that # the function iterates over the input list once and performs a constant number of # operations (a constant number of type and value comparisons) on each element of the list. Therefore, # the total number of operations is directly proportional to the number of elements in the list, which makes # the time complexity O(n). # # Space complexity: # The space complexity of this function is O(n). The reason is that the function creates two data structures: tree and # children both with the same size as the number of tuples in the input list, to store the tree and # children of the each node. Therefore, the space complexity is directly proportional to the number of # elements in the input list, which makes the space complexity O(n). def to_tree(data: List[Tuple[Optional[str], str]]) -> Dict[str, Any]: if not data: return {} if not isinstance(data, list): raise ValueError("Input data must be a list") if not all(map(lambda x: isinstance(x, tuple), data)): raise ValueError("Input data must be a list of tuples") if not all(map(lambda x: len(x) == 2, data)): raise ValueError("Each tuple in input data must have exactly two elements") if not all(map(lambda x: (isinstance(x[0], str) or x[0] is None) and isinstance(x[1], str), data)): raise ValueError("Parent and offspring must be of type str, parent can be None") check_offspring_duplicates(data) children: Dict[str, Any] = {o: {} for _, o in data} tree: Dict[str, Any] = {} for parent, offspring in data: if parent is None: tree[offspring] = children[offspring] else: children[parent][offspring] = children[offspring] return tree # Time complexity of this function is O(n) as it also iterates over the input list once, and does a constant number of # dictionary operations on each iteration, where n is the number of tuples in the input list. # # Space complexity of this function is O(n) too, where n is the number of unique offsprings in the input data, because # it's creating a dictionary to store the count of each offspring and the size of the dictionary will be equal to the # number of unique offsprings in the input data. def check_offspring_duplicates(data: List[Tuple[Optional[str], str]]): offspring_count = {} for _, offspring in data: if offspring in offspring_count: offspring_count[offspring] += 1 raise ValueError(f"Offspring {offspring} appears more than once in the input data") else: offspring_count[offspring] = 1 # Tests def test_to_tree(): source = [ (None, 'a'), (None, 'b'), (None, 'c'), ('a', 'a1'), ('a', 'a2'), ('a2', 'a21'), ('a2', 'a22'), ('b', 'b1'), ('b1', 'b11'), ('b11', 'b111'), ('b', 'b2'), ('c', 'c1'), ] expected = { 'a': {'a1': {}, 'a2': {'a21': {}, 'a22': {}}}, 'b': {'b1': {'b11': {'b111': {}}}, 'b2': {}}, 'c': {'c1': {}}, } assert to_tree(source) == expected def test_to_tree_with_invalid_inputs(): # Test with empty input assert to_tree([]) == {} # Test with non-tuple input try: to_tree(['a', 'b']) except ValueError as v: assert str(v) == "Input data must be a list of tuples" else: assert False # Test with tuple input with wrong number of elements try: to_tree([(None,), ('a', 'b', 'c')]) except ValueError as v: assert str(v) == "Each tuple in input data must have exactly two elements" else: assert False def test_input_type(): # Test input with non-string parent and offspring try: to_tree([(None, 1), (1, 2)]) except ValueError as v: assert str(v) == "Parent and offspring must be of type str, parent can be None" else: assert False try: to_tree([(None, '1'), ('1', 2)]) except ValueError as v: assert str(v) == "Parent and offspring must be of type str, parent can be None" else: assert False try: to_tree([(None, None)]) except ValueError as v: assert str(v) == "Parent and offspring must be of type str, parent can be None" else: assert False # Test input with string parent and offspring assert to_tree([(None, '1'), ('1', '2')]) == {'1': {'2': {}}} def test_duplicate_nodes(): try: to_tree([(None, '1'), ('1', '2'), ('1', '2')]) except ValueError as v: assert str(v) == "Offspring 2 appears more than once in the input data" else: assert False try: to_tree([(None, '1'), ('1', '2'), ('2', '2')]) except ValueError as v: assert str(v) == "Offspring 2 appears more than once in the input data" else: assert False test_to_tree() test_input_type() test_to_tree_with_invalid_inputs() test_duplicate_nodes() Остались последние штрихи, но тут chatGPT устал — слишком много запросов в час, так и сказал.
Что ж, в таком виде я решение и отправил работодателю. Жду теперь ответа.
В итоге опыт получился интересным и, как мне кажется, chatGPT может стать хорошим инструментом в помощь разработчику, он может брать на себя какие-то тривиальные и рутинные операции на своем уровне абстракции, а самому разработчику придется учиться четче ставить задачи, ревьюить код и выстраивать архитектуру.
ссылка на оригинал статьи https://habr.com/ru/post/710169/
Добавить комментарий