Topic: Mastering Recursion — From Basics to Advanced Applications

---

What is Recursion?

• Recursion is a technique where a function calls itself to solve smaller instances of a problem until reaching a base case.

---

Basic Structure

• Every recursive function needs:

* A base case to stop recursion.

* A recursive case that breaks the problem into smaller parts.

---

Simple Example: Fibonacci Numbers

def fibonacci(n):
    if n <= 1:
        return n  # base case
    else:
        return fibonacci(n-1) + fibonacci(n-2)  # recursive case

---

Drawbacks of Naive Recursion

• Repeated calculations cause exponential time complexity.

• Can cause stack overflow on large inputs.

---

Improving Recursion: Memoization

• Store results of subproblems to avoid repeated work.

memo = {}
def fib_memo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

---

Advanced Concepts

• Tail Recursion: Recursive call is the last operation. Python does not optimize tail calls but understanding it is important.

• Divide and Conquer Algorithms: Recursion breaks problems into subproblems (e.g., Merge Sort, Quick Sort).

---

Example: Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

---

Exercise

• Implement a recursive function to solve the Tower of Hanoi problem for *n* disks and print the moves.

---

#Algorithms #Recursion #Memoization #DivideAndConquer #CodingExercise

https://t.iss.one/DataScience4

Topic: Data Structures – Trees – Top 15 Interview Questions with Answers

---

### 1. What is a tree data structure?

A hierarchical structure with nodes connected by edges, having a root node and child nodes with no cycles.

---

### 2. What is the difference between binary tree and binary search tree (BST)?

A binary tree allows up to two children per node; BST maintains order where left child < node < right child.

---

### 3. What are the types of binary trees?

Full, perfect, complete, skewed (left/right), and balanced binary trees.

---

### 4. Explain tree traversal methods.

Inorder (LNR), Preorder (NLR), Postorder (LRN), and Level Order (BFS).

---

### 5. What is a balanced tree? Why is it important?

A tree where the height difference between left and right subtrees is minimal to ensure O(log n) operations.

---

### 6. What is an AVL tree?

A self-balancing BST maintaining balance factor (-1, 0, 1) with rotations to balance after insert/delete.

---

### 7. What are rotations in AVL trees?

Operations (Left, Right, Left-Right, Right-Left) used to rebalance the tree after insertion or deletion.

---

### 8. What is a Red-Black Tree?

A balanced BST with red/black nodes ensuring balance via color rules, offering O(log n) operations.

---

### 9. How does a Trie work?

A tree structure used for storing strings, where nodes represent characters, allowing fast prefix searches.

---

### 10. What is the height of a binary tree?

The number of edges on the longest path from root to a leaf node.

---

### 11. How do you find the lowest common ancestor (LCA) of two nodes?

By traversing from root, checking if nodes lie in different subtrees, or by storing parent pointers.

---

### 12. What is the difference between DFS and BFS on trees?

DFS explores as far as possible along branches; BFS explores neighbors level by level.

---

### 13. How do you detect if a binary tree is a BST?

Check if inorder traversal yields a sorted sequence or verify node values within valid ranges recursively.

---

### 14. What are leaf nodes?

Nodes with no children.

---

### 15. How do you calculate the number of nodes in a complete binary tree?

Using the formula: number\_of\_nodes = 2^(height + 1) - 1 (if perfect), else traverse and count.

---

### Exercise

Write functions for inorder, preorder, postorder traversals, check if tree is BST, and find LCA of two nodes.

---

#DSA #Trees #InterviewQuestions #BinaryTrees #Python #Algorithms

https://t.iss.one/DataScience4

In Python interviews, understanding common algorithms like binary search is crucial for demonstrating problem-solving efficiency—often asked to optimize time complexity from O(n) to O(log n) for sorted data, showing your grasp of divide-and-conquer strategies.

# Basic linear search (O(n) - naive approach)
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

nums = [1, 3, 5, 7, 9]
print(linear_search(nums, 5))  # Output: 2

# Binary search (O(log n) - efficient for sorted arrays)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:  # Divide range until found or empty
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half
    return -1

sorted_nums = [1, 3, 5, 7, 9]
print(binary_search(sorted_nums, 5))  # Output: 2
print(binary_search(sorted_nums, 6))  # Output: -1 (not found)

# Edge cases
print(binary_search([], 1))      # Output: -1 (empty list)
print(binary_search(, 1))     # Output: 0 (single element)

#python #algorithms #binarysearch #interviews #timescomplexity #problemsolving

