Exercitii Avansate Python

Exercitiul 1: Aplatizare Lista Nested

Problema: Aplatizeaza o lista cu nivele multiple de imbricare.

def aplatizeaza(lista):
    rezultat = []
    for elem in lista:
        if isinstance(elem, list):
            rezultat.extend(aplatizeaza(elem))
        else:
            rezultat.append(elem)
    return rezultat

# Test
print(aplatizeaza([1, [2, 3], [4, [5, 6]]]))
# [1, 2, 3, 4, 5, 6]

Exercitiul 2: Deep Copy Manual

Problema: Implementeaza deep copy fara import.

def deep_copy(obj):
    if isinstance(obj, dict):
        return {k: deep_copy(v) for k, v in obj.items()}
    elif isinstance(obj, list):
        return [deep_copy(elem) for elem in obj]
    elif isinstance(obj, tuple):
        return tuple(deep_copy(elem) for elem in obj)
    elif isinstance(obj, set):
        return {deep_copy(elem) for elem in obj}
    else:
        return obj  # Imutabil

# Test
original = {"a": [1, 2], "b": {"c": 3}}
copie = deep_copy(original)
copie["a"].append(3)
print(original)  # {'a': [1, 2], 'b': {'c': 3}}

Exercitiul 3: Memoizare Fibonacci

Problema: Fibonacci cu memoizare pentru eficienta.

def fibonacci_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fibonacci_memo(n-1, cache) + fibonacci_memo(n-2, cache)
    return cache[n]

# Sau cu decorator
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# Test
print(fibonacci_memo(100))

Exercitiul 4: Parser de Paranteze

Problema: Verifica daca parantezele sunt echilibrate.

def paranteze_valide(s):
    stack = []
    perechi = {")": "(", "]": "[", "}": "{"}

    for c in s:
        if c in "([{":
            stack.append(c)
        elif c in ")]}":
            if not stack or stack.pop() != perechi[c]:
                return False
    return len(stack) == 0

# Test
print(paranteze_valide("([{}])"))   # True
print(paranteze_valide("([)]"))     # False
print(paranteze_valide("(("))       # False

Exercitiul 5: Generator de Permutari

Problema: Genereaza toate permutarile unei liste.

def permutari(lista):
    if len(lista) <= 1:
        return [lista]

    rezultat = []
    for i, elem in enumerate(lista):
        rest = lista[:i] + lista[i+1:]
        for perm in permutari(rest):
            rezultat.append([elem] + perm)
    return rezultat

# Test
print(permutari([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Exercitiul 6: Compresie Run-Length

Problema: Comprima string cu numarare caractere consecutive.

def comprima(s):
    if not s:
        return ""

    rezultat = []
    contor = 1
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            contor += 1
        else:
            rezultat.append(s[i-1] + str(contor))
            contor = 1
    rezultat.append(s[-1] + str(contor))
    return "".join(rezultat)

# Test
print(comprima("aaabbbcc"))   # a3b3c2
print(comprima("abcd"))       # a1b1c1d1

Exercitiul 7: Cache LRU Simplu

Problema: Implementeaza un cache LRU (Least Recently Used).

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacitate):
        self.cache = OrderedDict()
        self.capacitate = capacitate

    def get(self, cheie):
        if cheie not in self.cache:
            return -1
        self.cache.move_to_end(cheie)
        return self.cache[cheie]

    def put(self, cheie, valoare):
        if cheie in self.cache:
            self.cache.move_to_end(cheie)
        self.cache[cheie] = valoare
        if len(self.cache) > self.capacitate:
            self.cache.popitem(last=False)

# Test
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
print(cache.get("a"))  # 1
cache.put("c", 3)
print(cache.get("b"))  # -1 (eliminat)

Puncte Cheie

• Recursivitatea pentru structuri imbricate
• Memoizarea pentru optimizare
• Stiva pentru validare paranteze
• OrderedDict pentru ordine de insertie