Lists and tuples are both used to store collections of items in Python, but they have key differences:

1. Mutability

• List: Mutable (can be changed after creation—elements can be added, removed, or modified).
• Tuple: Immutable (cannot be changed after creation—elements cannot be added, removed, or modified).

2. Syntax

• List: Defined using square brackets [].

  my_list = [1, 2, 3]
  

• Tuple: Defined using parentheses ().

  my_tuple = (1, 2, 3)
  

3. Performance

• List: Slower (because of mutability, it has extra overhead).
• Tuple: Faster (because it is immutable, making it more memory-efficient).

4. Use Cases

• List: Used when data needs to be modified, sorted, or frequently changed.
• Tuple: Used when data should remain constant and not be accidentally modified (e.g., representing fixed data like coordinates or database records).

5. Memory Usage

• List: Takes more memory due to dynamic nature.
• Tuple: Takes less memory, making it more efficient in some cases.

6. Methods Available

• List: Has more built-in methods like append(), remove(), sort(), etc.
• Tuple: Has fewer methods, mostly for accessing elements like count() and index().

Example :

# List Example (Mutable)
my_list = [1, 2, 3]
my_list.append(4)  # Allowed
print(my_list)  # Output: [1, 2, 3, 4]

# Tuple Example (Immutable)
my_tuple = (1, 2, 3)
# my_tuple.append(4)  # This will cause an error!
print(my_tuple)  # Output: (1, 2, 3)

When to Use What?

• Use a list when you need to modify data.
• Use a tuple when you want to ensure data remains unchanged and for better performance.

You can remove duplicates from a list in several ways. Here are the most common methods:

1. Using set() (Fastest, but Unordered)

my_list = [1, 2, 2, 3, 4, 4, 5]
unique_list = list(set(my_list))
print(unique_list)  # Output: [1, 2, 3, 4, 5] (order may change)

Downside : This method does not preserve the original order.

2. Using a Loop (Preserves Order)

my_list = [1, 2, 2, 3, 4, 4, 5]
unique_list = []
for item in my_list:
    if item not in unique_list:
        unique_list.append(item)
print(unique_list)  # Output: [1, 2, 3, 4, 5]

* Keeps the original order.

3. Using Dictionary Keys (dict.fromkeys())

my_list = [1, 2, 2, 3, 4, 4, 5]
unique_list = list(dict.fromkeys(my_list))
print(unique_list)  # Output: [1, 2, 3, 4, 5]

* Preserves order (since Python 3.7+).
* Faster than a loop but slower than set().

4. Using List Comprehension with set() (Efficient)

my_list = [1, 2, 2, 3, 4, 4, 5]
seen = set()
unique_list = [x for x in my_list if not (x in seen or seen.add(x))]
print(unique_list)  # Output: [1, 2, 3, 4, 5]

* Preserves order and is faster than using a loop.

Best Choice?

• Use set() if order doesn’t matter.
• Use dict.fromkeys() if order matters and you want a simple approach.
• Use list comprehension with a set for an optimized, order-preserving solution.

1. Using reversed() and list() :

my_list = [1, 2, 3, 4, 5]
reversed_list = list(reversed(my_list))
print(reversed_list)  # Output: [5, 4, 3, 2, 1]
print(my_list) #Output: [1, 2, 3, 4, 5]?

2. Using slicing :

my_list = [1, 2, 3, 4, 5]
reversed_list = my_list[::-1]
print(reversed_list)  # Output: [5, 4, 3, 2, 1]
print(my_list) #Output: [1, 2, 3, 4, 5]?

3. Using list.reverse() :

my_list = [1, 2, 3, 4, 5]
my_list.reverse()
print(my_list)  # Output: [5, 4, 3, 2, 1]?

Which method to choose :

You can find the length of a list in Python using the built-in len() function.

Example :

my_list = [10, 20, 30, 40, 50]
length = len(my_list)
print(length)  # Output: 5

* len() is the most efficient way to get the number of elements in a list.

Both append() and extend() are used to add elements to a list in Python, but they work differently.

1. append() – Adds a Single Element (or Object)

• append() adds an element as a single item at the end of the list.
• If you append another list, the entire list is added as a single element (nested list).

Example :

my_list = [1, 2, 3]
my_list.append([4, 5])  # Appends the list as a single element
print(my_list)  # Output: [1, 2, 3, [4, 5]]

* Used when you want to add a single element.

2. extend() – Merges Another Iterable :

• extend() takes an iterable (like another list, tuple, or set) and adds each element separately to the list.
• It does not create a nested list.

Example :

my_list = [1, 2, 3]
my_list.extend([4, 5])  # Adds elements separately
print(my_list)  # Output: [1, 2, 3, 4, 5]

* Used when you want to add multiple elements individually.

Key Differences :

What is a Dictionary in Python?

A dictionary in Python is an unordered, mutable, and key-value paired data structure. It allows you to store and retrieve values using unique keys.

Syntax:

my_dict = {
    "name": "Alice",
    "age": 25,
    "city": "New York"
}

• Keys (e.g., "name", "age", "city") must be unique and immutable (strings, numbers, or tuples).
• Values (e.g., "Alice", 25, "New York") can be any data type.

How is a Dictionary Different from a List?

Example: Dictionary vs. List

# List Example (Indexed Access)
my_list = ["Alice", 25, "New York"]
print(my_list[0])  # Output: Alice

# Dictionary Example (Key-Based Access)
my_dict = {"name": "Alice", "age": 25, "city": "New York"}
print(my_dict["name"])  # Output: Alice

* Dictionaries are best for labeled data (e.g., a database record).
* Lists are best for ordered collections (e.g., a list of items in a shopping cart).

