1.

Reverse a string
Method 1. Slicing Approach
In [2]: def rev_string(text):
return text[::-1]

rev_string('hello world!')

Out[2]: '!dlrow olleh'

Explaination:
It uses Python’s slicing feature.

text[::-1] means reverse the string.

Time Complexity: O(n)

Space Complexity: O(n)

This is efficient and clean.

Method 2. Iterative Approach

In [3]: ## Alternative Approach
def rev_string_alt(text):
result = ''
for char in text:
result = char + result
return result

rev_string_alt('hello world!')
Out[3]: '!dlrow olleh'

Example:
For 'abc' :

result = '', char = 'a' → result = 'a'

result = 'a', char = 'b' → result = 'b' + 'a' → 'ba'

result = 'ba', char = 'c' → result = 'c' + 'ba' → 'cba'

Explaination:
It starts with an empty string.

It adds each character at the beginning.

Time Complexity: O(n²) because of repeated concatenations.

Space Complexity: O(n)

This is inefficient for large strings.

Method 3. Recursive Approach

In [5]: def rev_string_rec(text):
if len(text)<=1:
return text
return text[-1] + rev_string_rec(text[:-1])

rev_string_rec('hello world!')

Out[5]: '!dlrow olleh'

Example
Example 'abc' :

'abc' → return 'c' + rev_string('ab')

'ab' → return 'b' + rev_string('a')

'a' → base case → return 'a'

combine → 'b' + 'a' → 'ba'

'c' + 'ba' → 'cba'

Explaination:
It reverses by taking the last character and appending the recursive call for the rest.
 Time Complexity: O(n²), due to slicing.

Space Complexity: O(n), due to recursion stack.

This is elegant but inefficient for large strings.

2. Check if String is Palindrome

Method 1. Clean and Compare

In [7]: def is_palindrome(text):
cleaned = ''.join([Link]() for char in text if [Link]())
return cleaned == cleaned[::-1]

is_palindrome('racecar')

Out[7]: True

Explanation:
First, clean the string: keep only alphanumeric characters, convert to lowercase
[Link]() checks if character is letter or digit
Compare cleaned string with its reverse
Time Complexity: O(n)
Space Complexity: O(n)

Method 2. Two Pointers

In [11]: def is_palindrome_pt(text):
left,right = 0, len(text)-1
while left<right:
if text[left] != text[right]:
return False
left += 1
right -= 1
return True

is_palindrome_pt('racecar')

Out[11]: True

✅ Working – Example:
Input: 'racecar'
Step by step:

1. left = 0 (r), right = 6 (r) → match → continue

 2. left = 1 (a), right = 5 (a) → match → continue

3. left = 2 (c), right = 4 (c) → match → continue

4. left = 3 (e), right = 3 (e) → pointers meet → return True

Input: 'hello'
left = 0 (h), right = 4 (o) → mismatch → return

✅ Time Complexity:
O(n) , where n = length of the string.
every character checked on once time only.

✅ Space Complexity:
O(1) : no need to extra space (only for pointers).

Two Sum Problem

Method 1. Brute Force Approach

In [28]: def two_sum_brute(arr,target):
for i in range(len(arr)):
for j in range(i+1,len(arr)):
if arr[i] + arr[j] == target:
return [i,j]

return []

two_sum_brute([2,7,11,15],18)

Out[28]: [1, 2]

✅ Working – Example
For nums = [2, 7, 11, 15], target = 9 :

i = 0 → nums[0] = 2

j = 1 → nums[1] = 7 → 2 + 7 = 9 → ✅ match → return [0, 1]

The function stops once it finds the pair.

✅ Complexity
 Time Complexity: O(n²) , because it checks all pairs.

Space Complexity: O(1) , no extra space used apart from the result.

⚠ Works fine for small inputs but becomes slow for large arrays.

Method 2. Optimized Approach ( Usinh Hash

Map/Dictionary)
In [26]: def two_sum_opt(arr,target):
seen = {}
for i , num in enumerate(arr):
complement = target - num
if complement in seen:
return [seen[complement],i]
seen[num]=i
return []

two_sum_opt([2,7,11,15],18)

Out[26]: [1, 2]

Working Example
For nums = [2, 7, 11, 15], target = 9 :

i=0, num=2 → complement=7 → not seen → store {2:0}.

i=1, num=7 → complement=2 → found in map → return [0, 1].

Complexity
Time: O(n) (one pass).

Space: O(n) (hash map).

✅ Very efficient for large inputs.

