Nasza strona używa cookies. Korzystając ze strony, wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki. Rozumiem

Jak uprościć kod i lepiej wypaść na rozmowie technicznej

Tuan Nhu Dinh Software Engineer / Facebook
Poznaj metodę, która nie tylko pozwoli Ci uprościć kod i lepiej wypaść na rozmowie technicznej, ale może się również przydać w późniejszej karierze.
Jak uprościć kod i lepiej wypaść na rozmowie technicznej

Artykuł ten jest częścią mojej serii pt. „15-dniowa ściąga do rozmów technicznych u technicznych gigantów”. Tutaj omówimy, w jaki sposób technika przesuwanego okna (ang. sliding window technique) może pomóc w uproszczeniu kodu i zredukowaniu złożoności czasowej. 

Przykładowe pytanie nr. 1

Zacznijmy od następującego pytania:

Given an array of integers and a number k.
Return the highest sum of any k consecutive elements in the array.

Examples:
Input: arr = [1, 5, 2, 3, 7, 1], k = 3
Output: 12 (the sum of subarray [2, 3, 7])

Input: arr = [5, -3, 7, -6, 8], k = 2
Output: 4 (the sum of subarray [-3, 7])

Input: arr = [5, -3, 7, -6, 8], k = 3
Output: 9 (the sum of subarray [5, -3, 7] or [7, -6, 8])


Metoda „na siłę” (ang. Brute Force Approach)

Najbardziej intuicyjnym sposobem jest tutaj znalezienie wszystkich możliwych podtablic k elementów, zsumowanie ich i porównanie. Metoda ta wymaga zagnieżdżonej pętli for. Zewnętrzna pętla for wykonuje iterację po początkowym indeksie podtablicy, a zagnieżdżona pętla oblicza sumę podtablicy.

def highestSum(arr, k):
    highest_sum = float('-inf')
    n = len(arr)

    # n must not be smaller than k
    if n < k:
        return -1

    # subarray starts at i
    for i in range(n - k + 1):
        # calculate sum of the subarray
        current_sum = 0
        for j in range(k):
            current_sum += arr[i + j]
        # compare the sum
        highest_sum = max(highest_sum, current_sum)
    return highest_sum


Złożoność czasowa wynosi O(k*n), ponieważ zawiera dwie zagnieżdżone pętle. Przechodzenie przez podtablicę za każdym razem, kiedy chcemy obliczyć sumę, jest bardzo nieefektywne, więc jeśli chcemy poprawić wydajność, potrzebujemy szybszej metody, aby znaleźć sumę.


Technika przesuwanego okna

Na pewnej części danych jest tworzone okno, które można po nich przesuwać, aby uchwycić różne ich części. Kiedy okno się przesuwa, zmieniają się tylko dwa elementy. Najstarszy odpada, a najnowszy pojawia się w ramie.


W przypadku metody „na siłę” nieefektywne jest to, że dla dowolnych dwóch kolejnych podtablic o rozmiarze k, nakładająca się część (która zawiera elementy k-1) jest przeliczana dwukrotnie. Korzystając z metody przesuwanego okna, możemy się tego pozbyć i obliczyć sumę w O(1), używając sumy poprzedniej podtablicy, która była następna w kolejności.

def highestSum(arr, k):
    highest_sum = float('-inf')
    n = len(arr)

    # n must not be smaller than k
    if n < k:
        return -1

    # Compute sum of first window of size k
    window_sum = sum([arr[i] for i in range(k)])

    # Compute sums of remaining windows by 
    # removing first element of previous 
    # window and adding last element of 
    # current window. 
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        highest_sum = max(highest_sum, window_sum)

    return highest_sum


Technikę przesuwanego okna można również implementować z dwoma wskaźnikami: lewym i prawym:

def highestSum(arr, k):
    highest_sum = float('-inf')
    n = len(arr)

    # n must be not smaller than k
    if n < k:
        return -1

    left = 0
    right = 0
    window_sum = 0
    while right < n:
        # sliding the window to the right
        window_sum += arr[right]
        right += 1

        # check the window size condition and compare the sum
        # drop off the left element to avoid oversize
        if right-left == k:
            highest_sum = max(highest_sum, window_sum)
            window_sum -= arr[left]
            left += 1

    return highest_sum


Złożoność czasowa O(n) jest teraz liniowa, ponieważ potrzebujemy tylko jednej pętli.