1. Using Square Brackets []:

my_dict = {"name": "Alice", "age": 30, "city": "New York"}
print(my_dict["name"])  # Output: Alice
print(my_dict["age"])   # Output: 30

#Example of a key error.
#print(my_dict["occupation"]) #This line would cause a KeyError.?

2. Using the get() Method :

my_dict = {"name": "Alice", "age": 30, "city": "New York"}
print(my_dict.get("name"))       # Output: Alice
print(my_dict.get("occupation")) # Output: None
print(my_dict.get("occupation", "Unknown")) # Output: Unknown.?

In Python, del, pop(), and popitem() are used to remove elements from a dictionary, but they work differently. Here’s a breakdown of their differences:

1. del – Removes a Key-Value Pair by Key

• Deletes a specific key and its value from the dictionary.
• Raises a KeyError if the key doesn’t exist.
• Can delete the entire dictionary if used without a key.

Example :

my_dict = {"name": "Alice", "age": 25, "city": "New York"}

# Delete a specific key
del my_dict["age"]
print(my_dict)  # Output: {'name': 'Alice', 'city': 'New York'}

# Delete the entire dictionary
del my_dict
# print(my_dict)  # Raises NameError because the dictionary is deleted.

* Use when you want to remove a specific key or delete the whole dictionary.

2. pop() – Removes and Returns a Value by Key

• Removes a specific key and returns its value.
• Raises a KeyError if the key doesn’t exist, unless a default value is provided.

Example :

my_dict = {"name": "Alice", "age": 25, "city": "New York"}

# Remove 'age' and return its value
removed_value = my_dict.pop("age")
print(removed_value)  # Output: 25
print(my_dict)  # Output: {'name': 'Alice', 'city': 'New York'}

# Using pop() with a default value to avoid KeyError
removed_value = my_dict.pop("country", "Not Found")
print(removed_value)  # Output: Not Found

* Use when you want to remove a key and retrieve its value.

3. popitem() – Removes and Returns the Last Inserted Key-Value Pair

• Removes and returns the last inserted (key, value) pair as a tuple.
• Raises a KeyError if the dictionary is empty.

Example :

my_dict = {"name": "Alice", "age": 25, "city": "New York"}

# Remove and return the last item
removed_item = my_dict.popitem()
print(removed_item)  # Output: ('city', 'New York')
print(my_dict)  # Output: {'name': 'Alice', 'age': 25}

* Use when you want to remove the most recently added key-value pair (useful for stacks or LIFO operations).

Comparison Table :

What Are Sets in Python?

A set in Python is an unordered, mutable, and unique collection of elements. It is similar to a list, but it does not allow duplicate values and is optimized for fast lookups.

Syntax :

my_set = {1, 2, 3, 4, 5}  # Defining a set
empty_set = set()  # Creating an empty set (NOT {})

Important: {} creates an empty dictionary, not an empty set.

How Are Sets Different from Lists?

Examples :

1. Removing Duplicates Using a Set

my_list = [1, 2, 2, 3, 4, 4, 5]
unique_set = set(my_list)  # Removes duplicates
print(unique_set)  # Output: {1, 2, 3, 4, 5}

* Sets are useful for removing duplicates from lists.

2. Adding and Removing Elements in a Set

my_set = {1, 2, 3}

# Add an element
my_set.add(4)
print(my_set)  # Output: {1, 2, 3, 4}

# Remove an element
my_set.remove(2)
print(my_set)  # Output: {1, 3, 4}

# Discard (won't raise an error if the element is missing)
my_set.discard(10)  # No error

3. Set Operations (Union, Intersection, Difference)

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

# Union (A ∪ B): Combines both sets
print(A | B)  # Output: {1, 2, 3, 4, 5, 6}

# Intersection (A ∩ B): Common elements
print(A & B)  # Output: {3, 4}

# Difference (A - B): Elements in A but not in B
print(A - B)  # Output: {1, 2}

# Symmetric Difference (A ⊕ B): Elements in either A or B, but not both
print(A ^ B)  # Output: {1, 2, 5, 6}

* Sets are powerful for mathematical operations and fast lookups.

When to Use Sets Over Lists?

• When uniqueness of elements is required (e.g., storing unique IDs).
• When fast membership tests are needed (x in my_set is faster than x in my_list).
• When performing set operations like union, intersection, or difference.

stack = []
stack.append(1) # Push element
stack.append(2)
stack.pop() # Pop element?

from collections import deque
queue = deque()
queue.append(1) # Enqueue element
queue.append(2)
queue.popleft() # Dequeue element?

You can merge two dictionaries in Python using several methods. Here are the most common ways:

1. Using the update() Method (Modifies Original Dictionary)

• The update() method adds key-value pairs from one dictionary to another.
• If a key exists in both dictionaries, the value from the second dictionary overwrites the value in the first.

Example :

dict1 = {"a": 1, "b": 2}
dict2 = {"b": 3, "c": 4}

dict1.update(dict2)  # Modifies dict1
print(dict1)  # Output: {'a': 1, 'b': 3, 'c': 4}

* Best when you want to modify an existing dictionary.

2. Using Dictionary Unpacking (**) (Creates a New Dictionary)

• This method merges dictionaries into a new one without modifying the originals.
• If keys overlap, values from later dictionaries overwrite earlier ones.

Example :

dict1 = {"a": 1, "b": 2}
dict2 = {"b": 3, "c": 4}

merged_dict = {**dict1, **dict2}
print(merged_dict)  # Output: {'a': 1, 'b': 3, 'c': 4}

* Best when you want to create a new merged dictionary.

3. Using the | Operator (Python 3.9+)

• Introduced in Python 3.9, | merges two dictionaries and returns a new one.
• Overlapping keys take the value from the second dictionary.

