LINUX.ORG.RU

тесты с сайта hackerrank и собственный тест показывают разные результаты

 , ,


1

2

Может ли быть, что отдельные тесты на сайте hackerrank составлены некорректно?

Задача с сайта. Проверить является ли дерево binary search tree. Если не является, то ответ False.

Все тесты с сайта, которые проверяют ответ False показывают, что у моя ф. дает ответ True.

Спецально была написана фнукция, которая формирует дерево в проивольном порядке, т.е. оно не binary search tree. После этого ф. которая проверяет такое дерево, проверялась моим собственым тестом и ответ постоянно False, т.е. такой какой и требуется.

Мне на первый взгляд непонятно, что у меня не так написано. Может, кто подскажет?

    def __comp__(self):
        l = self.left
        r = self.right
        if l and r:
            if l.right:
                extra = l.right
                if extra and not extra.data.__lt__(self.data) and not extra.data.__lt__(r.data):
                    return False, 'NO'
            return l.data.__lt__(self.data) and r.data.__gt__(self.data), 'LR'
        elif l:
            return l.data.__lt__(self.data), 'L'
        elif r:
            return r.data.__gt__(self.data), 'R'
        elif not r and not l:
            return True, 'END'

 def check_binary_search_tree_(root):
    nodes = root.__comp__()
    if not nodes[0]: return False
    dic = dict()
    if 'L' in nodes[1]: dic[root.left] = 'lwing'
    if 'R' in nodes[1]: dic[root.right] = 'rwing'

    while dic:
        new_dic = dict()
        for node in dic:
            nodes = node.__comp__()
            if not nodes[0]: return False
            if 'R' in nodes[1]:
                new_dic[node.right] = dic[node]
                if new_dic[node.right] == 'lwing' and not node.right.__lt__(root):
                    return False
            if 'L' in nodes[1]:
                new_dic[node.left] = dic[node]
                if new_dic[node.left] == 'rwing' and not node.left.__gt__(root):
                    return False
        dic = new_dic
    return True


def Checker(tree, func):
    assert func(tree)==False
    return 'OK'


print(Checker(form_tree(ls),check_binary_search_tree_))

 

На самом деле тот сайт полная херня. Помню как светились мои глаза когда я там только зарегистрировался. Но по факту даже не проверяют корректность, только результат на ожидаемых вводных, и куча унылых искусственных задач.

anonymous ()
Ответ на: комментарий от anonymous

а есть информация, кто эти тесты составляет и проверяет их корректность? Hackerrank - коммерческая компания со штаб-квартирой в Калифорнии. В компании, очевидно, есть штатные программисты. Насколько понимаю, задачи в разделе practice придумывают сами участники и выкладывают.

hibiscusM ()

Может ли быть, что отдельные тесты на сайте hackerrank составлены некорректно?

Может, конечно. Их же люди делали.

Мне на первый взгляд непонятно, что у меня не так написано. Может, кто подскажет?

А фиг его, очень странная реализация. Может, оно теоретически и работоспособно, но понять трудно. Судя по какой-то проверке с корнем, а не со всеми промежуточными родителями, то скорее всего в коде что-то не так.

P.S. Интересно, есть ли десктопный аналог подобных сайтов, т.е. чтобы база задач с тестами была локальной и никуда ничего не отправлялось...

xaizek ★★★★★ ()
Ответ на: комментарий от xaizek

проверка с промежуточным родителем происходит в __comp__ и далее если возвращается True, то идет проверка с корнем уже в самой фукнции (может проверка с корнем и не нужна, но хуже не сделает-то?)

А можно подробнее, что еще кажется странным?

hibiscusM ()

Зачем так сложно? Можно же рекурсивно проверить свойство bst. Для каждого узла ключ левого потомка должен быть меньше ключа узла, а ключ правого потомка должен быть больше ключа узла. Потомки тоже должны быть bst:

def bst(node):
    if node.left:
        if node.left.key >= node.key:
            return False
        if not bst(node.left):
            return False
    if node.right:
        if node.right.key <= node.key:
            return False
        if not bst(node.right):
            return False
    
    return True

И зачем ты вызываешь методы типа __gt__? Они как раз и нужны, чтобы можно было просто сравнивать, с помощью <, = и >.

i-rinat ★★★★★ ()
Последнее исправление: i-rinat (всего исправлений: 1)
Ответ на: комментарий от hibiscusM

проверка с промежуточным родителем происходит в __comp__

С одним из, а не со всеми. Пример, который, как мне кажется, вернёт True, а не False:

         10
        /
       5
        \
         8
        /
       2

А можно подробнее, что еще кажется странным?

Подход в целом. Много проверок и они все проверяют локальные/частные свойства, хотя возможные значения узла определяются всеми его родителями. Проверяя только одного, толку не будет. Нужно либо как-нибудь аккумулировать информацию о всех родителях и сравнивать с ней, либо проверять всех родителей (это медленней, понятно).

xaizek ★★★★★ ()
Ответ на: комментарий от hibiscusM

Для рекурсивных структур ты так или иначе будешь эмулировать стек. Если ожидаемая глубина рекурсии ограничена сверху, то почему бы сразу в рекурсивном виде на написать?

i-rinat ★★★★★ ()