0

Daily Challenge #25

Witaj!

  • Zadanie numer: #25
  • Autor: Google
  • Trudność: 2/5
  • Główny problem: optymalizacja przeszukiwania listy
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ść

Given a singly linked list and an integer k, remove the kth last element from the list. k is guaranteed to be smaller than the length of the list.
The list is very long, so making more than one pass is prohibitively expensive.
Do this in constant space and in one pass.

Implementacja: testy

[TestMethod]
public void DailyChallenge25()
{
    DailyChallenge25 daily = new DailyChallenge25();
    Node node400 = GenerateRandom(400);
    daily.Proceed(node400,100);
    int i = 0;
    while (node400 != null)
    {
        node400 = node400.Next;
        ++i;
    }
    Assert.AreEqual(300, i);
}
 
private Node GenerateRandom(int k)
{
    Node first = null;
    Node last = null;
    for(int i=0;i<k;++i)
    {
        Node newNode = new Node();
        if (last != null)
        {
            last.Next = newNode;
        }
        else
        {
            first = newNode;
        }
        last = newNode;
    }
    return first;
}

Implementacja: algorytm

public class Node
{
    public Guid ID = Guid.NewGuid();
    public Node Next;
}
 
public void Proceed(Node first, int kLast)
{
    Node node = first;
    Node remove = first;
    int k = 0;
    while (node != null)
    {
        if (k > kLast)
        {
            remove = remove.Next;
        }
        k++;
        node = node.Next;
    }
    // GC will do the rest
    remove.Next = null;
}

Mission Completed

Łatwe, przyjemne zadanie od Google. Nie ma co się rozwijać ;).

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.