Example (Python 3.9+ Only) :

dict1 = {"a": 1, "b": 2}
dict2 = {"b": 3, "c": 4}

merged_dict = dict1 | dict2
print(merged_dict)  # Output: {'a': 1, 'b': 3, 'c': 4}

* Best when using Python 3.9+ and you need a clean syntax.

4. Using a Dictionary Comprehension (Advanced)

• This method gives more control, allowing transformations while merging.

Example :

dict1 = {"a": 1, "b": 2}
dict2 = {"b": 3, "c": 4}

merged_dict = {key: dict2.get(key, dict1.get(key)) for key in dict1.keys() | dict2.keys()}
print(merged_dict)  # Output: {'a': 1, 'b': 3, 'c': 4}

* Best when you need custom merging logic.

Which Method to Use?

Sorting a dictionary in Python can be done in two ways:

1. Sorting by Keys
2. Sorting by Values

Since dictionaries are unordered before Python 3.7, sorting creates a new dictionary with a specific order.

1. Sorting a Dictionary by Keys

• Use the sorted() function on dict.keys() and reconstruct the dictionary.

Example :

my_dict = {"b": 2, "a": 1, "c": 3}

# Sorting by keys (ascending order)
sorted_dict = dict(sorted(my_dict.items()))
print(sorted_dict)  # Output: {'a': 1, 'b': 2, 'c': 3}

* Default sorting is in ascending order (A → Z, 0 → 9).
* Use reverse=True for descending order.

2. Sorting a Dictionary by Values

• Sort based on the second element in (key, value) pairs.

Example :

my_dict = {"b": 2, "a": 1, "c": 3}

# Sorting by values (ascending order)
sorted_by_values = dict(sorted(my_dict.items(), key=lambda item: item[1]))
print(sorted_by_values)  # Output: {'a': 1, 'b': 2, 'c': 3}

* Sorting is based on values instead of keys.
* Use reverse=True for descending order.

3. Sorting by Keys in Descending Order

sorted_dict_desc = dict(sorted(my_dict.items(), reverse=True))
print(sorted_dict_desc)  # Output: {'c': 3, 'b': 2, 'a': 1}

4. Sorting by Values in Descending Order

sorted_by_values_desc = dict(sorted(my_dict.items(), key=lambda item: item[1], reverse=True))
print(sorted_by_values_desc)  # Output: {'c': 3, 'b': 2, 'a': 1}

Which Method Should You Use?

The difference between copy() and deepcopy() in Python lies in how they handle nested objects (mutable objects inside other objects like lists or dictionaries).

1. copy() (Shallow Copy)

• Creates a new object, but references nested objects instead of copying them.
• Changes to nested objects affect both the original and copied object.

Example :

import copy

original = [[1, 2, 3], [4, 5, 6]]
shallow_copy = copy.copy(original)

shallow_copy[0][0] = 99  # Modifying a nested list
print(original)       # Output: [[99, 2, 3], [4, 5, 6]]  (Changed!)
print(shallow_copy)   # Output: [[99, 2, 3], [4, 5, 6]]

* Best for non-nested objects or when modifying nested elements is acceptable.

2. deepcopy() (Deep Copy)

• Creates a completely independent copy, including all nested objects.
• Changes to the new object do not affect the original.

Example :

import copy

original = [[1, 2, 3], [4, 5, 6]]
deep_copy = copy.deepcopy(original)

deep_copy[0][0] = 99  # Modifying a nested list
print(original)      # Output: [[1, 2, 3], [4, 5, 6]]  (Unchanged!)
print(deep_copy)     # Output: [[99, 2, 3], [4, 5, 6]]

* Best for deeply nested structures where modifications should be independent.

Key Differences

import copy
original = [[1, 2], [3, 4]]
deep_copied = copy.deepcopy(original)?

Time Complexity of Insertion and Deletion in a Python List

Python lists are implemented as dynamic arrays, which affects the time complexity of insertion and deletion operations.

1. Inserting Elements into a List

a) append() – Add at the End

my_list.append(10)  # Adds element at the end

• Time Complexity: O(1) (Amortized)
• Why? Appending at the end is usually constant time, but occasional resizing may cause O(n) when the array expands.

b) insert(index, value) – Insert at a Specific Position

my_list.insert(2, 50)  # Inserts 50 at index 2

• Time Complexity: O(n)
• Why? Inserting in the middle shifts all elements after the index.

2. Deleting Elements from a List

a) pop() – Remove from the End

my_list.pop()  # Removes the last element

• Time Complexity: O(1)
• Why? Removing from the end does not require shifting elements.

b) pop(index) – Remove from a Specific Position

my_list.pop(2)  # Removes element at index 2

• Time Complexity: O(n)
• Why? Removing an element from the middle requires shifting elements to fill the gap.

c) remove(value) – Remove by Value

my_list.remove(50)  # Removes first occurrence of 50

• Time Complexity: O(n)
• Why? It first searches for the value (O(n)) and then removes it (O(n), worst case).

Summary Table

Implementing a Stack Using Lists in Python

A stack is a data structure that follows the Last In, First Out (LIFO) principle. Python lists can be used to implement a stack because they support append() and pop(), which operate in O(1) time at the end of the list.

1. Using a List to Implement a Stack

Operations :

• Push (add an element) → append()
• Pop (remove top element) → pop()
• Peek (view top element without removing) → [-1]
• Check if Stack is Empty → len(stack) == 0