FizzBuzz Problem
In [33]: def fizzbuzz(n):
result = []
for i in range(1,n+1):
if i%15 == 0:
[Link]("FizzBuzz")
elif i%3 == 0:
[Link]("Fizz")
elif i%5 == 0:
[Link]("Buzz")
else:
[Link](str(i))
 return result

fizzbuzz(15)

Out[33]: ['1',
'2',
'Fizz',
'4',
'Buzz',
'Fizz',
'7',
'8',
'Fizz',
'Buzz',
'11',
'Fizz',
'13',
'14',
'FizzBuzz']

Explanation:
Classic programming problem: replace multiples of 3 "Fizz" , multiples of 5 with
"Buzz"
Check for 15 first (since 15 = 3×5, divisible by both) "FizzBuzz"
% operator gives remainder after division
Time Complexity: O(n)
Space Complexity: O(n) - storing results

5. Find Max Element

Method 1. Manual Iteration
In [34]: def find_max(arr):
if not arr:
return None
max_val = arr[0]
for num in arr[1:]:
if num>max_val:
max_val = num
return max_val

find_max([2,7,5,11])

Out[34]: 11

Explaination:
Start with first element as maximum
Compare each subsequent element
Update maximum when we find larger value
Time Complexity: O(n)
 Space Complexity: O(1)

Method 2. Built-in Function

In [37]: def find_max_builtin(arr):
return max(arr) if arr else None

find_max_builtin([2,7,5,11])

Out[37]: 11

Explaination:
Uses Python's built-in max() function
Ternary operator handles empty array case
Time Complexity: O(n)
Space Complexity: O(1)

6. Remove Duplicates
Method 1. Using Set (Order Not Preserved)
In [38]: def remove_duplicates(arr):
return list(set(arr))

remove_duplicates([2,5,7,11,2,5,7])

Out[38]: [2, 11, 5, 7]

Explanation:
Convert list to set (automatically removes duplicates)
Convert back to list
Drawback: Original order is lost
Time Complexity: O(n)
Space Complexity: O(n)

Method 2. Preserve Order

In [39]: def remove_duplicates_pre(arr):
seen = set()
result = []
for item in arr:
if item not in seen:
[Link](item)
[Link](item)
return result

remove_duplicates_pre([2,5,7,11,2,5,7])
Out[39]: [2, 5, 7, 11]

Explanation:
Maintain a set to track seen elements
Only add to result if we haven't seen the element before
Preserves original order of first occurrences
Time Complexity: O(n)
Space Complexity: O(n)

7. Fibonacci Sequence
Method 1: Recursive (Inefficient)
In [46]: def fibonacci(n):
if n<=1:
return n
return fibonacci(n-1) + fibonacci(n-2)

fibonacci(25)

Out[46]: 75025

Explanation:
Classic recursive definition: F(n) = F(n-1) + F(n-2)
Problem: Recalculates same values multiple times
Time Complexity: O(2^n) - exponential!
Space Complexity: O(n) - call stack depth

Method 2. Iterative (Efficient)

In [47]: def fibonacci_iter(n):
if n<=1:
return n
a,b = 0,1
for _ in range(2,n+1):
a,b = b, a+b
return b

fibonacci_iter(25)

Out[47]: 75025

Explanation:
Keep track of only last two values
Update them iteratively: new_a = old_b, new_b = old_a + old_b
Python's tuple assignment makes this elegant
 Time Complexity: O(n)
Space Complexity: O(1)

Method 3. Memoization (Top-Down DP)

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

fib_memo(50)

Out[53]: 12586269025

Explanation:
Cache results to avoid recalculation
Warning: Using mutable default argument (memo={}) can cause issues
Time Complexity: O(n)
Space Complexity: O(n)

8. Check if Number is Prime

In [54]: def is_prime(n):
if n<2:
return False
if n==2:
return True
if n%2 ==0:
return False

for i in range(3,int(n**0.5)+1,2):
if n%i ==0:
return False
return True

Examples:
Example 1:
print(is_prime(11))

11 > 2 → continue.

11 is odd → continue.

Check i = 3 → 11 % 3 = 2 → not divisible.

√11 ≈ 3.3 → loop ends → return True .

 Example 2:
print(is_prime(25))

25 > 2 → continue.

25 is odd → continue.

Check i = 3 → not divisible.

Check i = 5 → 25 % 5 = 0 → divisible → return False .

