Python Interview Preparation - Top 50 Questions & Solutions

# Time Complexity Cheat Sheet

# Lists - O(1) append, O(n) insert/delete
nums = [1, 2, 3]
nums.append(4)  # O(1)

# Dicts - O(1) average lookup
user = {'id': 1, 'name': 'Alice'}
print(user['name'])  # O(1)

# Sets - O(1) membership test
seen = set([1, 2, 3])
print(2 in seen)  # O(1)

def reverse_string(s: list[str]) -> None:
    """Do not return anything, modify s in-place instead."""
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

# Test cases
s1 = list('hello')
reverse_string(s1)
print(''.join(s1))  # olleh

s2 = list('python')
reverse_string(s2)
print(''.join(s2))  # nohtyp

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome('A man, a plan, a canal: Panama'))  # True
print(is_palindrome('race a car'))  # False

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # num: index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

print(two_sum([2,7,11,15], 9))  # [0,1]
print(two_sum([3,2,4], 6))  # [1,2]
print(two_sum([3,3], 6))  # [0,1]

def fib(n: int) -> int:
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

print(fib(2))  # 1
print(fib(3))  # 2
print(fib(4))  # 3
print(fib(30)) # 832040

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

# Test
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
print(lru.get(1))  # 1
lru.put(3, 3)
print(lru.get(2))  # -1

def merge(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []
    
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    return merged

print(merge([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]

# Decorator
 def timer(func):
    import time
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        print(f'{func.__name__}: {time.time()-start:.2f}s')
        return result
    return wrapper

@timer
def slow_function():
    time.sleep(1)

# Generator
 def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

# Context Manager
class DatabaseConnection:
    def __enter__(self):
        print('Connected')
        return self
    def __exit__(self, exc_type, exc_val, exc_tb):
        print('Disconnected')

from collections import deque
import time

class RateLimiter:
    def __init__(self, max_requests: int, window: int):
        self.max_requests = max_requests
        self.window = window
        self.requests = deque()
    
    def allow(self, client_id: str) -> bool:
        now = time.time()
        # Remove old requests
        while self.requests and now - self.requests[0] > self.window:
            self.requests.popleft()
        
        if len(self.requests) < self.max_requests:
            self.requests.append(now)
            return True
        return False

{
  "version": "0.2.0",
  "configurations": [
    {
      "name": "LeetCode Practice",
      "type": "python",
      "request": "launch",
      "program": "${file}",
      "console": "integratedTerminal",
      "cwd": "${workspaceFolder}"
    },
    {
      "name": "Run All Tests",
      "type": "python",
      "request": "launch",
      "module": "pytest",
      "args": ["tests", "-v"]
    }
  ]
}