Example :

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        """Add an item to the top of the stack (O(1) operation)."""
        self.stack.append(item)

    def pop(self):
        """Remove and return the top item from the stack (O(1) operation)."""
        if not self.is_empty():
            return self.stack.pop()
        return "Stack is empty"

    def peek(self):
        """Return the top item without removing it."""
        if not self.is_empty():
            return self.stack[-1]
        return "Stack is empty"

    def is_empty(self):
        """Check if the stack is empty."""
        return len(self.stack) == 0

    def size(self):
        """Return the size of the stack."""
        return len(self.stack)

# Example usage
s = Stack()
s.push(10)
s.push(20)
s.push(30)

print(s.peek())   # Output: 30
print(s.pop())    # Output: 30
print(s.size())   # Output: 2

2. Why Use append() and pop()?

• append(x) adds to the end → O(1)
• pop() removes from the end → O(1)
• If we inserted or removed from the beginning (insert(0, x) or pop(0)), it would be O(n) due to shifting elements.

3. Alternative: Using collections.deque (More Efficient)

Python’s collections.deque is optimized for fast insertions/removals at both ends.

from collections import deque

class Stack:
    def __init__(self):
        self.stack = deque()

    def push(self, item):
        self.stack.append(item)  # O(1)

    def pop(self):
        return self.stack.pop() if self.stack else "Stack is empty"

    def peek(self):
        return self.stack[-1] if self.stack else "Stack is empty"

    def is_empty(self):
        return len(self.stack) == 0

    def size(self):
        return len(self.stack)

* deque is faster for large datasets because it avoids list resizing.

Difference Between OrderedDict and a Normal Dictionary (dict)

Python provides both dict (normal dictionary) and OrderedDict from the collections module. The key difference lies in how they maintain insertion order and handle performance.

1. Normal Dictionary (dict)

• Since Python 3.7+, dictionaries maintain insertion order by default.
• Keys remain in the order they were inserted.
• Fast performance due to being implemented as a hash table.

Example :

# Normal Dictionary (Python 3.7+ retains order)
my_dict = {"a": 1, "b": 2, "c": 3}
print(my_dict)  # Output: {'a': 1, 'b': 2, 'c': 3}

* Insertion order is preserved.
* Faster than OrderedDict due to internal optimizations.

2. OrderedDict (Before Python 3.7, Required for Ordered Keys)

• Explicitly guarantees order of keys across Python versions.
• Provides additional methods like move_to_end().
• Slightly slower than a normal dictionary.

Example :

from collections import OrderedDict

# Creating an OrderedDict
ordered_dict = OrderedDict()
ordered_dict["a"] = 1
ordered_dict["b"] = 2
ordered_dict["c"] = 3

print(ordered_dict)  # Output: OrderedDict([('a', 1), ('b', 2), ('c', 3)])

* Ensures order even in Python versions below 3.7.
* Slightly slower due to extra overhead.

3. Special Features of OrderedDict

a) move_to_end(key, last=True)

Moves a key to the end (or start if last=False).

ordered_dict.move_to_end("b")
print(ordered_dict)  # Output: OrderedDict([('a', 1), ('c', 3), ('b', 2)])

b) Maintains Order in Equality Checks (==)

d1 = OrderedDict([("a", 1), ("b", 2)])
d2 = OrderedDict([("b", 2), ("a", 1)])

print(d1 == d2)  # Output: False (Order matters)

* Unlike a normal dictionary, order matters in comparison.

4. Which One Should You Use?