Explanation:
Key insight: If n has a divisor > √n, it must also have one ≤ √n
Skip even numbers after 2 for efficiency
Only check odd potential divisors
range(3, int(n**0.5) + 1, 2) generates 3, 5, 7, ... up to √n
Time Complexity: O(√n), because we only check up to the square root of n.
Space Complexity: O(1),only a few variables are used → constant extra space.

9. Count Character Frequency

Method 1. Manual Dictionary
In [55]: def count_chars(s):
char_count={}
for char in s:
char_count[char] = char_count.get(char,0)+1
return char_count

count_chars("rahul rathour")

Out[55]: {'r': 3, 'a': 2, 'h': 2, 'u': 2, 'l': 1, ' ': 1, 't': 1, 'o': 1}

Explanation:
[Link](key, default) returns value for key, or default if key doesn't exist
Increment count for each character occurrence
Time Complexity: O(n)
Space Complexity: O(k) where k is number of unique characters

Method 2. Using Counter

In [56]: from collections import Counter
def count_chars_counter(s):
return dict(Counter(s))

count_chars_counter("rahul rathour")
Out[56]: {'r': 3, 'a': 2, 'h': 2, 'u': 2, 'l': 1, ' ': 1, 't': 1, 'o': 1}

Explanation:
Counter is a dictionary subclass designed for counting
More concise and Pythonic
Time Complexity: O(n)
Space Complexity: O(k)

10. Binary Search

✅ Binary Search
Given a sorted list arr and a target value target , the goal is to find the index of
target in arr .
If the target is not present in the list, return -1 .

Binary search works by repeatedly dividing the search space in half, making it much
faster than linear search for large lists.

Example:
arr = [1, 3, 5, 7, 9, 11, 13] , target = 7 → Output: 3
arr = [1, 3, 5, 7, 9, 11, 13] , target = 8 → Output: -1

In [65]: 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

print("Index of 7:",binary_search([1, 3, 5, 7, 9, 11, 13],target=7))

print("Index of 8:",binary_search([1, 3, 5, 7, 9, 11, 13],target=8))

Index of 7: 3
Index of 8: -1

✅ Step-by-step Explanation
1. Initialize pointers
We start with left = 0 and right = len(arr) - 1 , covering the whole array.
 2. Loop until pointers cross
The loop continues while left <= right , meaning there’s still a search space.

3. Find the middle element

mid = (left + right) // 2 helps us find the center.

4. Check if the target is found

If arr[mid] is equal to target , we return the index.

5. Adjust the search space

If arr[mid] < target , the target is in the right half → move left to mid
+ 1.
If arr[mid] > target , the target is in the left half → move right to mid -
1.
6. If the loop ends
If the target is not found after checking all possibilities → return -1 .

✅ Example Walkthrough
Example 1: Searching for 7 in [1, 3, 5, 7, 9, 11, 13]
Initial pointers → left = 0 , right = 6

Step 1:

mid = (0 + 6) // 2 = 3 , arr[3] = 7
Found → return index 3

Example 2: Searching for 8 in [1, 3, 5, 7, 9, 11, 13]

Initial pointers → left = 0 , right = 6

Step 1:

mid = 3 , arr[3] = 7
7 < 8 → search right half → left = 4

Step 2:

mid = (4 + 6) // 2 = 5 , arr[5] = 11
11 > 8 → search left half → right = 4

Step 3:

mid = 4 , arr[4] = 9
9 > 8 → search left half → right = 3

Now left = 4 , right = 3 , pointers crossed → return -1 (target not found)

 ✅ Time and Space Complexity
Time complexity: O(log n), where n is the length of the array.
Space complexity: O(1), because we only use a few extra variables.

11. Valid Parenthesis

✅ Valid Parentheses Problem

You are given a string s containing only the characters '(' , ')' , '{' , '}' , '[' ,
']' .
The task is to check if the string is valid, meaning:

1. Every opening bracket must be closed by the same type of bracket.

2. Brackets must be closed in the correct order.

Example:
"()" → ✅ valid
"()[]{}" → ✅ valid
"(]" → ❌ invalid
"([)]" → ❌ invalid
"{[]}" → ✅ valid

In [59]: def is_valid_parenthesis(s):

stack = []
mapping = {
")":"(",
"}":"{",
"]":"["
}

for char in s:
if char in mapping:
if not stack or [Link]() != mapping[char]:
return False
else:
[Link](char)
return len(stack) ==0

is_valid_parenthesis("[}[]]")

Out[59]: False

