Programming interviews are a crucial part of the hiring process in the tech industry. They assess your problem-solving skills, coding proficiency, and understanding of data structures and algorithms. This blog post compiles some of the most frequently asked programming interview questions across various topics such as Arrays, Linked Lists, Strings, Binary Trees, Graphs, and Dynamic Programming.
Table of Contents
Arrays
How is an array sorted using Quicksort?
Answer: Quicksort is a divide-and-conquer algorithm that selects a ‘pivot’ element and partitions the array around the pivot, so that elements less than the pivot are on the left, and those greater are on the right. The process is then recursively applied to the sub-arrays.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
How do you reverse an array?
Answer: Reversing an array involves swapping the elements from the start with the elements from the end, moving towards the center.
def reverse_array(arr):
start, end = 0, len(arr) - 1
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
return arr
How do you remove duplicates from an array?
Answer: Duplicates can be removed by converting the array into a set, which inherently removes duplicates, and then converting it back to a list.
def remove_duplicates(arr):
return list(set(arr))
How do you find the 2nd largest number in an unsorted integer array?
Answer: You can find the 2nd largest number by first finding the maximum, then removing all occurrences of it, and finally finding the new maximum.
def second_largest(arr):
first = second = float('-inf')
for num in arr:
if num > first:
second = first
first = num
elif first > num > second:
second = num
return second
Answer: Traverse the linked list from the head to the end, counting the nodes.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def length_of_linked_list(head):
count = 0
current = head
while current:
count += 1
current = current.next
return count
How do you reverse a linked list?
Answer: Reverse a linked list by iterating through it and reversing the pointers.
def reverse_linked_list(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
How do you find the third node from the end?
Answer: Use two pointers, with one starting three nodes ahead. When the first pointer reaches the end, the second pointer will be at the third node from the end.
def third_from_end(head):
first = head
second = head
for _ in range(3):
if first is None:
return None
first = first.next
while first:
first = first.next
second = second.next
return second
How are duplicate nodes removed in an unsorted linked list?
Answer: Use a hash set to keep track of seen values as you iterate through the list, removing duplicates as you go.
def remove_duplicates(head):
if not head:
return None
seen = set()
current = head
seen.add(current.data)
while current.next:
if current.next.data in seen:
current.next = current.next.next
else:
seen.add(current.next.data)
current = current.next
return head
How do you check if a string contains only digits?
Answer: Use the isdigit() method to check if all characters in the string are digits.
def is_digit_only(s):
return s.isdigit()
How can a given string be reversed?
Answer: Reverse the string by slicing it.
def reverse_string(s):
return s[::-1]
How do you find the first non-repeated character?
Answer: Use a dictionary to count the frequency of each character, then return the first character with a count of 1.
def first_non_repeated(s):
count = {}
for char in s:
count[char] = count.get(char, 0) + 1
for char in s:
if count[char] == 1:
return char
return None
How do you find duplicate characters in strings?
Answer: Use a dictionary to count characters and return those with a count greater than 1.
def find_duplicates(s):
count = {}
duplicates = []
for char in s:
count[char] = count.get(char, 0) + 1
for char, c in count.items():
if c > 1:
duplicates.append(char)
return duplicates
Answer: Use a recursive function to traverse the tree and print nodes with no children.
class TreeNode:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def print_leaves(root):
if root:
if not root.left and not root.right:
print(root.value)
print_leaves(root.left)
print_leaves(root.right)
How do you check if a tree is a binary search tree?
Answer: Use a recursive function to ensure each node follows the binary search tree properties.
def is_bst(node, left=float('-inf'), right=float('inf')):
if not node:
return True
if not (left < node.value < right):
return False
return (is_bst(node.left, left, node.value) and
is_bst(node.right, node.value, right))
How is a binary search tree implemented?
Answer: Implement a binary search tree with insert, search, and delete operations.
class BSTNode:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def insert(self, value):
if value < self.value:
if self.left:
self.left.insert(value)
else:
self.left = BSTNode(value)
else:
if self.right:
self.right.insert(value)
else:
self.right = BSTNode(value)
def search(self, value):
if value < self.value:
return self.left.search(value) if self.left else False
elif value > self.value:
return self.right.search(value) if self.right else False
return True
Answer: Use recursion to find the lowest common ancestor by checking the position of the nodes in relation to the root.
def lowest_common_ancestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left if left else right
Find the total number of strongly connected components?
Answer: Use Kosaraju’s algorithm or Tarjan’s algorithm to find strongly connected components.
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs(self, v, visited):
visited[v] = True
for neighbor in self.graph[v]:
if not visited[neighbor]:
self.dfs(neighbor, visited)
def fill_order(self, v, visited, stack):
visited[v] = True
for neighbor in self.graph[v]:
if not visited[neighbor]:
self.fill_order(neighbor, visited, stack)
stack.append(v)
def get_transpose(self):
g = Graph(self.V)
for i in self.graph:
for j in self.graph[i]:
g.add_edge(j, i)
return g
def find_sccs(self):
stack = []
visited = [False] * self.V
for i in range(self.V):
if not visited[i]:
self.fill_order(i, visited, stack)
gr = self.get_transpose()
visited = [False] * self.V
scc_count = 0
while stack:
i = stack.pop()
if not visited[i]:
gr.dfs(i, visited)
scc_count += 1
return scc_count
Find whether a path exists between two nodes of a graph?
Answer: Use depth-first search (DFS) or breadth-first search (BFS) to determine if a path exists between two nodes.
def dfs_path_exists(graph, start, end, visited):
visited[start] = True
if start == end:
return True
for neighbor in graph[start]:
if not visited[neighbor]:
if dfs_path_exists(graph, neighbor, end, visited):
return True
return False
def path_exists(graph, start, end):
visited = [False] * len(graph)
return dfs_path_exists(graph, start, end, visited)
Find the minimum number of swaps required to sort an array.
Answer: Use cycle detection in graphs where the array elements represent the vertices, and edges are defined by element positions.
def min_swaps(arr):
n = len(arr)
arr_pos = [*enumerate(arr)]
arr_pos.sort(key=lambda it: it[1])
visited = {k: False for k in range(n)}
swaps = 0
for i in range(n):
if visited[i] or arr_pos[i][0] == i:
continue
cycle_size = 0
j = i
while not visited[j]:
visited[j] = True
j = arr_pos[j][0]
cycle_size += 1
if cycle_size > 0:
swaps += (cycle_size - 1)
return swaps
Answer: Use dynamic programming to build a table that compares the substrings of the two sequences.
def lcs(X, Y):
m = len(X)
n = len(Y)
L = [[None] * (n + 1) for i in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i - 1] == Y[j - 1]:
L[i][j] = L[i - 1][j - 1] + 1
else:
L[i][j] = max(L[i - 1][j], L[i][j - 1])
return L[m][n]
Find the longest common substring?
Answer: Use dynamic programming to build a table and track the longest substring.
def longest_common_substring(X, Y):
m = len(X)
n = len(Y)
result = 0
length = [[0] * (n + 1) for i in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
length[i][j] = 0
elif X[i - 1] == Y[j - 1]:
length[i][j] = length[i - 1][j - 1] + 1
result = max(result, length[i][j])
else:
length[i][j] = 0
return result
Coin change problem?
Answer: Use dynamic programming to find the minimum number of coins needed to make up a given amount.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Most Asked Programming Interview Questions
Box stacking problem?
Answer: Use dynamic programming to find the maximum height of stackable boxes.
class Box:
def __init__(self, h, w, d):
self.h = h
self.w = w
self.d = d
def max_stack_height(boxes):
n = len(boxes)
all_rotations = []
for box in boxes:
all_rotations.append(Box(box.h, max(box.w, box.d), min(box.w, box.d)))
all_rotations.append(Box(box.w, max(box.h, box.d), min(box.h, box.d)))
all_rotations.append(Box(box.d, max(box.h, box.w), min(box.h, box.w)))
all_rotations.sort(key=lambda box: box.w * box.d, reverse=True)
max_height = [0] * len(all_rotations)
for i in range(len(all_rotations)):
max_height[i] = all_rotations[i].h
for i in range(1, len(all_rotations)):
for j in range(0, i):
if (all_rotations[i].w < all_rotations[j].w and
all_rotations[i].d < all_rotations[j].d):
max_height[i] = max(max_height[i], max_height[j] + all_rotations[i].h)
return max(max_height)
Count the number of ways to cover a distance?
Answer: Use dynamic programming to count the number of ways to cover a given distance with 1, 2, or 3 steps.
def count_ways(n):
res = [0] * (n + 1)
res[0] = 1
res[1] = 1
res[2] = 2
for i in range(3, n + 1):
res[i] = res[i - 1] + res[i - 2] + res[i - 3]
return res[n]
2 comments