* Use dict in Python 3.7+ unless you need OrderedDict's extra features.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert_recursive(self.root, data)

    def _insert_recursive(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = Node(data)
            else:
                self._insert_recursive(node.left, data)
        else:
            if node.right is None:
                node.right = Node(data)
            else:
                self._insert_recursive(node.right, data)?

Purpose of defaultdict in Python

defaultdict is a subclass of Python’s built-in dict that automatically provides a default value for missing keys, preventing KeyError. It’s part of the collections module.

1. Why Use defaultdict?

• Avoids KeyError when accessing missing keys.
• Automatically assigns a default value to new keys.
• Simplifies code, especially when handling nested structures like lists or sets.

2. Basic Usage of defaultdict

Without defaultdict (Using Normal dict)

my_dict = {}
my_dict["a"].append(1)  # ? KeyError: 'a' (Key does not exist)

With defaultdict (Prevents KeyError)

from collections import defaultdict

# Creates a defaultdict with list as the default factory
my_dict = defaultdict(list)

# No KeyError, automatically initializes 'a' as an empty list
my_dict["a"].append(1)

print(my_dict)  # Output: {'a': [1]}

* No KeyError! defaultdict automatically creates an empty list.

3. Default Factories in defaultdict

You can pass a factory function to specify default values:

Example: Using int to Count Occurrences

word_count = defaultdict(int)
words = ["apple", "banana", "apple", "orange", "banana", "banana"]

for word in words:
    word_count[word] += 1  # No need to check if key exists!

print(word_count)  # Output: {'apple': 2, 'banana': 3, 'orange': 1}

* No need to initialize keys manually!

4. Nested defaultdict (Creating Auto-Nested Dictionaries)

defaultdict can be used to create nested dictionaries without manually initializing sub-dictionaries.

Example : Creating a Nested Dictionary

nested_dict = defaultdict(lambda: defaultdict(int))

nested_dict["A"]["Math"] = 90
nested_dict["A"]["Science"] = 85

print(nested_dict)  
# Output: {'A': {'Math': 90, 'Science': 85}}

* Automatically creates sub-dictionaries when accessing missing keys.

5. When to Use defaultdict vs. dict?

When Should You Use defaultdict?

* When grouping elements (defaultdict(list))
* When counting occurrences (defaultdict(int))
* When creating nested dictionaries (defaultdict(lambda: defaultdict(int))

Implementing a Priority Queue in Python

A priority queue is a data structure where elements are dequeued based on priority rather than insertion order. Python provides several ways to implement a priority queue.

1. Using heapq (Efficient and Built-in)

Python's heapq module implements a min-heap by default, where the smallest element has the highest priority.

Example: Implementing a Min-Priority Queue

import heapq

# Create an empty priority queue
pq = []

# Add elements with heapq.heappush()
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)  # Lowest priority (highest priority)
heapq.heappush(pq, 4)
heapq.heappush(pq, 2)

print(pq)  # Output: [1, 2, 4, 3] (Heap structure, not sorted)

# Remove elements with heapq.heappop()
print(heapq.heappop(pq))  # Output: 1 (Smallest element)
print(heapq.heappop(pq))  # Output: 2

* Efficient: heappush() and heappop() run in O(log n) time.
* Always dequeues the smallest element first (Min-Heap).

2. Implementing a Max-Priority Queue (Max-Heap)

Since heapq is a min-heap by default, we can simulate a max-heap by pushing negative values.

Example :

import heapq

pq = []
heapq.heappush(pq, -3)
heapq.heappush(pq, -1)
heapq.heappush(pq, -4)
heapq.heappush(pq, -2)

print(-heapq.heappop(pq))  # Output: 4 (Highest priority first)
print(-heapq.heappop(pq))  # Output: 3

* Largest element dequeued first.
* Negating values is a common trick for max-heaps.

3. Using heapq with Tuples for Custom Priority

If we need custom priority values, we can store elements as tuples (priority, item).

Example: Priority Queue with Custom Priority

import heapq

pq = []
heapq.heappush(pq, (2, "Task B"))  # Lower number = higher priority
heapq.heappush(pq, (1, "Task A"))
heapq.heappush(pq, (3, "Task C"))

print(heapq.heappop(pq))  # Output: (1, 'Task A')
print(heapq.heappop(pq))  # Output: (2, 'Task B')

* Maintains a priority order based on the first tuple element.
* Useful for scheduling tasks or event processing.

4. Using queue.PriorityQueue (Thread-Safe)

The queue.PriorityQueue class provides a thread-safe priority queue.

Example :

from queue import PriorityQueue

pq = PriorityQueue()
pq.put((2, "Task B"))
pq.put((1, "Task A"))
pq.put((3, "Task C"))

print(pq.get())  # Output: (1, 'Task A')
print(pq.get())  # Output: (2, 'Task B')

* Thread-safe for multi-threaded applications.
* Uses heapq internally, so operations are O(log n).

5. Implementing a Priority Queue Using a Custom Class

If we want more control, we can implement a priority queue class using heapq.

import heapq

class PriorityQueue:
    def __init__(self):
        self.queue = []
    
    def push(self, priority, item):
        heapq.heappush(self.queue, (priority, item))
    
    def pop(self):
        return heapq.heappop(self.queue)[1]  # Return only the item

    def is_empty(self):
        return len(self.queue) == 0

# Example usage
pq = PriorityQueue()
pq.push(2, "Task B")
pq.push(1, "Task A")
pq.push(3, "Task C")

print(pq.pop())  # Output: 'Task A' (Highest priority)
print(pq.pop())  # Output: 'Task B'

* Encapsulates priority queue behavior.
* Cleaner and reusable code.

Which Method Should You Use?

Named Tuples in Python

A named tuple is a special type of tuple provided by the collections module that allows named fields, making them more readable and self-documenting compared to regular tuples.

1. Why Use Named Tuples?

• Improves code readability by accessing elements by name instead of index.
• Immutable, just like regular tuples.
• Memory-efficient compared to dictionaries (uses less space).
• Useful for lightweight data structures like database records, coordinates, or configurations.

2. Creating a Named Tuple

You can create a named tuple using collections.namedtuple().

Example: Using Named Tuples for a Point (x, y)

from collections import namedtuple

# Define a named tuple called 'Point' with fields 'x' and 'y'
Point = namedtuple("Point", ["x", "y"])

# Create a point instance
p = Point(3, 4)

# Access values by name instead of index
print(p.x)  # Output: 3
print(p.y)  # Output: 4

# Named tuple is still a tuple, so it supports indexing
print(p[0])  # Output: 3

* More readable than a regular tuple (p.x instead of p[0]).

3. Named Tuples vs. Dictionaries

4. Extra Features of Named Tuples

a) Assigning Default Values with defaultdict

from collections import namedtuple

# Define a named tuple with default values
Person = namedtuple("Person", ["name", "age", "city"])
p1 = Person("Alice", 25, "New York")

print(p1.name)  # Output: Alice

b) Converting Named Tuple to Dictionary

print(p1._asdict())  # Output: {'name': 'Alice', 'age': 25, 'city': 'New York'}

* Easily convert to a dictionary!

c) Replacing Values with _replace()

p2 = p1._replace(age=26)  
print(p2)  # Output: Person(name='Alice', age=26, city='New York')

* Creates a new modified instance (since tuples are immutable).

5. When Should You Use Named Tuples?

* For lightweight, immutable data structures (e.g., coordinates, database rows).
* When you need dictionary-like access but with better performance.
* For cleaner, self-documenting code.

Heap Data Structure in Python

A heap is a special tree-based data structure that satisfies the heap property:

• In a min-heap, the parent node is always smaller than its children.
• In a max-heap, the parent node is always greater than its children.

Heaps are commonly used for priority queues, sorting algorithms (Heap Sort), and graph algorithms (Dijkstra’s Algorithm, Prim’s Algorithm, etc.).

1. Types of Heaps

1. Min-Heap: The smallest element is always at the root.
2. Max-Heap: The largest element is always at the root.

2. Implementing a Heap in Python

Python provides the heapq module, which implements a min-heap by default.

