0

Daily Challenge #32

Witaj! Kolejny dzień, kolejne zadanie.

  • Zadanie numer: #32
  • Autor: Microsoft
  • Trudność: 1/5
  • Główny problem: wyznaczanie mediany (statystyka)
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ść

Compute the running median of a sequence of numbers. That is, given a stream of numbers, print out the median of the list so far on each new element.
Recall that the median of an even-numbered list is the average of the two middle numbers.
For example, given the sequence [2, 1, 5, 7, 2, 0, 5], your algorithm should print out: [2, 1.5, 2, 3.5, 2, 2, 2].

Implementacja: testy

[TestMethod]
public void DailyChallenge32()
{
    DailyChallenge32 daily = new DailyChallenge32();
    float[] result = daily.Proceed(new int[] { 2, 1, 5, 7, 2, 0, 5 });
    float[] expected = new float[] { 2, 1.5f, 2, 3.5f, 2, 2, 2 };
    CollectionAssert.AreEqual(expected, result);
}

Implementacja: algorytm

public float[] Proceed(int[] numbers)
{
    List<float> result = new List<float>();
    List<int> listOfNumbers = new List<int>();
    foreach(int number in numbers)
    {
        listOfNumbers.Add(number);
        listOfNumbers.Sort();
        if (listOfNumbers.Count % 2 == 0)
        {
            // even
            float res = (listOfNumbers[listOfNumbers.Count/2 -1] + listOfNumbers[listOfNumbers.Count / 2]) / 2f;
            result.Add(res);
        }
        else
        {
            result.Add(listOfNumbers[listOfNumbers.Count / 2]);
        }
    }
    return result.ToArray();
}

Mission Completed

Szybko poszło. Miło po tych poprzednich zadaniach w końcu dostać coś łatwiejszego :D. Główny problem polegał chyba na niepomyleniu mediany ze średnią ;).

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.