This tutorial addresses interview inquiries that integrate nested loops and functions, which frequently appear in technical interviews to evaluate candidates' problem-solving abilities.
Basic Nested Loop Concepts
1. What is a nested loop?
A nested loop refers to a loop that exists within another loop. For every iteration of the outer loop, the inner loop executes all of its iterations.
Example:
Example
for i in range(3):
for j in range(2):
print(f"i={i}, j={j}")
Output:
Output
i=0, j=0
i=0, j=1
i=1, j=0
i=1, j=1
i=2, j=0
i=2, j=1
### 1. What is the time complexity of nested loops?What is the time complexity of nested loops?
When two loops are nested and each runs n times, the resulting time complexity is O(n²). In the case of three nested loops, the time complexity increases to O(n³).
Example:
Example
# O(n²) complexity
def print_pairs(n):
for i in range(n): # runs n times
for j in range(n): # runs n times for each i
print(f"({i}, {j})")
1. How do you break out of nested loops?How do you break out of nested loops?
Utilize a flag variable or implement a function that employs a return statement to break out of nested loops.
Example using flag:
Example
found = False
for i in range(5):
for j in range(5):
if i * j == 12:
print(f"Found: {i} * {j} = 12")
found = True
break
if found:
break
Example using function:
Example
def find_product():
for i in range(5):
for j in range(5):
if i * j == 12:
print(f"Found: {i} * {j} = 12")
return
find_product()
Pattern Printing Questions
1. Write a function to print a square patternWrite a function to print a square pattern
Example
def print_square(n):
for i in range(n):
for j in range(n):
print("*", end=" ")
print()
print_square(4)
Output:
Output
* * * *
* * * *
* * * *
* * * *
1.Write a function to print a right triangle pattern
Example
def print_triangle(n):
for i in range(1, n + 1):
for j in range(i):
print("*", end=" ")
print()
print_triangle(5)
Output:
Output
*
* *
* * *
* * * *
* * * * *
1.Write a function to print an inverted triangle
Example
def print_inverted_triangle(n):
for i in range(n, 0, -1):
for j in range(i):
print("*", end=" ")
print()
print_inverted_triangle(5)
Output:
Output
* * * * *
* * * *
* * *
* *
*
7. Write a function to print a pyramid pattern
Example
def print_pyramid(n):
for i in range(1, n + 1):
# Print spaces
for j in range(n - i):
print(" ", end="")
# Print stars
for k in range(2 * i - 1):
print("*", end="")
print()
print_pyramid(5)
Output:
Output
*
***
*****
*******
*********
8. Write a function to print a diamond pattern
Example
def print_diamond(n):
# Upper half
for i in range(1, n + 1):
print(" " * (n - i) + "*" * (2 * i - 1))
# Lower half
for i in range(n - 1, 0, -1):
print(" " * (n - i) + "*" * (2 * i - 1))
print_diamond(5)
Output:
Output
*
***
*****
*******
*********
*******
*****
***
*
9. Write a function to print a number pattern
Example
def print_number_pattern(n):
for i in range(1, n + 1):
for j in range(1, i + 1):
print(j, end=" ")
print()
print_number_pattern(5)
Output:
Output
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
10. Write a function to print Floyd's triangle
Example
def print_floyds_triangle(n):
num = 1
for i in range(1, n + 1):
for j in range(i):
print(num, end=" ")
num += 1
print()
print_floyds_triangle(5)
Output:
Output
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
Matrix and Array Operations
11. Write a function to create a 2D matrix
Example
def create_matrix(rows, cols, value=0):
matrix = []
for i in range(rows):
row = []
for j in range(cols):
row.append(value)
matrix.append(row)
return matrix
matrix = create_matrix(3, 4, 0)
print(matrix)
Output:
Output
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
12. Write a function to print a matrix
Example
def print_matrix(matrix):
for row in matrix:
for element in row:
print(element, end=" ")
print()
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print_matrix(matrix)
Output:
Output
1 2 3
4 5 6
7 8 9
13. Write a function to find sum of matrix elements
Example
def matrix_sum(matrix):
total = 0
for row in matrix:
for element in row:
total += element
return total
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(matrix_sum(matrix)) # 45
14. Write a function to transpose a matrix
Example
def transpose_matrix(matrix):
rows = len(matrix)
cols = len(matrix[0])
result = []
for j in range(cols):
new_row = []
for i in range(rows):
new_row.append(matrix[i][j])
result.append(new_row)
return result
matrix = [[1, 2, 3], [4, 5, 6]]
transposed = transpose_matrix(matrix)
print_matrix(transposed)
Output:
Output
1 4
2 5
3 6
15. Write a function to multiply two matrices
Example
def multiply_matrices(mat1, mat2):
rows1 = len(mat1)
cols1 = len(mat1[0])
cols2 = len(mat2[0])
result = []
for i in range(rows1):
row = []
for j in range(cols2):
sum_val = 0
for k in range(cols1):
sum_val += mat1[i][k] * mat2[k][j]
row.append(sum_val)
result.append(row)
return result
mat1 = [[1, 2], [3, 4]]
mat2 = [[5, 6], [7, 8]]
result = multiply_matrices(mat1, mat2)
print_matrix(result)
Output:
Output
19 22
43 50
Searching and Traversal
16. Write a function to search in a 2D matrix
Example
def search_matrix(matrix, target):
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == target:
return (i, j)
return None
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
result = search_matrix(matrix, 5)
print(result) # (1, 1)
17. Write a function to find maximum element in each row
Example
def max_in_rows(matrix):
result = []
for row in matrix:
max_val = row[0]
for element in row:
if element > max_val:
max_val = element
result.append(max_val)
return result
matrix = [[1, 5, 3], [9, 2, 7], [4, 8, 6]]
print(max_in_rows(matrix)) # [5, 9, 8]
18. Write a function to find diagonal sum
Example
def diagonal_sum(matrix):
n = len(matrix)
total = 0
for i in range(n):
total += matrix[i][i] # main diagonal
return total
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(diagonal_sum(matrix)) # 15
Advanced Problems
19. Write a function to spiral print a matrix
Example
def spiral_print(matrix):
result = []
while matrix:
# Print first row
result.extend(matrix.pop(0))
# Print last column
if matrix and matrix[0]:
for row in matrix:
result.append(row.pop())
# Print last row in reverse
if matrix:
result.extend(matrix.pop()[::-1])
# Print first column in reverse
if matrix and matrix[0]:
for row in matrix[::-1]:
result.append(row.pop(0))
return result
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(spiral_print(matrix))
Output:
Output
[1, 2, 3, 6, 9, 8, 7, 4, 5]
20. Write a function to rotate matrix 90 degrees
Example
def rotate_matrix_90(matrix):
n = len(matrix)
# Transpose
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse each row
for i in range(n):
matrix[i].reverse()
return matrix
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotated = rotate_matrix_90(matrix)
print_matrix(rotated)
Output:
Output
7 4 1
8 5 2
9 6 3
Combining Loops with Functions
21. Write a function that uses nested loops to check prime numbers
Example
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def print_primes_in_range(start, end):
for num in range(start, end + 1):
if is_prime(num):
print(num, end=" ")
print_primes_in_range(1, 20)
Output:
Output
2 3 5 7 11 13 17 19
22. Write a function to generate Pascal's triangle
Example
def generate_pascals_triangle(n):
triangle = []
for i in range(n):
row = [1]
if triangle:
last_row = triangle[-1]
for j in range(len(last_row) - 1):
row.append(last_row[j] + last_row[j + 1])
row.append(1)
triangle.append(row)
return triangle
def print_pascals_triangle(n):
triangle = generate_pascals_triangle(n)
for row in triangle:
print(" ".join(map(str, row)))
print_pascals_triangle(6)
Output:
Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
23. Write a function to find all pairs with given sum
Example
def find_pairs_with_sum(arr, target):
pairs = []
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] + arr[j] == target:
pairs.append((arr[i], arr[j]))
return pairs
arr = [1, 2, 3, 4, 5, 6]
print(find_pairs_with_sum(arr, 7))
Output:
Output
[(1, 6), (2, 5), (3, 4)]
24. Write a function to check if a matrix is symmetric
Example
def is_symmetric(matrix):
n = len(matrix)
for i in range(n):
for j in range(n):
if matrix[i][j] != matrix[j][i]:
return False
return True
matrix1 = [[1, 2, 3], [2, 4, 5], [3, 5, 6]]
matrix2 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(is_symmetric(matrix1)) # True
print(is_symmetric(matrix2)) # False
25. Write a function to find saddle point in matrix
Example
def find_saddle_point(matrix):
for i in range(len(matrix)):
# Find minimum in row
min_val = min(matrix[i])
col_index = matrix[i].index(min_val)
# Check if it's maximum in column
is_saddle = True
for k in range(len(matrix)):
if matrix[k][col_index] > min_val:
is_saddle = False
break
if is_saddle:
return (i, col_index, min_val)
return None
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
result = find_saddle_point(matrix)
if result:
print(f"Saddle point at ({result[0]}, {result[1]}) = {result[2]}")
Best Practices
Tips for Nested Loops and Functions:
1.
- Enhance nested loops - Prevent superfluous iterations
- Implement descriptive variable names - Variables like i, j, k should convey distinct ideas
- Terminate early - Exit loops once the specified condition is satisfied
- Evaluate time complexity - Be mindful of the effects of O(n²), O(n³)
- Utilize functions - Divide intricate nested logic into more manageable functions
- Examine edge cases - Consider scenarios involving empty arrays, single elements, and large datasets
Summary
Integrating nested loops with functions is a crucial competency evaluated during programming interviews. Engaging in practice with these patterns can enhance your problem-solving skills and facilitate the creation of efficient code.