0

Daily Challenge #47

Witaj! Kolejny dzień, kolejne zadanie.

  • Zadanie numer: #47
  • Autor: Google
  • Trudność: 2/5
  • Główny problem: rekurencja, dziel i zwyciężaj
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ę ani refaktoryzuję kodu, 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. Pamiętaj, że implementacje przedstawione w ramach tego cyklu nie nadają się do kodu produkcyjnego, traktuj to bardziej jako ‘proof of concept’.

Treść

Given pre-order and in-order traversals of a binary tree, write a function to reconstruct the tree.
For example, given the following preorder traversal:
[a, b, d, e, c, f, g]
And the following inorder traversal:
[d, b, e, a, f, c, g]
You should return the following tree:
a
….left: b
……..left: d
……..right: e
….right: c
……..left: f
……..right: g

Implementacja: testy

[TestMethod]
public void DailyChallenge47()
{
    DailyChallenge47 daily = new DailyChallenge47();
    Node root = daily.Proceed(new char[] { 'a', 'b', 'd', 'e', 'c', 'f', 'g' }, new char[] { 'd', 'b', 'e', 'a', 'f', 'c', 'g' });
    Assert.IsNotNull(root);
    Assert.AreEqual('a', root.Value);
 
    Assert.IsNotNull(root.Left);
    Assert.AreEqual('b', root.Left.Value);
 
    Assert.IsNotNull(root.Right);
    Assert.AreEqual('c', root.Right.Value);
 
    Assert.IsNotNull(root.Left.Left);
    Assert.AreEqual('d', root.Left.Left.Value);
 
    Assert.IsNotNull(root.Left.Right);
    Assert.AreEqual('e', root.Left.Right.Value);
 
    Assert.IsNotNull(root.Right.Left);
    Assert.AreEqual('f', root.Right.Left.Value);
 
    Assert.IsNotNull(root.Right.Right);
    Assert.AreEqual('g', root.Right.Right.Value);
}

Implementacja: algorytm

public class Node
{
    public Node Left;
    public Node Right;
    public char Value;
}
 
public Node Proceed(char[] preorder, char[] inorder)
{
    if (preorder.Length != inorder.Length)
    {
        throw new ArgumentException();
    }
    Node root = new Node();
    if(ProceedIntern(root, preorder.ToList(), inorder.ToList()))
    {
        return root;
    }
    return null;
}
 
public bool ProceedIntern(Node current, List<char> preorder, List<char> inorder)
{
    if (inorder.Any() == false)
    {
        return false;
    }
    current.Value = preorder[0];
    if (inorder.Count == 2)
    {
        current.Left = new Node() { Value = preorder[1] };
    }
    else if (inorder.Count == 3)
    {
        current.Left = new Node() { Value = preorder[1] };
        current.Right = new Node() { Value = preorder[2] };
    }
    else
    {
        int index = inorder.IndexOf(current.Value);
        if (index < 0)
        {
            throw new InvalidOperationException();
        }
        Node left = new Node();
        if (ProceedIntern(left, preorder.Skip(1).ToList(), inorder.Take(index).ToList()))
        {
            current.Left = left;
        }
        Node right = new Node();
        if (ProceedIntern(right, preorder.Skip(index + 1).ToList(), inorder.Skip(index + 1).ToList()))
        {
            current.Right = right;
        }
    }
    return true;
}

Mission Completed

Zadanie mogło się wydawać na pierwszy rzut oka trudne, ale w rzeczywistości nie było tak źle.

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.