👉 @DataScience4

# Check if `n > 0` and `(n & (n - 1)) == 0`.

• Pow(x, n): Implement pow(x, n).

# Use exponentiation by squaring for an O(log n) solution.

• Majority Element:

# Boyer-Moore Voting Algorithm for an O(n) time, O(1) space solution.

• Excel Sheet Column Number:

# Base-26 conversion from string to integer.

• Valid Number:

# Use a state machine or a series of careful conditional checks.

• Integer to English Words:

# Handle numbers in chunks of three (hundreds, tens, ones) with helper functions.

• Sqrt(x): Compute and return the square root of x.

# Use binary search or Newton's method.

• Gray Code:

# Formula: `i ^ (i >> 1)`.

• Shuffle an Array:

# Implement the Fisher-Yates shuffle algorithm.

IX. Python Concepts

• Explain the GIL (Global Interpreter Lock):

# Conceptual: A mutex that allows only one thread to execute Python bytecode at a time in CPython.

• Difference between __str__ and __repr__:

# __str__ is for end-users (readable), __repr__ is for developers (unambiguous).

• Implement a Context Manager (with statement):

class MyContext:
    def __enter__(self): # setup
        return self
    def __exit__(self, exc_type, exc_val, exc_tb): # teardown
        pass

• Implement itertools.groupby logic:

# Iterate through the sorted iterable, collecting items into a sublist until the key changes.

#Python #CodingInterview #DataStructures #Algorithms #SystemDesign

━━━━━━━━━━━━━━━
By: @DataScience4 ✨

Learning Common Algorithms with Python

• This lesson covers fundamental algorithms implemented in Python. Understanding these concepts is crucial for building efficient software. We will explore searching, sorting, and recursion.

• Linear Search: This is the simplest search algorithm. It sequentially checks each element of the list until a match is found or the whole list has been searched. Its time complexity is O(n).

def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i  # Return the index of the found element
    return -1 # Return -1 if the element is not found

# Example
my_list = [4, 2, 7, 1, 9, 5]
print(f"Linear Search: Element 7 found at index {linear_search(my_list, 7)}")

• Binary Search: A much more efficient search algorithm, but it requires the list to be sorted first. It works by repeatedly dividing the search interval in half. Its time complexity is O(log n).

def binary_search(sorted_data, target):
    low = 0
    high = len(sorted_data) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if sorted_data[mid] < target:
            low = mid + 1
        elif sorted_data[mid] > target:
            high = mid - 1
        else:
            return mid # Element found
    return -1 # Element not found

# Example
my_sorted_list = [1, 2, 4, 5, 7, 9]
print(f"Binary Search: Element 7 found at index {binary_search(my_sorted_list, 7)}")

• Bubble Sort: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The process is repeated until the list is sorted. Its time complexity is O(n^2).

def bubble_sort(data):
    n = len(data)
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n-i-1):
            if data[j] > data[j+1]:
                # Swap the elements
                data[j], data[j+1] = data[j+1], data[j]
    return data

# Example
my_list_to_sort = [4, 2, 7, 1, 9, 5]
print(f"Bubble Sort: Sorted list is {bubble_sort(my_list_to_sort)}")

• Recursion (Factorial): Recursion is a method where a function calls itself to solve a problem. A classic example is calculating the factorial of a number (n!). It must have a base case to stop the recursion.

def factorial(n):
    # Base case: if n is 1 or 0, factorial is 1
    if n == 0 or n == 1:
        return 1
    # Recursive step: n * factorial of (n-1)
    else:
        return n * factorial(n - 1)

# Example
num = 5
print(f"Recursion: Factorial of {num} is {factorial(num)}")

#Python #Algorithms #DataStructures #Coding #Programming #LearnToCode

━━━━━━━━━━━━━━━
By: @DataScience4 ✨

✨ Quiz: Recursion in Python: An Introduction ✨

📖 Test your understanding of recursion in Python, including base cases, recursive structure, performance considerations, and common use cases.

🏷️ #intermediate #algorithms #python

✨ Quiz: Build a Hash Table in Python With TDD ✨

📖 Learn how Python hashing spreads values into buckets and powers hash tables. Practice collisions, uniform distribution, and test-driven development.

🏷️ #intermediate #algorithms #data-structures

✨ Quiz: Python Stacks, Queues, and Priority Queues in Practice ✨

📖 Test your knowledge of stacks, queues, deques, and priority queues with practical questions and Python coding exercises.

🏷️ #intermediate #algorithms #data-structures