0

Daily Challenge #23

Witaj! Dzisiaj dosyć ciekawe zadanie od Google, zapraszam do czytania i rozwiązywania.

  • Zadanie numer: #23
  • Autor: Google
  • Trudność: 2/5
  • Główny problem: drzewo binarne
Wpis ten należy do cyklu Daily Challenge. Od poniedziałku do piątku, codziennie, o 7:30 publikuję rozwiązanie jednego zadania. Zadania rozwiązywane w ramach tego cyklu są zadaniami przeznaczonymi na rozmowy kwalifikacyjne. Są treściwe, krótkie i wymagają jakichś konkretnych umiejętności. Przedstawione problemy realizuję właśnie w ten sposób. Nie wymyślam najlepszego algorytmu, nie optymalizuję kodu do granic możliwości, tylko implementuję pierwszą myśl. Robię to dla zabawy i chęci sprawdzenia swoich możliwości. Zaimplementowane rozwiązanie nie jest z reguły tłumaczone, jeżeli masz pytania możesz je zadawać w komentarzach. Wszystkie zadania udostępniane są subskrybentom Daily Coding Problem. Moje implementacje (również tego zadania) dostępne są na GitHubie.

Treść

Implement locking in a binary tree. A binary tree node can be locked or unlocked only if all of its descendants or ancestors are not locked.
Design a binary tree node class with the following methods:

  •  is_locked, which returns whether the node is locked
  • lock, which attempts to lock the node. If it cannot be locked, then it should return false. Otherwise, it should lock it and return true.
  • unlock, which unlocks the node. If it cannot be unlocked, then it should return false. Otherwise, it should unlock it and return true.

You may augment the node to add parent pointers or any other property you would like. You may assume the class is used in a single-threaded program, so there is no need for actual locks or mutexes. Each method should run in O(h), where h is the height of the tree.

Implementacja: testy

[TestMethod]
public void DailyChallenge23()
{
    Node root = new Node();
    Node left_0 = new Node() { Parent = root };
    Node right_0 = new Node() { Parent = root };
    root.Left = left_0;
    root.Right = right_0;
    Node right_1_0 = new Node() { Parent = right_0 };
    Node right_1_1 = new Node() { Parent = right_0 };
    right_0.Left = right_1_0;
    right_0.Right = right_1_1;
    Node right_2_1 = new Node() { Parent = right_1_1 };
    right_1_1.Right = right_2_1;
 
    Assert.IsTrue(right_2_1.Lock());
    Assert.IsTrue(right_2_1.IsLocked());
    Assert.IsFalse(right_1_1.Lock());
    Assert.IsFalse(root.Lock());
    Assert.IsTrue(right_2_1.Unlock());
 
    Assert.IsTrue(left_0.Lock());
    Assert.IsTrue(right_2_1.Lock());
    Assert.IsFalse(root.Lock());
    Assert.IsTrue(left_0.Unlock());
    Assert.IsFalse(root.Lock());
    Assert.IsTrue(right_2_1.Unlock());
    Assert.IsTrue(root.Lock());
}

Implementacja: algorytm

public class Node
{
    private bool _locked;
 
    public Node Parent { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
 
    private Guid _id = Guid.NewGuid();
    private List<Guid> _lockedBy = new List<Guid>();
 
    public bool IsLocked()
    {
        return _locked;
    }
 
    public bool Lock()
    {
        if (_locked || _lockedBy.Any())
        {
            return false;
        }
        Node parent = Parent;
        while(parent != null)
        {
            if (parent._locked)
            {
                return false;
            }
            parent = parent.Parent;
        }
        // We can lock
        parent = Parent;
        while (parent != null)
        {
            parent._lockedBy.Add(_id);
            parent = parent.Parent;
        }
        _locked = true;
        return true;
    }
 
    public bool Unlock()
    {
        if (_locked == false || _lockedBy.Any())
        {
            return false;
        }
        Node parent = Parent;
        while (parent != null)
        {
            if (parent._locked)
            {
                return false;
            }
            parent = parent.Parent;
        }
        // We can unlock
        parent = Parent;
        while (parent != null)
        {
            parent._lockedBy.Remove(_id);
            parent = parent.Parent;
        }
        _locked = false;
        return true;
    }
}

Mission Completed

Kolejne zadanie od Google, tym razem dosyć łatwe. Pozwolili trzymać dowolne dane, to można trzymać obiekty, które nas blokują, nie ;)? Maksymalna złożoność obliczeniowa to O(2*h), czyli O(h).

Jeżeli Ty chciałbyś podesłać jakieś ciekawe zadanie, to nie krępuj się proszę i ślij na p.bogdanski@devmight.pl. Pamiętaj, że zadanie powinno nadawać się na rozmowę kwalifikacyjną, więc nie może to być problem, którego rozwiązanie zajmuje kilka godzin. Dzięki!

Pozdro!

Patryk Bogdański

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

This site uses Akismet to reduce spam. Learn how your comment data is processed.