Usuwanie duplikatów — Zadanie rekrutacyjne #7

Czego szuka rekruter: znajomość HashSet<T>, złożoność O(n) vs O(n²), zachowanie kolejności
Poziom: Junior / Mid

Zadanie

Napisz funkcję, która usuwa duplikaty z tablicy lub listy i zwraca tylko unikalne elementy. Zachowaj kolejność pierwszego wystąpienia.

Czego szuka rekruter

To zadanie o wyborze właściwej struktury danych. HashSet<T> daje O(1) przy sprawdzaniu czy element już istnieje. Zagnieżdżona pętla daje O(n²). Rekruter patrzy:

• Czy kandydat zna HashSet<T> i wie dlaczego jest właściwy tutaj
• Czy zachowuje kolejność — HashSet nie gwarantuje porządku
• Czy zna LINQ Distinct() i rozumie kiedy go używać

Najczęstszy błąd: zagnieżdżona pętla O(n²) z Contains na liście. List<T>.Contains to O(n), więc cała operacja to O(n²).

❌ Naiwne rozwiązanie — O(n²)

static int[] RemoveDuplicatesNaive(int[] arr)
{
    var result = new List<int>();
    foreach (var item in arr)
    {
        if (!result.Contains(item))  // List.Contains = O(n) → całość O(n²)
            result.Add(item);
    }
    return result.ToArray();
}

✅ Optymalne rozwiązanie — O(n) z HashSet

static T[] RemoveDuplicates<T>(T[] arr)
{
    if (arr == null) throw new ArgumentNullException(nameof(arr));
    
    var seen = new HashSet<T>();
    var result = new List<T>(arr.Length);
    
    foreach (var item in arr)
    {
        if (seen.Add(item))  // HashSet.Add zwraca false jeśli element już istnieje
            result.Add(item);
    }
    
    return result.ToArray();
}

HashSet.Add robi dwie rzeczy naraz: sprawdza czy element istnieje (O(1) amortyzowane) i dodaje go jeśli nie istnieje. Zwraca true przy nowym elemencie, false przy duplikacie.

LINQ — Distinct()

static T[] RemoveDuplicatesLinq<T>(T[] arr)
    => arr?.Distinct().ToArray() ?? throw new ArgumentNullException(nameof(arr));

Distinct() wewnętrznie używa HashSet<T> — ta sama złożoność O(n), o wiele mniej kodu. W produkcji to poprawne podejście.

Gdy chcesz usunąć duplikaty obiektów po właściwości

record Product(int Id, string Name);

var products = new[]
{
    new Product(1, "Klawiatura"),
    new Product(2, "Mysz"),
    new Product(1, "Klawiatura"),  // duplikat
};

// Deduplikacja po Id:
var unique = products
    .GroupBy(p => p.Id)
    .Select(g => g.First())
    .ToArray();

// Lub z DistinctBy (NET 6+):
var unique2 = products.DistinctBy(p => p.Id).ToArray();

Testy jednostkowe

[Fact]
public void RemoveDuplicates_TypicalArray_PreservesOrder()
{
    var result = RemoveDuplicates(new[] { 3, 1, 2, 1, 3, 4 });
    Assert.Equal(new[] { 3, 1, 2, 4 }, result);
}

[Fact]
public void RemoveDuplicates_NoDuplicates_ReturnsSameElements()
{
    var result = RemoveDuplicates(new[] { 1, 2, 3 });
    Assert.Equal(new[] { 1, 2, 3 }, result);
}

[Fact]
public void RemoveDuplicates_AllSame_ReturnsSingleElement()
{
    var result = RemoveDuplicates(new[] { 5, 5, 5, 5 });
    Assert.Equal(new[] { 5 }, result);
}

[Fact]
public void RemoveDuplicates_Empty_ReturnsEmpty()
{
    var result = RemoveDuplicates(Array.Empty<int>());
    Assert.Empty(result);
}

Co powiedzieć na rozmowie

“List.Contains to O(n), więc zagnieżdżona pętla to O(n²). HashSet ma O(1) amortyzowane dla Add i Contains, więc całe usuwanie duplikatów to O(n). W produkcji użyłbym LINQ Distinct() lub DistinctBy() bo są czytelne i wewnętrznie robią to samo. HashSet bezpośrednio piszę gdy potrzebuję pełnej kontroli lub obsługi specjalnego przypadku.”

Podsumowanie