Chcąc rozpocząć ścieżkę kariery jako programista Pythona w dobie AI, zastanawiałem się, jaki sens ma rozwiązywanie zadania „na kartce” podczas rekrutacji.
W tym artykule podzielę się z Wami zadaniem, z którym miałem styczność. Przejdziemy krok po kroku proces jego wytwarzania oraz poznamy kilka właściwości tego języka.
Jeżeli temat Was zaciekawił, zapraszam do przeczytania mojego poprzedniego artykułu utrzymanego w podobnej konwencji (Rekrutacja na Junior Python Developera – przykładowe zadanie techniczne).
Zadanie: wyszukiwanie tekstu w tekście
Na tapet bierzemy wyszukiwarkę – znajdowanie ciągu znaków w innym ciągu znaków, jednakże na wyjściu oczekujemy listy indeksów ciągu rozpoczynających pierwszy znak wyszukiwanego słowa.
Na potrzeby tego zadania uproszczę nazewnictwo: słowo to wyszukiwany ciąg znaków, zdanie to ciąg znaków, w którym wyszukujemy.
Poniżej przykładowe wywołanie funkcji z oczekiwanym wynikiem:
>>> search('aa', 'maakkaanaakka')
[1, 5, 8]
Do rozwiązania zadania użyłem Pythona w wersji 3.x.
Na pierwszy rzut oka zadanie wydaje się przystępne, szczególnie w czasach, gdy AI potrafi wygenerować poprawne rozwiązanie w kilka sekund. W praktyce podczas rozmowy technicznej często nie chodzi jednak o sam wynik, lecz o sposób analizy problemu, uzasadnianie decyzji i dostosowywanie rozwiązania do zmieniających się wymagań. Dlatego przejdźmy przez kolejne podejścia krok po kroku.
Podejście podstawowe
W związku z tym, że szukamy w stringach, które są typem wbudowanym, sprawdźmy, czy dokumentacja może rozwiązać za nas ten problem.
Na stronie docs.python.org znajdujemy rodzinę metod find. Niestety, rozwiązują one nasz problem tylko połowicznie, ponieważ zwracają tylko pierwsze wystąpienie słowa. Po dłuższej kontemplacji wnioskujemy, że dalsze kombinowanie w tym kierunku może przynieść oczekiwany rezultat, jednakże byłoby to co najmniej zagmatwane.
def search001(word, sentence):
"""
Return tha list of index of a substring found in string
>>> search001('aa', 'makkaanada')
[4]
>>> search001('ad', 'makkaanada')
[7]
>>> search001('an', 'makkaanada')
[5]
"""
return [sentence.find(word)]
Podejście ambitne – wyrażenie regularne
Wydaje się intuicyjne, że jeśli mamy znaleźć słowo w zdaniu, to jeśli zaprzęgniemy wyrażenie regularne (RegEx), sprawa będzie załatwiona. Importujemy odpowiednią bibliotekę i do dzieła.
Cytując klasyka:
Jeżeli chcesz rozwiązać swój problem za pomocą wyrażenia regularnego, to teraz masz dwa problemy: rozwiązanie zadania i stworzenie prawidłowego wyrażenia regularnego.
def search002(word, sentence):
"""
Return tha list of indexs of a substring found in string
>>> search002('aa', 'makkaanada')
[4]
>>> search002('ad', 'makkaanada')
[7]
>>> search002('an', 'makkaanada')
[5]
"""
return [re.search(word, sentence).span()[0]]
No i wszystko byłoby dobrze, gdybyśmy szukali tylko pierwszego wystąpienia słowa w zdaniu.
Po chwili wyszukiwania w ulubionym AI, wrzucając powyższy kod, dowiadujemy się dwóch rzeczy:
- pierwsza – primo: że jak najbardziej można to zadanie rozwiązać za pomocą wyrażenia regularnego,
- druga – primo: że dokumentacja tej funkcji to doctest – dokumentacja, którą można użyć do testowania działania funkcji.
Poniżej kod, zwracający wszystkie znalezione indeksy z odpowiadającymi im testami:
def search003(word: str, sentence: str) -> list:
"""
Return tha list of indexs of a substring found in string
>>> search003('aa', 'maakkaanaakka')
[1, 5, 8]
>>> search003('kk', 'maakkaanaakka')
[3, 10]
>>> search003('ak', 'maakkaanaakka')
[2, 9]
"""
return [match.start() for match in re.finditer(word, sentence)]
A może wykorzystamy właściwość języka Python?
Stringi w Pythonie mają możliwość podzielenia w locie zdania na „odcinki” o długości słowa i porównywania ich bezpośrednio.
def search004(word: str, sentence: str):
"""
Return tha list of indexes of a substring found in string
>>> search004('aa', 'maakkaanaakka')
[1, 5, 8]
>>> search004('kk', 'maakkaanaakka')
[3, 10]
>>> search004('ak', 'maakkaanaakka')
[2, 9]
"""
response = []
word_len = len(word)
for i in range(len(sentence) - word_len):
if (word == sentence[i:i+word_len]):
response.append(i)
return response
Plot twist – zmiana w wymaganiach
Wszystkie rozwiązania oparte na wyrażeniach regularnych lub funkcjach wbudowanych, takich jak 'str.find()’, wymagają przechowywania wyników w pamięci. W naszym przypadku nie jest to optymalne, ponieważ przeszukiwane teksty mogą mieć bardzo duże rozmiary, sięgające setek megabajtów, a nawet kilku gigabajtów. Dlatego zamiast zwracać listę wszystkich dopasowań, warto zwracać je w postaci generatora, który udostępnia wyniki na bieżąco i zużywa znacznie mniej pamięci.
W bardzo łatwy sposób możemy przekonwertować nasze ostatnie rozwiązanie.
def search005(word: str, sentence: str):
"""
Return tha list of indexes of a substring found in string
>>> list(search005('aa', 'maakkaanaakka'))
[1, 5, 8]
>>> list(search005('kk', 'maakkaanaakka'))
[3, 10]
>>> list(search005('ak', 'maakkaanaakka'))
[2, 9]
"""
word_len = len(word)
for i in range(len(sentence) - word_len):
if (word == sentence[i:i + word_len]):
yield i
Więcej optymalizacji, więcej optymalizacji!
Chcąc uzyskać jak największą wydajność i jak najprecyzyjniej odpowiedzieć na zadany problem, sprawdźmy, czy można go rozwiązać, adaptując powyższą metodę i wykorzystując wyłącznie porównania znaków.
Spróbujmy iterować po znaku z naszego zdania; jeżeli znak na danej pozycji jest równy z pierwszym znakiem słowa, porównujemy kolejne znaki słowa i zdania. Jak tylko znajdziemy znak, który nie pasuje, przechodzimy do następnego kroku w iteracji zdania.
def search006(word: str, sentence: str):
"""
Return a generator of indexs of a substring found in string
>>> list(search006('aa', 'maakkaanaakka'))
[1, 5, 8]
>>> list(search006('kk', 'maakkaanaakka'))
[3, 10]
>>> list(search006('ak', 'maakkaanaakka'))
[2, 9]
>>> list(search006('au', 'maakkaanaakka'))
[]
>>> list(search006('ana', 'maakkaanaakka'))
[6]
>>> list(search006('ana', 'maannakkaanaakka'))
[9]
"""
word_len = len(word)
for i in range(len(sentence) - word_len):
for j in range(word_len):
if (sentence[i+j] == word[j]):
if (j == word_len-1):
yield i
else:
break
Podsumujmy, co wiemy
- iteracja po tablicy elementów – funkcja `range`,
- ciąg znaków jest tablicą,
- użycie metody liczącej znaki w stringu,
- wycinanie elementów tablicy,
- wyrażenia regularne jako biblioteka,
- umiejętność tworzenia generatorów i ich użycia,
- znajomość techniki tworzenia testów w dokumentacji,
- umiejętność modyfikowania rozwiązania w sytuacji, gdy zmieniają się wymagania problemu.
Szkolenia z IT, biznesu i kompetencji miękkich
Ucz się od ekspertów wdrażających rozwiązania dla branżowych liderów.
Oferta szkoleniowaWnioski
Po przejściu przez kolejne wersje rozwiązania łatwiej zrozumieć, dlaczego podobne zadania nadal pojawiają się podczas rekrutacji. Nie sprawdzają one wyłącznie znajomości składni czy gotowych funkcji, ale przede wszystkim sposób myślenia, analizę kompromisów oraz umiejętność rozwijania rozwiązania wraz ze zmianą wymagań.
Kod naszych zmagań jest dostępny pod adresem GitHub.
Ciężko stwierdzić, czy wykazanie się taką wiedzą i umiejętnościami będzie wystarczające do zdobycia upragnionego stanowiska Python Developera.
Na pewno rozwiązanie zadania pokazuje umiejętności analityczne, podchodzenie do problemu z różnych perspektyw oraz znajomość i wiedzę z podstaw języka Python. A to nie zaszkodzi! Trenowanie na takich podstawowych przykładach, rozwijanie się oraz dokumentowanie kodu w repozytorium będą dodatkowym atutem.
Zostaw komentarz