Min-Heap Implementation (Using heapq)

import heapq

# Create an empty heap
heap = []

# Insert elements into the heap
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 15)
heapq.heappush(heap, 7)

print(heap)  # Output: [5, 7, 15, 10] (Heap structure, not sorted)

# Remove and return the smallest element
print(heapq.heappop(heap))  # Output: 5
print(heap)  # Output: [7, 10, 15]

* heappush() and heappop() run in O(log n) time.
* Always dequeues the smallest element first (Min-Heap).

3. Implementing a Max-Heap

Since heapq only supports min-heaps, we can simulate a max-heap by inserting negative values.

import heapq

max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -15)
heapq.heappush(max_heap, -7)

print(-heapq.heappop(max_heap))  # Output: 15 (Largest element first)

* By pushing negative values, the smallest negative becomes the largest positive.

4. Building a Heap from a List

We can convert an existing list into a heap using heapq.heapify(), which runs in O(n) time.

import heapq

arr = [10, 5, 15, 7]
heapq.heapify(arr)

print(arr)  # Output: [5, 7, 15, 10] (Min-Heap order)
print(heapq.heappop(arr))  # Output: 5

* heapify() transforms a list into a valid heap in O(n) time.

5. Using a Heap as a Priority Queue

Example: Using Tuples for Priority

import heapq

pq = []
heapq.heappush(pq, (2, "Task B"))  # Priority 2
heapq.heappush(pq, (1, "Task A"))  # Priority 1 (Highest)
heapq.heappush(pq, (3, "Task C"))  # Priority 3

print(heapq.heappop(pq))  # Output: (1, 'Task A')

* The lowest priority number is dequeued first.

6. Implementing a Heap Manually

If you want to implement a heap from scratch, you can use a binary tree with an array.

Manual Min-Heap Implementation

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def _heapify_up(self, index):
        parent = self.parent(index)
        if index > 0 and self.heap[index] < self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            self._heapify_up(parent)

    def pop(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root

    def _heapify_down(self, index):
        smallest = index
        left = self.left_child(index)
        right = self.right_child(index)

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._heapify_down(smallest)

# Example Usage
heap = MinHeap()
heap.insert(10)
heap.insert(5)
heap.insert(15)
heap.insert(7)

print(heap.pop())  # Output: 5
print(heap.pop())  # Output: 7

* Implements min-heap from scratch.
* Uses array representation of a binary tree.

7. When to Use Heaps?

Python's sets and dictionaries are both implemented using hash tables, which is the key to their efficiency. Here's a breakdown:

Hash Tables :

• At the core, a hash table is a data structure that uses a hash function to map keys to indices in an array (the "table").
• A hash function takes a key as input and produces an integer (the "hash code").
• This hash code is then used to determine where in the array the key-value pair (in the case of dictionaries) or the key (in the case of sets) should be stored.
• This allows for very fast lookups, insertions, and deletions, typically with an average time complexity of O(1).

Dictionaries :

• In Python dictionaries, keys must be hashable (meaning they have a hash code that doesn't change during their lifetime).
• When you add a key-value pair to a dictionary:
  • The key's hash code is calculated.
  • This hash code is used to find an index in the underlying hash table.
  • The key and its associated value are stored at that index.
• When you look up a value using a key:
  • The key's hash code is calculated again.
  • The hash table is consulted at the corresponding index.
  • If the key is found, the associated value is returned.
• Collision Handling: Because different keys can produce the same hash code (a "collision"), Python uses collision resolution techniques (like open addressing or separate chaining) to handle these situations.

Sets :

• Python sets also rely on hash tables, but they primarily store keys (the set elements) rather than key-value pairs.
• Each element in a set must also be hashable.
• Sets utilize hash tables to ensure that:
  • All elements are unique.
  • Membership tests (checking if an element is in the set) are very fast.
• Because of the underlaying use of the hash table, checking if an element exists within a set is very fast.

Key Advantages :

• Speed: Hash tables enable very efficient lookups, insertions, and deletions.
• Uniqueness: Sets inherently enforce uniqueness due to the nature of hash tables.
• Efficiency: Dictionaries can efficiently associate values with keys, enabling rapid data retrieval.

In essence, the use of hash tables is what makes Python's dictionaries and sets so performant.

How Python Handles Hash Collisions in Dictionaries

Python dictionaries use a hash table internally, where keys are stored based on their hash values. A hash collision occurs when two different keys generate the same hash value. To handle this, Python uses open addressing with probing.

1. Dictionary Structure

A Python dictionary consists of:

• A dynamic array (hash table): Stores key-value pairs.
• A hash function: Computes a hash for the key.
• Collision resolution strategy: Handles cases where two keys have the same hash.

2. Collision Resolution: Open Addressing

Python uses open addressing with probing to resolve collisions. This means:

• If a hash collision occurs, Python searches for the next available empty slot.
• The search follows a probing sequence (e.g., linear probing or quadratic probing).

Example of Hash Collision

d = {}
d[1] = "One"
d[2] = "Two"

# Assume hash(1) and hash(2) collide
# Python finds an empty slot for the second key

Even if two keys collide, they still get stored separately due to probing.

3. Steps Python Follows When Inserting a Key

1. Compute hash(key) % table_size → Finds the initial slot.
2. If the slot is empty, store (key, value).
3. If the slot is occupied (collision occurs):
   • Check if the key already exists (update value).
   • If not, find the next available slot using probing.
4. If too many collisions occur, Python resizes the dictionary.

4. Example: How Python Handles Collisions

class SimpleDict:
    def __init__(self, size=5):
        self.size = size
        self.table = [None] * size  # Simulated hash table

    def _hash(self, key):
        return hash(key) % self.size  # Simulate Python's hash function

    def insert(self, key, value):
        index = self._hash(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:  # Update value if key exists
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size  # Linear probing
        self.table[index] = (key, value)

    def display(self):
        print(self.table)

# Example usage
d = SimpleDict()
d.insert(1, "One")
d.insert(6, "Six")  # Hash collision if size=5 (1 and 6 share index)
d.display()

* Uses linear probing to handle collisions.

5. Dictionary Resizing to Reduce Collisions

• When the dictionary gets too full, Python doubles its size.
• All keys are rehashed and redistributed.

6. Summary

Deques in Python vs. Lists

A deque (double-ended queue) is a specialized data structure from Python's collections module that allows fast O(1) appends and pops from both ends, unlike lists which have O(n) time complexity for operations at the start.

1. What is a Deque?

A deque is an optimized list-like container that allows:
* Fast insertion/removal from both ends (O(1) time complexity).
* Thread-safe (supports locking for multi-threading).
* Efficient memory usage (implemented as a doubly linked list).

2. Creating a Deque

You need to import collections.deque to use it.

from collections import deque

# Creating a deque
dq = deque([1, 2, 3])

# Append elements (to the right)
dq.append(4)  # [1, 2, 3, 4]

# Append elements (to the left)
dq.appendleft(0)  # [0, 1, 2, 3, 4]

print(dq)  # Output: deque([0, 1, 2, 3, 4])

* Faster than list.append() and list.insert(0, x).

3. Deque vs. List – Key Differences

4. Deque Operations

a) Removing Elements

dq.pop()  # Removes from right
dq.popleft()  # Removes from left

b) Rotating a Deque

dq.rotate(2)  # Moves last two elements to front
print(dq)

* Useful for circular buffers!

c) Limiting Deque Size (Fixed-Length Queues)

