25 Algorithm interview

questions
Here are some essential algorithm interview questions to help you
prepare:

1. Write a function to reverse a string.

2. Implement a function to check if a string is a palindrome.

3. Write a program to find the factorial of a number using recursion.

4. Create a function to find the maximum element in an array.

5. Write a function to merge two sorted arrays into one sorted array.

6. Implement a function to check if two strings are anagrams of each

other.

7. Write a program to find the Fibonacci sequence up to a given

number.

8. Create a function to count the number of vowels in a string.

9. Implement a function to find the first non-repeating character in a

string.

10. Write a program to sort an array using bubble sort.

11. Create a function to find the intersection of two arrays.

12. Implement a function to rotate an array to the right by a given

number of steps.

13. Write a program to find the longest common prefix among an

array of strings.

14. Create a function to determine if a number is prime.

15. Implement a function to find the missing number in an array of
integers from 1 to n.

16. Write a program to generate all permutations of a string.

17. Create a function to find the longest substring without

repeating characters.

18. Implement a binary search algorithm on a sorted array.

19. Write a program to find the kth largest element in an unsorted

array.

20. Create a function to check if a binary tree is balanced.

21. Implement a depth-first search (DFS) algorithm for a graph.

22. Write a program to find the shortest path in a weighted graph

using Dijkstra's algorithm.

23. Create a function to solve the N-Queens problem.

24. Implement a function to detect a cycle in a linked list.

25. Write a program to find all subsets of a given set.

1. Write a function to reverse a

string.
Why you might get asked this: Reversing a string is a
fundamental problem that tests your understanding of basic string
manipulation and algorithmic thinking, which is crucial for roles such
as software development.

How to answer:

 Explain the logic of iterating from the end of the string to the
beginning.

 Discuss the use of a new string or array to store the reversed

characters.
 Mention the time complexity of the solution, which is O(n).

Example answer:

"To reverse a string, you can iterate from the end of the string to the
beginning, appending each character to a new string. This approach
ensures that the time complexity remains O(n), where n is the
length of the string."

Here is a simple implementation in Python:

def reverse_string(s): return s[::-1]

2. Implement a function to check if a

string is a palindrome.
Why you might get asked this: Checking if a string is a
palindrome tests your ability to manipulate strings and understand
algorithmic efficiency, which is essential for technical roles such as
software engineering.

How to answer:

 Explain the concept of comparing characters from both ends of the

string towards the center.

 Discuss the use of two-pointer technique to optimize the solution.

 Mention the time complexity of the solution, which is O(n).

Example answer:

"To check if a string is a palindrome, you can use a two-pointer

technique, comparing characters from both ends of the string
towards the center. This approach ensures that the time complexity
remains O(n), where n is the length of the string."

Here is a simple implementation in Python:

 def is_palindrome(s): return s == s[::-1]

3. Write a program to find the

factorial of a number using
recursion.
Why you might get asked this: Finding the factorial of a number
using recursion tests your understanding of recursive functions and
mathematical concepts, which is crucial for technical roles such as
software development.

How to answer:

 Explain the concept of recursion and how it applies to calculating

factorials.

 Discuss the base case for the recursion to prevent infinite loops.

 Mention the time complexity of the solution, which is O(n).

Example answer:

"To find the factorial of a number using recursion, you define a

function that calls itself with the decremented value until it reaches
the base case of 1. This approach ensures that the time complexity
remains O(n), where n is the number for which the factorial is being
calculated."

Here is a simple implementation in Python:

def factorial(n): if n == 1: return 1 else: return n *

factorial(n - 1)

4. Create a function to find the

maximum element in an array.
 Why you might get asked this: Finding the maximum element in
an array tests your understanding of basic array manipulation and
algorithmic efficiency, which is essential for technical roles such as
software engineering.

How to answer:

 Explain the concept of iterating through the array to compare each

element.

 Discuss the use of a variable to keep track of the maximum value

found so far.

 Mention the time complexity of the solution, which is O(n).

Example answer:

"To find the maximum element in an array, you can iterate through
the array, comparing each element to a variable that keeps track of
the maximum value found so far. This approach ensures that the
time complexity remains O(n), where n is the number of elements in
the array."

Here is a simple implementation in Python:

def find_maximum(arr): max_val = arr[0] for num in arr:

if num > max_val: max_val = num return max_val

5. Write a function to merge two

sorted arrays into one sorted array.
Why you might get asked this: Merging two sorted arrays into
one sorted array tests your ability to handle array manipulation and
algorithmic efficiency, which is crucial for technical roles such as
software engineering.

