Ето как ChatGPT вместо мен реши теста по програмиране в интервюто за започване на работа

Оригиналът е на Mamont

От началото на годината активно започнах да си търся нова работа и провеждам предварителни онлайн интервюта, в които понякога работодателите ми изпращат тестови задачи, преди да ме поканят на реално интервю. Предишния път ми изпратиха да намеря решение на класическата задача от списъка с върхове да бъде изградена дървовидна структура от данни. Ето как изглежда заданието:

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 бързо написа отговора, при това с коментари и обяснения.

Първото решение:

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]
            )

На пръв поглед изглежда доста правдоподобно, някои моменти са смущаващи, но това си е немалко сорс код. Стартирах го в средата на 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, използвайки неговия собствен съвет за използването на специализирани структури от данни.

Ето го моят код:

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 веднага съобщи, че това решение е по-добро и без малко да ме похвали. Благодаря, разбира се, но нека да продължим нататък. След като този сложен момент на подадената задача отмина, ние със съвместни усилия съставихме необходимия сорс код. Моят песимизъм ме напусна и работата тръгна съвсем леко.

След това го помолих той да напише няколко тестови задачи от подобен род, но с нестандартни входни данни. Измисли някои неща. Помолих го да потърси други решения на неговите тестове, които да изискват по-оптимизирани отговори и той веднага подаде допълнителните уточняващи блокове сорс код. Същото направихме, когато реших да променя тези тестове с други гранични условия. Разбира се, налагаше се от време на време по приятелски да му пооправя някои грешки. Станахме приятели. Накрая го помолих подробно да опише алгоритмичната сложност разпределена по време и по заемана памет. Справи се перфектно.

Ето какъв се получи крайният много добре работещ код:

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

През изтеклите десетина дни примерите за използването на ChatGPT в програмирането прогресивно растат, като положителните отзиви  за неговата работа са многократно повече от отрицателните. Може да се каже, че този нов изкуствен интелект е поредното звено в развитието на програмирането. В началото програмистите пишеха код на най-ниско ниво – на асемблер, който се транслираше в машинен код, изпълняван от процесора. Сега разработчикът от новото по-високо ниво ще трябва да се научи да пише подробно техническо задание, което се преобразува в код на програмен език от високо ниво, който от своя страна се транслира в код от ниско ниво, който се преобразува в машинен код, изпълняван от процесора.

Но това не е като да пишеш на асемблер и е напредък нали? Интересно какво ще е следващото ниво в програмирането?