dq = deque(maxlen=3)  # Fixed size of 3
dq.extend([1, 2, 3])
dq.append(4)  # Removes 1 automatically
print(dq)  # Output: deque([2, 3, 4], maxlen=3)

* Great for implementing caches and sliding windows!

5. When to Use Deques Instead of Lists?

* Fast insert/remove at both ends (e.g., queues, caching).
* Efficiently handle large datasets (e.g., log files, sliding windows).
* Ideal for FIFO (first-in, first-out) and LIFO (last-in, first-out) structures.

Traversing a Binary Tree Using BFS and DFS in Python

Binary trees can be traversed in two main ways:
* Breadth-First Search (BFS) – Level-order traversal
* Depth-First Search (DFS) – Preorder, Inorder, Postorder

1. BFS (Breadth-First Search) – Level Order Traversal

• Visits nodes level by level.
• Uses a queue (FIFO) data structure.
• Time Complexity: O(n)
• Space Complexity: O(n) (for storing nodes in the queue).

Implementation of BFS

from collections import deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def bfs(root):
    if not root:
        return
    
    queue = deque([root])  # Initialize queue with root
    while queue:
        node = queue.popleft()  # Remove front node
        print(node.val, end=" ")  # Process node
        
        if node.left:
            queue.append(node.left)  # Add left child
        if node.right:
            queue.append(node.right)  # Add right child

# Example usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

bfs(root)  # Output: 1 2 3 4 5 6 7

* Best for shortest path problems & hierarchical data.

2. DFS (Depth-First Search) – Types

DFS explores as deep as possible before backtracking. It can be done in three ways:

a) Preorder (Root → Left → Right)

def dfs_preorder(root):
    if not root:
        return
    print(root.val, end=" ")  # Process root
    dfs_preorder(root.left)   # Process left subtree
    dfs_preorder(root.right)  # Process right subtree

dfs_preorder(root)  # Output: 1 2 4 5 3 6 7

b) Inorder (Left → Root → Right)

def dfs_inorder(root):
    if not root:
        return
    dfs_inorder(root.left)   # Process left subtree
    print(root.val, end=" ")  # Process root
    dfs_inorder(root.right)  # Process right subtree

dfs_inorder(root)  # Output: 4 2 5 1 6 3 7

* Used in Binary Search Trees (BSTs) to get sorted order.

c) Postorder (Left → Right → Root)

def dfs_postorder(root):
    if not root:
        return
    dfs_postorder(root.left)   # Process left subtree
    dfs_postorder(root.right)  # Process right subtree
    print(root.val, end=" ")  # Process root

dfs_postorder(root)  # Output: 4 5 2 6 7 3 1

* Used for deleting nodes safely (e.g., freeing memory).

3. DFS Using a Stack (Iterative)

Since recursion uses the call stack, we can also use an explicit stack.

Preorder DFS (Using a Stack)

def dfs_preorder_iterative(root):
    if not root:
        return
    
    stack = [root]
    while stack:
        node = stack.pop()  # Process current node
        print(node.val, end=" ")
        
        # Push right first so left is processed first (LIFO order)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

dfs_preorder_iterative(root)  # Output: 1 2 4 5 3 6 7

* Useful when recursion depth is too large.

4. BFS vs. DFS – When to Use?

Trie Data Structure (Prefix Tree)

A Trie (pronounced "try") is a tree-based data structure used to store and search words efficiently. It's mainly used in applications like autocomplete, spell checking, and IP routing.

1. Why Use a Trie?

* Fast lookups – O(m) time complexity (where m = length of the word).
* Efficient storage – Common prefixes are stored once.
* Great for prefix-based searches – E.g., searching words starting with "ca" returns ["cat", "car", "cart"].

2. Trie Node Structure

Each node in a Trie contains:

• A dictionary (children) for storing next letters.
• A boolean (is_end_of_word) to mark the end of a word.