How to answer:
 Explain the concept of using two pointers to traverse both arrays
simultaneously.

 Discuss the process of comparing elements and appending the

smaller one to the result array.

 Mention the time complexity of the solution, which is O(n + m).

Example answer:

"To merge two sorted arrays into one sorted array, you can use two
pointers to traverse both arrays simultaneously, comparing
elements and appending the smaller one to the result array. This
approach ensures that the time complexity remains O(n + m),
where n and m are the lengths of the two arrays."

Here is a simple implementation in Python:

def merge_sorted_arrays(arr1, arr2): merged_array = [] i,

j = 0, 0 while i < len(arr1) and j < len(arr2): if
arr1[i] < arr2[j]: merged_array.append(arr1[i]) i += 1
else: merged_array.append(arr2[j]) j += 1
merged_array.extend(arr1[i:])
merged_array.extend(arr2[j:]) return merged_array

6. Implement a function to check if

two strings are anagrams of each
other.
Why you might get asked this: Implementing a function to check
if two strings are anagrams of each other tests your ability to
manipulate strings and understand algorithmic efficiency, which is
crucial for technical roles such as software engineering.

How to answer:

 Explain the concept of sorting both strings and comparing them for
equality.
 Discuss the use of a frequency counter to count character
occurrences in both strings.

 Mention the time complexity of the solution, which is O(n log n) for
sorting or O(n) for the frequency counter approach.

Example answer:

"To check if two strings are anagrams, you can sort both strings and
compare them for equality. Alternatively, you can use a frequency
counter to count character occurrences in both strings and compare
the counts."

Here is a simple implementation in Python:

def are_anagrams(str1, str2): return sorted(str1) ==

sorted(str2)

7. Write a program to find the

Fibonacci sequence up to a given
number.
Why you might get asked this: Finding the Fibonacci sequence
up to a given number tests your understanding of recursion and
iterative algorithms, which is essential for technical roles such as
software development.

How to answer:

 Explain the concept of using either recursion or iteration to generate

the Fibonacci sequence.

 Discuss the base cases for the first two numbers in the sequence.

 Mention the time complexity of the solution, which is O(n) for the
iterative approach and O(2^n) for the naive recursive approach.

Example answer:
 "To find the Fibonacci sequence up to a given number, you can use
an iterative approach to generate the sequence efficiently. This
method ensures that the time complexity remains O(n), where n is
the number of terms in the sequence."

Here is a simple implementation in Python:

def fibonacci_sequence(n): fib_seq = [0, 1] while

len(fib_seq) < n: fib_seq.append(fib_seq[-1] + fib_seq[-
2]) return fib_seq[:n]

8. Create a function to count the

number of vowels in a string.
Why you might get asked this: Counting the number of vowels in
a string tests your ability to manipulate strings and understand
basic algorithmic concepts, which is essential for technical roles
such as software engineering.

How to answer:

 Explain the concept of iterating through the string and checking

each character.

 Discuss the use of a set to store vowel characters for quick lookup.

 Mention the time complexity of the solution, which is O(n).

Example answer:

"To count the number of vowels in a string, you can iterate through
the string and check each character against a set of vowels. This
approach ensures that the time complexity remains O(n), where n is
the length of the string."

Here is a simple implementation in Python:

 def count_vowels(s): vowels = {'a', 'e', 'i', 'o', 'u',
'A', 'E', 'I', 'O', 'U'} return sum(1 for char in s if
char in vowels)

9. Implement a function to find the

first non-repeating character in a
string.
Why you might get asked this: Implementing a function to find
the first non-repeating character in a string tests your ability to
manipulate strings and understand algorithmic efficiency, which is
crucial for technical roles such as software engineering.

How to answer:

 Explain the concept of using a hash map to count character

occurrences.

 Discuss iterating through the string a second time to find the first
character with a count of one.

 Mention the time complexity of the solution, which is O(n).

Example answer:

"To find the first non-repeating character in a string, you can use a
hash map to count character occurrences and then iterate through
the string a second time to find the first character with a count of
one. This approach ensures that the time complexity remains O(n),
where n is the length of the string."

Here is a simple implementation in Python:

def first_non_repeating_char(s): char_count = {} for char

in s: char_count[char] = char_count.get(char, 0) + 1 for
char in s: if char_count[char] == 1: return char return
None
 10. Write a program to sort an array
using bubble sort.
Why you might get asked this: Sorting an array using bubble
sort tests your understanding of basic sorting algorithms and their
efficiency, which is essential for technical roles such as software
engineering.

How to answer:

 Explain the concept of repeatedly swapping adjacent elements if