✅ Step-by-step Explanation
1. Initialize stack
We use a stack to store opening brackets.
 2. Create a mapping dictionary
The mapping dictionary maps closing brackets to their corresponding opening
brackets.

3. Iterate through the string

If the character is a closing bracket:

Check if the stack is empty → return False .
Pop the last element and check if it matches → if not → return False .
If the character is an opening bracket:
Push it onto the stack.
4. Final check
After checking all characters, the stack must be empty if the brackets are valid.
Return True if empty, otherwise False .

✅ Example Walkthrough
Let's walk through a few examples to understand how the algorithm works.

Example 1: "()[]{}"
Start with an empty stack: []

Step 1 → char = '('

It's an opening bracket → push → stack = ['(']

Step 2 → char = ')'

It's a closing bracket → pop '(' → matches → stack = []

Step 3 → char = '['

Opening → push → stack = ['[']

Step 4 → char = ']'

Closing → pop '[' → matches → stack = []

Step 5 → char = '{'

Opening → push → stack = ['{']

Step 6 → char = '}'

Closing → pop '{' → matches → stack = []

✔ Final stack is empty → return True

Example 2: "([)]"
Start with an empty stack: []

Step 1 → char = '('

Opening → push → stack = ['(']

Step 2 → char = '['

Opening → push → stack = ['(', '[']

Step 3 → char = ')'

Closing → pop '[' → expected '(' → mismatch

✔ Return False

Example 3: "{[]}"
Start with an empty stack: []

Step 1 → char = '{'

Opening → push → stack = ['{']

Step 2 → char = '['

Opening → push → stack = ['{', '[']

Step 3 → char = ']'

Closing → pop '[' → matches → stack = ['{']

Step 4 → char = '}'

Closing → pop '{' → matches → stack = []

✔ Final stack is empty → return True

✅ Time and Space Complexity

Time complexity: O(n), where n is the length of the string, because we check each
character once.
Space complexity: O(n), in the worst case when all characters are opening brackets.

12. Merge Two Sorted Lists

✅ Merge Two Sorted Lists

 Given two sorted lists, list1 and list2 , the task is to merge them into one sorted
list.

Example:
list1 = [1, 3, 5]
list2 = [2, 4, 6]

Output → [1, 2, 3, 4, 5, 6]

In [63]: def merge_sorted_lists(list1,list2):

result = []
i=j=0 # pointer for list 1 and list2

# compare elements and add smaller one to result

while i < len(list1) and j< len(list2):
if list1[i] <= list2[j]:
[Link](list1[i])
i+=1
else:
[Link](list2[j])
j+=1

[Link](list1[i:])
[Link](list2[j:])
return result

# Example run
list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged_list = merge_sorted_lists(list1, list2)
print("Merged List:", merged_list)

Merged List: [1, 2, 3, 4, 5, 6]

✅ Step-by-step Explanation
1. Initialize the result list and pointers
We create an empty result list and two pointers i and j starting at the
beginning of list1 and list2 .

2. Compare elements from both lists

We compare list1[i] and list2[j] at each step:

If list1[i] is smaller or equal, add it to result and move pointer i .

Otherwise, add list2[j] to result and move pointer j .
3. Handle leftover elements
After one list is fully traversed, add the remaining elements from the other list using
extend() .

4. Return the merged result

Once all elements are processed, return the merged list.
✅ Example Walkthrough
Let's merge:

list1 = [1, 3, 5]
list2 = [2, 4, 6]

Initial state:
result = []
i = 0 , pointing at 1
j = 0 , pointing at 2

Step 1 → Compare 1 and 2

1 <= 2 → add 1 → result = [1] , i = 1

Step 2 → Compare 3 and 2

3 > 2 → add 2 → result = [1, 2] , j = 1

Step 3 → Compare 3 and 4

3 <= 4 → add 3 → result = [1, 2, 3] , i = 2

Step 4 → Compare 5 and 4

5 > 4 → add 4 → result = [1, 2, 3, 4] , j = 2

Step 5 → Compare 5 and 6

5 <= 6 → add 5 → result = [1, 2, 3, 4, 5] , i = 3

Final step → Add remaining elements

list1 finished → nothing left
list2 has 6 → add → result = [1, 2, 3, 4, 5, 6]

✔ Final output: [1, 2, 3, 4, 5, 6]

✅ Time and Space Complexity

Time complexity: O(n + m), where n and m are the lengths of list1 and
list2 .
Space complexity: O(n + m), because we create a new list to store the merged
result.