Как ChatGPT за меня тестовое задание для собеседования писал11.01.2023 22:16

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