they are in the wrong order.

 Discuss the use of nested loops to iterate through the array multiple
times.

 Mention the time complexity of the solution, which is O(n^2).

Example answer:

"To sort an array using bubble sort, you repeatedly swap adjacent
elements if they are in the wrong order. This process continues until
the array is sorted, ensuring a time complexity of O(n^2)."

Here is a simple implementation in Python:

def bubble_sort(arr): n = len(arr) for i in range(n): for

j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j],
arr[j+1] = arr[j+1], arr[j] return arr

11. Create a function to find the

intersection of two arrays.
Why you might get asked this: Finding the intersection of two
arrays tests your ability to handle array manipulation and set
operations, which is crucial for technical roles such as software
engineering.
 How to answer:

 Explain the concept of using a set to store elements of the first

array.

 Discuss iterating through the second array to check for common

elements.

 Mention the time complexity of the solution, which is O(n + m).

Example answer:

"To find the intersection of two arrays, you can use a set to store
elements of the first array and then iterate through the second array
to check for common elements. This approach ensures that the time
complexity remains O(n + m), where n and m are the lengths of the
two arrays."

Here is a simple implementation in Python:

def intersection(arr1, arr2): set1 = set(arr1) return

[num for num in arr2 if num in set1]

12. Implement a function to rotate

an array to the right by a given
number of steps.
Why you might get asked this: Implementing a function to rotate
an array to the right by a given number of steps tests your
understanding of array manipulation and algorithmic efficiency,
which is crucial for technical roles such as software engineering.

How to answer:

 Explain the concept of using array slicing to achieve the rotation.

 Discuss the use of modulo operation to handle cases where the

number of steps exceeds the array length.
 Mention the time complexity of the solution, which is O(n).

Example answer:

"To rotate an array to the right by a given number of steps, you can
use array slicing to split the array and rearrange the parts. This
approach ensures that the time complexity remains O(n), where n is
the length of the array."

Here is a simple implementation in Python:

def rotate_array(arr, steps): steps = steps % len(arr)

return arr[-steps:] + arr[:-steps]

13. Write a program to find the

longest common prefix among an
array of strings.
Why you might get asked this: Finding the longest common
prefix among an array of strings tests your ability to handle string
manipulation and understand algorithmic efficiency, which is crucial
for technical roles such as software engineering.

How to answer:

 Explain the concept of comparing characters of each string at the

same position.

 Discuss the use of a loop to iterate through the characters until a

mismatch is found.

 Mention the time complexity of the solution, which is O(n * m),

where n is the number of strings and m is the length of the shortest
string.

Example answer:
 "To find the longest common prefix among an array of strings, you
can compare characters of each string at the same position until a
mismatch is found. This approach ensures that the time complexity
remains O(n * m), where n is the number of strings and m is the
length of the shortest string."

Here is a simple implementation in Python:

def longest_common_prefix(strs): if not strs: return ""

prefix = strs[0] for s in strs[1:]: while s[:len(prefix)]
!= prefix and prefix: prefix = prefix[:len(prefix)-1]
return prefix

14. Create a function to determine if

a number is prime.
Why you might get asked this: Determining if a number is prime
tests your understanding of basic mathematical concepts and
algorithmic efficiency, which is crucial for technical roles such as
software engineering.

How to answer:

 Explain the concept of checking divisibility from 2 up to the square

root of the number.

 Discuss the use of a loop to iterate through potential divisors.

 Mention the time complexity of the solution, which is O(√n).

Example answer:

"To determine if a number is prime, you can check its divisibility

from 2 up to the square root of the number. This approach ensures
that the time complexity remains O(√n), where n is the number
being checked."

Here is a simple implementation in Python:

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

15. Implement a function to find the

missing number in an array of
integers from 1 to n.
Why you might get asked this: Implementing a function to find
the missing number in an array of integers from 1 to n tests your
understanding of array manipulation and algorithmic efficiency,
which is crucial for technical roles such as software engineering.

How to answer:

 Explain the concept of using the sum formula for the first n natural
numbers.

 Discuss the process of subtracting the sum of the array elements

from the expected sum.

 Mention the time complexity of the solution, which is O(n).

Example answer:

"To find the missing number in an array of integers from 1 to n, you

can use the sum formula for the first n natural numbers and
subtract the sum of the array elements from the expected sum. This
approach ensures that the time complexity remains O(n), where n is
the number of elements in the array."

Here is a simple implementation in Python:

def find_missing_number(arr, n): expected_sum = n * (n +

1) // 2 actual_sum = sum(arr) return expected_sum -
actual_sum
 16. Write a program to generate all