Przykładowe pytanie nr. 2

Przyjrzyjmy się następnemu pytaniu:

Given a string, find the length of the longest substring without repeating characters.
Full description at https://leetcode.com/problems/longest-substring-without-repeating-characters/

Examples:
Input: "pwwkew"
Output: 3 (the substring "wke" or "kew")

Input: "abcabcbb"
Output: 3 (the substring "abc" or "bca" or "cab")

Input: "bbbbb"
Output: 1 (the substring "b")


Metoda „na siłę”

Podejście naiwne to sprawdzanie wszystkich podciągów znaków jeden po drugim i znajdowanie najdłuższego, którego wszystkie znaki są unikalne.

def longest_unique_substring(s):
    # function to check if the characters in the substring are all unique or not
    def is_all_unique(start_index, end_index):
        character_set = set()
        for z in range(start_index, end_index):
            if s[z] in character_set:
                return False
            character_set.add(s[z])
        return True

    longest_length = float('-inf')
    n = len(s)

    # empty string has 0 substring
    if n == 0:
        return 0

    # enumerate all substrings [i, j)
    for i in range(n):
        for j in range(i + 1, n + 1):
            # if the characters in the substring are all unique, compare the length.
            if is_all_unique(i, j):
                longest_length = max(longest_length, j - i)

    return longest_length


Złożoność czasowa wynosi O(n³), ponieważ potrzebujemy O(n²), aby wylistować wszystkie podciągi znaków, a dla każdego z nich potrzebujemy O(n), aby sprawdzić, czy wszystkie znaki są unikalne.


Technika przesuwanego okna

Przy metodzie „na siłę”, dla każdego podciągu znaków potrzebujemy O(n), aby sprawdzić, czy wszystkie znaki są unikalne. Używając tablicy mieszającej (ang. hash map) jako okna do zapisywania liczby wystąpień znaków, możemy zbadać Sᵢⱼ, sprawdzając, czy znak j w oknie jest [i, j-1], czy nie. A do tego potrzebujemy jedynie O(1).

Ponadto nie musimy sprawdzać wszystkich podciągów znaków. Możemy zacząć od indeksu 0, przesuwając się w prawo, o ile znaki w podłańcuchu są nadal unikalne. Jeśli napotkamy powtarzający się element, możemy zostawić kilka lewych znaków, aby znów stały się unikalne.

from collections import defaultdict

def longest_unique_substring(s):
    longest_length = float('-inf')
    n = len(s)

    # empty string has the longest length is 0
    if n == 0:
        return 0

    left = 0
    right = 0
    window = defaultdict(int)
    while right < n:
        # sliding the window to the right
        right_character = s[right]
        window[right_character] += 1
        right += 1

        # if a duplicate character appears in the window
        # drop off the left elements until we have valid condition again
        while window[right_character] > 1:
            window[s[left]] -= 1
            left += 1
        longest_length = max(longest_length, right - left)

    return longest_length


Złożoność czasowa wynosi O(2n)=O(n), ponieważ w najgorszym przypadku każdy znak zostanie odwiedzony dwukrotnie po lewej i po prawej stronie.


Z czym można ćwiczyć

Możesz ćwiczyć technikę przesuwanego okna z następującymi pytaniami:


Podsumowanie

Potęga zastosowania przesuwnego okna polega na zapobieganiu niepotrzebnym iteracjom po kolekcji. Gdy zostaniesz poproszony o znalezienie lub obliczenie czegoś spośród wszystkich przyległych podtablic (lub podlist), to może to oznaczać, że chcą, abyś użył właśnie takiego podejścia. 

W niektórych przypadkach rozmiar przesuwanego okna nie jest z góry ustalony (np. w przykładowym pytaniu 2) i trzeba rozszerzyć lub zmniejszyć okno w oparciu o ograniczenia problemu.

Abstrakcyjny kod techniki przesuwanego okna można podsumować w następujący sposób:

left = 0
right = 0

while right < n:
window.add(s[right])
right += 1


while (condition):
window.remove(s[left])
left += 1


Oryginał tekstu w języku angielskim możesz przeczytać tutaj.

Nie przegap treści Bulldogjob
Subskrybuj artykuły

Lubisz dzielić się wiedzą i chcesz zostać autorem?

Podziel się wiedzą z 160 tysiącami naszych czytelników

Dowiedz się więcej