Intermediate 30 Questions • ~8 hrs study

DSA in Python (Q151-180)

Data Structures & Algorithms in Python — sorting, searching, trees, graphs, dynamic programming, and common interview patterns.

151

Implement a Binary Search in Python.

Short Answer

Binary search repeatedly divides a sorted array in half. Time complexity O(log n), space O(1) iterative or O(log n) recursive.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

💡 Memory Trick: "Binary = halving the phone book. O(log n) = 1000 items in 10 steps"

152

How does Python's built-in sort work (Timsort)?

Short Answer

Python uses Timsort — a hybrid of merge sort and insertion sort. Best case O(n), average/worst O(n log n), stable, and optimized for real-world partially sorted data.

Key Points

  • Finds naturally occurring "runs" (sorted subsequences)
  • Uses insertion sort for small runs (< 64 elements)
  • Merges runs using merge sort strategy
  • Stable sort: equal elements maintain relative order

💡 Memory Trick: "Timsort = Smart merge sort that exploits existing order in data"

153

Implement a LRU Cache using Python.

Short Answer

Use OrderedDict or functools.lru_cache. LRU evicts the least recently used item when capacity is reached.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        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)

💡 Memory Trick: "LRU = Library shelf — least borrowed books get removed first"

Questions 154-180 continue with the same detailed format.

Topics covered: Two Pointers, Sliding Window, BFS/DFS, Dijkstra's Algorithm, Dynamic Programming (Fibonacci, Knapsack, LCS), Stack/Queue implementations, Linked List operations, Heap/Priority Queue, Trie, and common LeetCode patterns.

View Full Documentation →
Previous: Advanced (Q101-150) Next: NumPy & Pandas (Q181-200)