permutations of a string.
Why you might get asked this: Generating all permutations of a
string tests your understanding of recursion and combinatorial
algorithms, which is crucial for technical roles such as software
engineering.

How to answer:

 Explain the concept of using recursion to generate permutations.

 Discuss the base case for the recursion to stop.

 Mention the time complexity of the solution, which is O(n!).

Example answer:

"To generate all permutations of a string, you can use recursion to

swap characters and backtrack to explore all possible arrangements.
This approach ensures that the time complexity remains O(n!),
where n is the length of the string."

Here is a simple implementation in Python:

def permute(s): def backtrack(start): if start == len(s)

- 1: [Link](''.join(s)) for i in
range(start, len(s)): s[start], s[i] = s[i], s[start]
backtrack(start + 1) s[start], s[i] = s[i], s[start] s =
list(s) permutations = [] backtrack(0) return
permutations

17. Create a function to find the

longest substring without repeating
characters.
 Why you might get asked this: Finding the longest substring
without repeating characters tests your ability to handle string
manipulation and understand algorithmic efficiency, which is crucial
for technical roles such as software engineering.

How to answer:

 Explain the concept of using a sliding window to keep track of the

current substring.

 Discuss the use of a set to store characters and ensure no

repetitions.

 Mention the time complexity of the solution, which is O(n).

Example answer:

"To find the longest substring without repeating characters, you can
use a sliding window to keep track of the current substring and a set
to store characters and ensure no repetitions. This approach
ensures that the time complexity remains O(n), where n is the
length of the string."

def longest_substring_without_repeating(s): char_set =

set() left = 0 max_length = 0 for right in range(len(s)):
while s[right] in char_set: char_set.remove(s[left]) left
+= 1 char_set.add(s[right]) max_length = max(max_length,
right - left + 1) return max_length

18. Implement a binary search

algorithm on a sorted array.
Why you might get asked this: Implementing a binary search
algorithm on a sorted array tests your understanding of efficient
search algorithms and their application in optimizing performance,
which is crucial for technical roles such as software engineering.

How to answer:
 Explain the concept of dividing the array into halves to locate the
target element.

 Discuss the use of pointers to keep track of the search boundaries.

 Mention the time complexity of the solution, which is O(log n).

Example answer:

"To implement a binary search algorithm on a sorted array, you can

divide the array into halves to locate the target element efficiently.
This approach ensures that the time complexity remains O(log n),
where n is the number of elements in the array."

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

19. Write a program to find the kth

largest element in an unsorted
array.
Why you might get asked this: Finding the kth largest element in
an unsorted array tests your ability to handle array manipulation
and understand algorithmic efficiency, which is crucial for technical
roles such as software engineering.

How to answer:

 Explain the concept of using a heap data structure to efficiently find

the kth largest element.

 Discuss the use of a min-heap to keep track of the k largest

elements seen so far.

 Mention the time complexity of the solution, which is O(n log k).

Example answer:
 "To find the kth largest element in an unsorted array, you can use a
min-heap to keep track of the k largest elements seen so far. This
approach ensures that the time complexity remains O(n log k),
where n is the number of elements in the array."

import heapqdef find_kth_largest(nums, k): return

[Link](k, nums)[-1]

20. Create a function to check if a

binary tree is balanced.
Why you might get asked this: Creating a function to check if a
binary tree is balanced tests your understanding of tree data
structures and algorithmic efficiency, which is crucial for technical
roles such as software engineering.

How to answer:

 Explain the concept of checking the height difference between the

left and right subtrees.

 Discuss the use of recursion to traverse the tree and calculate

heights.

 Mention the time complexity of the solution, which is O(n).

Example answer:

"To check if a binary tree is balanced, you can use recursion to

calculate the height of each subtree and ensure the height
difference is no more than one. This approach ensures that the time
complexity remains O(n), where n is the number of nodes in the
tree."

def is_balanced(root): def height(node): if not node:

return 0 left_height = height([Link]) right_height =
height([Link]) if left_height == -1 or right_height
== -1 or abs(left_height - right_height) > 1: return -1
 return max(left_height, right_height) + 1 return
height(root) != -1

21. Implement a depth-first search

(DFS) algorithm for a graph.
Why you might get asked this: Implementing a depth-first
search (DFS) algorithm for a graph tests your understanding of
graph traversal techniques and their applications, which is crucial
for technical roles such as software engineering.

How to answer:

 Explain the concept of using a stack or recursion to traverse the