Implementation in Python

class TrieNode:
    def __init__(self):
        self.children = {}  # Dictionary to store child nodes
        self.is_end_of_word = False  # Marks if it's the end of a word

class Trie:
    def __init__(self):
        self.root = TrieNode()  # Root node (empty)

    def insert(self, word):
        """ Inserts a word into the Trie """
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # Create new node if not present
            node = node.children[char]  # Move to the next node
        node.is_end_of_word = True  # Mark last node as end of word

    def search(self, word):
        """ Returns True if the word is found in the Trie """
        node = self.root
        for char in word:
            if char not in node.children:
                return False  # Word not found
            node = node.children[char]
        return node.is_end_of_word  # Return True if it's an exact word

    def starts_with(self, prefix):
        """ Returns True if any word starts with the given prefix """
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False  # Prefix not found
            node = node.children[char]
        return True  # Prefix found

# Example usage
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("cart")

print(trie.search("car"))  # Output: True
print(trie.search("can"))  # Output: False
print(trie.starts_with("ca"))  # Output: True

3. Trie Operations & Complexity

* Faster than searching in lists or sets!

4. When to Use a Trie?

* Autocomplete & Spell Checking (Google Search, AutoCorrect).
* Word Dictionary (Lexicons, Word Games).
* IP Routing & Prefix Matching (Network Routing).

Using the Counter Class from collections in Python

The Counter class from the collections module is a specialized dictionary used for counting hashable objects (e.g., numbers, strings, tuples). It simplifies counting elements in lists, strings, and other iterables.

1. Creating a Counter

Counting Elements in a List

from collections import Counter

# Example list
numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

# Create a Counter
counter = Counter(numbers)

print(counter)  
# Output: Counter({4: 4, 3: 3, 2: 2, 1: 1})

* Counts occurrences of each element.

Counting Characters in a String

text = "banana"
char_count = Counter(text)

print(char_count)  
# Output: Counter({'a': 3, 'n': 2, 'b': 1})

2. Accessing Counter Data

print(counter[3])  # Output: 3 (count of 3 in list)
print(counter[5])  # Output: 0 (5 is not in the list)

* Returns 0 for missing elements (instead of KeyError).

3. Most Common Elements

top_counts = counter.most_common(2)  # Get top 2 most common elements
print(top_counts)  
# Output: [(4, 4), (3, 3)]

* Great for finding the most frequent items.

4. Arithmetic & Set Operations

Counters support addition, subtraction, intersection, and union.

c1 = Counter("apple")
c2 = Counter("pear")

# Add counts
print(c1 + c2)  
# Output: Counter({'p': 3, 'a': 2, 'e': 2, 'l': 1, 'r': 1})

# Subtract counts
print(c1 - c2)  
# Output: Counter({'l': 1})

* Useful for bag-of-words models in NLP!

5. Converting Counter to a List

elements = list(counter.elements())
print(elements)  
# Output: [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

* Expands the counts back into a list.

6. When to Use Counter?

* Counting words in a document (NLP).
* Finding the most common elements in a dataset.
* Histogram-like frequency analysis.

Implementing a Graph Using Adjacency List and Adjacency Matrix in Python

Graphs can be represented in two primary ways:
1. Adjacency List – Space-efficient for sparse graphs.
2. Adjacency Matrix – Faster lookups but uses more space.

1. Graph Representation: Adjacency List

An adjacency list uses a dictionary where each key is a node, and the value is a list of adjacent nodes.
* Efficient for sparse graphs (O(V + E) space).
* Faster traversal (O(V + E) time complexity).
* Slower edge lookups (O(degree) time).

Implementation of Graph Using Adjacency List

class GraphAdjList:
    def __init__(self):
        self.graph = {}  # Dictionary to store adjacency list

    def add_edge(self, u, v):
        """ Adds an edge from u to v (undirected) """
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append(v)
        self.graph[v].append(u)  # Remove this for a directed graph

    def display(self):
        """ Prints adjacency list """
        for node in self.graph:
            print(f"{node} -> {self.graph[node]}")

# Example usage
g = GraphAdjList()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 4)

g.display()
# Output:
# 1 -> [2, 3]
# 2 -> [1, 4]
# 3 -> [1, 4]
# 4 -> [2, 3]

* Best for graphs with fewer edges (sparse graphs).

2. Graph Representation: Adjacency Matrix

An adjacency matrix is a 2D matrix (V × V) where matrix[i][j] = 1 if there is an edge, otherwise 0.
* Fast edge lookup O(1).
* Good for dense graphs.
* Consumes more space O(V²).

Implementation of Graph Using Adjacency Matrix

class GraphAdjMatrix:
    def __init__(self, size):
        self.size = size
        self.matrix = [[0] * size for _ in range(size)]  # Initialize with zeros

    def add_edge(self, u, v):
        """ Adds an edge from u to v (undirected) """
        self.matrix[u][v] = 1
        self.matrix[v][u] = 1  # Remove this for a directed graph

    def display(self):
        """ Prints adjacency matrix """
        for row in self.matrix:
            print(row)

# Example usage
g = GraphAdjMatrix(5)  # 5 nodes (0-4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)

g.display()
# Output:
# [0, 1, 1, 0, 0]
# [1, 0, 0, 1, 0]
# [1, 0, 0, 0, 1]
# [0, 1, 0, 0, 0]
# [0, 0, 1, 0, 0]

* Best for dense graphs (many edges).

3. Comparison: Adjacency List vs. Adjacency Matrix

4. When to Use Each?

* Adjacency List – When memory efficiency is needed (e.g., social networks, road networks).
* Adjacency Matrix – When fast edge lookup is required (e.g., Floyd-Warshall shortest path algorithm).