0

Daily Challenge #39

Witaj! Kolejny dzień, kolejne zadanie.

  • Zadanie numer: #39
  • Autor: Google
  • Trudność: 4/5
  • Główny problem: operacje bitowe
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 an array of integers where every integer occurs three times except for one integer, which only occurs once, find and return the non-duplicated integer.
For example, given [6, 1, 3, 3, 3, 6, 6], return 1. Given [13, 19, 13, 13], return 19.
Do this in O(N) time and O(1) space.

Implementacja: test

[TestMethod]
public void DailyChallenge39()
{
    DailyChallenge39 daily = new DailyChallenge39();
    Assert.AreEqual(19, daily.Proceed(new[] { 13, 13, 19, 13 }));
    Assert.AreEqual(1, daily.Proceed(new[] { 6, 1, 3, 3, 3, 6, 6 }));
    Assert.AreEqual(-3, daily.Proceed(new[] { -2, -2, -2, 1, 1, 1, -3 }));
    Assert.AreEqual(int.MaxValue, daily.Proceed(new[] { int.MinValue, int.MinValue, int.MinValue, int.MaxValue}));
    Assert.AreEqual(int.MinValue, daily.Proceed(new[] { int.MaxValue, int.MaxValue, int.MinValue, int.MaxValue }));
    Assert.AreEqual(int.MinValue + 1, daily.Proceed(new[] { int.MaxValue, int.MaxValue, int.MinValue+1, int.MinValue, int.MaxValue, int.MinValue, int.MinValue }));
}

Implementacja: algorytm

public int Proceed(int[] input)
{
    // size of int in C#
    int maxBits = 32;
    int result = 0;
    for (int i = 0; i< maxBits;++i)
    {
        int sum = 0;
        int current = (1 << i);
        foreach (int value in input)
        {
            if ((value & current) == 0)
            {
                sum++;
            }
        }
        if ((sum % 3) == 0)
        {
            result |= current;
        }
    }
    return result;
}

Mission Completed

Uff… łatwo nie było. Google bardzo lubi dawać banalne zadania, ograniczając złożoność algorytmów do minimum, co powoduje, że zadanie już takie banalne nie są. Dzisiaj kluczem były operacje bitowe, z racji, że nie jest to moja najmocniejsza strona, to 4 gwiazdki. Osoby programujące w językach niskiego poziomu pewnie łatwiej by sobie poradziły z takim zadaniem.

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.