13 czerwca 2016

Zadanie rekrutacyjne #3

Znajdź referencje do obiektu w pythonie

Zaimplementuj funkcję w języku Python, która policzy, ile jest elementów w liście jednokierunkowej. Argumentem funkcji jest dowolny element tej listy.

class Node:
   def __init__(self, data, next):
      self.data = data
      self.next = next

def CountNodes( node ):
    pass #Implement me

def main():
    n5 = Node("5", None)
    n4 = Node("4", n5)
    n3 = Node("3", n4)
    n2 = Node("2", n3)
    n1 = Node("1", n2)

    print('Total number of elements: {}'.format(CountNodes(n1)))
    print('Total number of elements: {}'.format(CountNodes(n3)))
    print('Total number of elements: {}'.format(CountNodes(n5)))

if __name__ == "__main__":
    main()

Rozwiązanie

Potrzebujemy sprawdzić odległość pomiędzy wskazanym węzłem i końcem oraz początkiem listy. Suma tych dwóch wartości da nam oczekiwany wynik. Niestety, węzeł listy nie zawiera referencji do poprzedniego elementu (lista jednokierunkowa). Aby poznać referencje do poprzedniego elementu, musimy poprosić o pomoc środowisko uruchomieniowe.

Odległość do końca łatwo uzyskać.

def GetDistanceToEnd(node):
    result = 0
    while node.next:
        result += 1
        node = node.next
    return result

def GetDistanceFromStart(node):
    return 0 #implement me

def CountNodes( node ):
    return GetDistanceFromStart(node) + GetDistanceToEnd(node) + 1

Aby poznać natomiast odległość od początku listy, musimy zapytać GC o referencje do naszego obiektu.

import gc

def get_prev_node(nodeArg):
    result = [a for a in gc.get_objects() if type(a) is Node and a.next == nodeArg]
    if len(result) == 0:
        return None
    if len(result) > 1:
        raise "Exception List structure problem"
    return result[0]

def GetDistanceFromStart(node):
    result = 0
    prev = get_prev_node(node)
    while prev:
        result += 1
        prev = get_prev_node(prev)
    return result

def CountNodes( node ):
    gc.disable()
    result = GetDistanceFromStart(node) + GetDistanceToEnd(node) + 1
    gc.enable()
    return result

Na czas naszej pracy wyłączamy GC. Następnie pobieramy listę wszystkich obiektów, których czas życia jest kontrolowany przez GC, filtrujemy je po typie i szukamy takiego, który wskazuje na nasz węzeł listy.

Uwaga

Aby powyższy fragment kodu zadziałał, lista musi być poprawna. Powyższa metoda podana jest jako ciekawostka. Nie stosujcie jej na produkcji. Źródło (opens new window)