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:
- Minimalny podciąg znaków okna
- Max Consecutive Ones III
- Najdłuższy podciąg znaków z największą liczbą k unikalnych znaków
- Najdłużej powtarzające się substytuty znaków
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.