graph.

 Discuss the importance of marking nodes as visited to avoid cycles.

 Mention the time complexity of the solution, which is O(V + E).

Example answer:

"To implement a depth-first search (DFS) algorithm for a graph, you

can use a stack or recursion to traverse the graph. This approach
ensures that the time complexity remains O(V + E), where V is the
number of vertices and E is the number of edges."

def dfs(graph, start): visited = set() stack = [start]

while stack: vertex = [Link]() if vertex not in
visited: [Link](vertex)
[Link](set(graph[vertex]) - visited) return visited

22. Write a program to find the

shortest path in a weighted graph
using Dijkstra's algorithm.
 Why you might get asked this: Finding the shortest path in a
weighted graph using Dijkstra's algorithm tests your understanding
of graph algorithms and their applications in optimizing network
routing, which is crucial for technical roles such as software
engineering.

How to answer:

 Explain the concept of using a priority queue to select the next node
with the smallest tentative distance.

 Discuss the process of updating the distances to neighboring nodes

based on the current node's distance.

 Mention the time complexity of the solution, which is O(V log V + E

log V).

Example answer:

"To find the shortest path in a weighted graph using Dijkstra's

algorithm, you can use a priority queue to select the next node with
the smallest tentative distance. This approach ensures that the time
complexity remains O(V log V + E log V), where V is the number of
vertices and E is the number of edges."

import heapqdef dijkstra(graph, start): pq = [(0, start)]

distances = {vertex: float('infinity') for vertex in
graph} distances[start] = 0 while pq: current_distance,
current_vertex = [Link](pq) if current_distance >
distances[current_vertex]: continue for neighbor, weight
in graph[current_vertex].items(): distance =
current_distance + weight if distance <
distances[neighbor]: distances[neighbor] = distance
[Link](pq, (distance, neighbor)) return distances

23. Create a function to solve the N-

Queens problem.
 Why you might get asked this: Creating a function to solve the
N-Queens problem tests your ability to handle complex algorithmic
challenges and recursion, which is crucial for technical roles such as
software engineering.

How to answer:

 Explain the concept of using backtracking to place queens on the

board.

 Discuss the importance of checking for conflicts in rows, columns,

and diagonals.

 Mention the time complexity of the solution, which is O(n!).

Example answer:

"To solve the N-Queens problem, you can use backtracking to place
queens on the board while ensuring no two queens threaten each
other. This approach ensures that the time complexity remains
O(n!), where n is the number of queens."

def solve_n_queens(n): def is_safe(board, row, col): for

i in range(col): if board[row][i] == 1: return False for
i, j in zip(range(row, -1, -1), range(col, -1, -1)): if
board[i][j] == 1: return False for i, j in zip(range(row,
n, 1), range(col, -1, -1)): if board[i][j] == 1: return
False return True def solve(board, col): if col >= n:
return True for i in range(n): if is_safe(board, i, col):
board[i][col] = 1 if solve(board, col + 1): return True
board[i][col] = 0 return False board = [[0] * n for _ in
range(n)] if not solve(board, 0): return [] return board

24. Implement a function to detect a

cycle in a linked list.
Why you might get asked this: Detecting a cycle in a linked list
tests your understanding of linked list data structures and
 algorithmic efficiency, which is crucial for technical roles such as
software engineering.

How to answer:

 Explain the concept of using two pointers, one moving twice as fast
as the other.

 Discuss the process of detecting a cycle when the two pointers

meet.

 Mention the time complexity of the solution, which is O(n).

Example answer:

"To detect a cycle in a linked list, you can use two pointers, one
moving twice as fast as the other. If the two pointers meet, a cycle
exists; otherwise, the list is acyclic."

def detect_cycle(head): slow, fast = head, head while

fast and [Link]: slow = [Link] fast =
[Link] if slow == fast: return True return False

25. Write a program to find all

subsets of a given set.
Why you might get asked this: Finding all subsets of a given set
tests your understanding of combinatorial algorithms and recursion,
which is crucial for technical roles such as software engineering.

How to answer:

 Explain the concept of using recursion to generate all possible

subsets.

 Discuss the importance of including and excluding each element in

the recursive calls.

 Mention the time complexity of the solution, which is O(2^n).

Example answer:

"To find all subsets of a given set, you can use recursion to generate
all possible subsets by including and excluding each element in the
recursive calls. This approach ensures that the time complexity
remains O(2^n), where n is the number of elements in the set."

def find_subsets(nums): def backtrack(start, path):

[Link](path) for i in range(start, len(nums)):
backtrack(i + 1, path + [nums[i]]) subsets = []
backtrack(0, []) return subsets