So here is a List of 20+ Coding which can be asked in a Coding Interview.
Q: Write a function to reverse a string.
A: Sure! Here’s a Python code snippet that reverses a string:
def reverse_string(input_str):
return input_str[::-1]Q: Implement a stack using an array or a linked list.
A: To implement a stack using an array in Python, you can use a list. Here’s a simple implementation:
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
def is_empty(self):
return len(self.stack) == 0
def peek(self):
if not self.is_empty():
return self.stack[-1]
Q: Find the maximum element in a stack with O(1) time complexity.
A: In order to find the maximum element in a stack with O(1) time complexity, you can use an additional stack to keep track of the current maximum at each step. Here’s a Python implementation:
class MaxStack:
def __init__(self):
self.stack = []
self.max_stack = []
def push(self, item):
self.stack.append(item)
if not self.max_stack or item >= self.max_stack[-1]:
self.max_stack.append(item)
def pop(self):
if not self.is_empty():
popped = self.stack.pop()
if popped == self.max_stack[-1]:
self.max_stack.pop()
return popped
def is_empty(self):
return len(self.stack) == 0
def get_max(self):
if not self.is_empty():
return self.max_stack[-1]
Q: Given an array of integers, find the two elements that sum up to a specific target.
A: Here’s a Python function that finds two elements in an array that sum up to a target value:
def find_two_sum(arr, target):
num_map = {}
for num in arr:
complement = target - num
if complement in num_map:
return [complement, num]
num_map[num] = True
return None
Q: Determine if a string is a palindrome.
A: Here’s a Python function to check if a string is a palindrome:
def is_palindrome(input_str):
return input_str == input_str[::-1]
Q: Implement a binary search algorithm. A: Here’s a Python implementation of the binary search algorithm:
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1Q: Implement a bubble sort algorithm.
A: Here’s a Python implementation of the bubble sort algorithm:
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]
Q: Given a binary tree, write a function to check if it is a binary search tree.
A: Here’s a Python code snippet to check if a binary tree is a binary search tree:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def is_bst(root):
def is_bst_util(node, min_val, max_val):
if node is None:
return True
if node.value <= min_val or node.value >= max_val:
return False
return (is_bst_util(node.left, min_val, node.value) and
is_bst_util(node.right, node.value, max_val))
return is_bst_util(root, float('-inf'), float('inf'))
Q: Find the intersection of two sorted arrays.
A: Here’s a Python function to find the intersection of two sorted arrays:
def find_intersection(arr1, arr2):
intersection = []
i = 0
j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] == arr2[j]:
intersection.append(arr1[i])
i += 1
j += 1
elif arr1[i] < arr2[j]:
i += 1
else:
j += 1
return intersection
Q: Implement a queue using two stacks.
A: Here’s a Python implementation of a queue using two stacks:
class Queue:
def __init__(self):
self.enqueue_stack = []
self.dequeue_stack = []
def enqueue(self, item):
self.enqueue_stack.append(item)
def dequeue(self):
if not self.dequeue_stack:
while self.enqueue_stack:
self.dequeue_stack.append(self.enqueue_stack.pop())
return self.dequeue_stack.pop()
Q: Implement a depth-first search (DFS) algorithm for a graph.
A: Here’s a Python implementation of the depth-first search (DFS) algorithm for a graph:
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v):
if u in self.graph:
self.graph[u].append(v)
else:
self.graph[u] = [v]
def dfs(self, start):
visited = set()
self.dfs_util(start, visited)
def dfs_util(self, node, visited):
visited.add(node)
print(node, end=' ')
if node in self.graph:
for neighbor in self.graph[node]:
if neighbor not in visited:
self.dfs_util(neighbor, visited)
Q: Implement a breadth-first search (BFS) algorithm for a graph.
A: Here’s a Python implementation of the breadth-first search (BFS) algorithm for a graph:
from collections import deque
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v):
if u in self.graph:
self.graph[u].append(v)
else:
self.graph[u] = [v]
def bfs(self, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=' ')
if node in self.graph:
for neighbor in self.graph[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
Q: Given a linked list, find the middle element in a single pass.
A: Here’s a Python function to find the middle element of a linked list in a single pass:
class Node:
def __init__(self, value):
self.value = value
self.next = None
def find_middle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.value
Q: Write a function to check if a string contains valid parentheses.
A: Here’s a Python function to check if a string contains valid parentheses:
def is_valid_parentheses(input_str):
stack = []
parentheses_map = {')': '(', '}': '{', ']': '['}
for char in input_str:
if char in parentheses_map.values():
stack.append(char)
elif char in parentheses_map.keys():
if not stack or parentheses_map[char] != stack.pop():
return False
return len(stack) == 0Q: Reverse a linked list.
A: Here’s a Python function to reverse a linked list:
class Node:
def __init__(self, value):
self.value = value
self.next = None
def reverse_linked_list(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
Q: Find the factorial of a number using recursion.
A: Here’s a Python function to find the factorial of a number using recursion:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)Q: Implement a merge sort algorithm.
A: Here’s a Python implementation of the merge sort algorithm:
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
return merge(left_half, right_half)
def merge(left, right):
merged = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
while i < len(left):
merged.append(left[i])
i += 1
while j < len(right):
merged.append(right[j])
j += 1
return merged
Q: Given a string, find the first non-repeating character.
A: Here’s a Python function to find the first non-repeating character in a string:
from collections import Counter
def first_non_repeating_char(input_str):
char_counts = Counter(input_str)
for char in input_str:
if char_counts[char] == 1:
return char
return NoneQ: Determine if a given string is an anagram of another string.
A: Here’s a Python function to check if a string is an anagram of another string:
def is_anagram(str1, str2):
return sorted(str1) == sorted(str2)Q: Given a binary tree, write a function to find the maximum depth of the tree.
A: Here’s a Python function to find the maximum depth of a binary tree:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def max_depth(root):
if root is None:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return max(left_depth, right_depth) + 1
Q: Implement a priority queue.
A: Here’s a Python implementation of a priority queue using the heapq module:
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
self.index = 0
def is_empty(self):
return len(self.heap) == 0
def push(self, item, priority):
heapq.heappush(self.heap, (priority, self.index, item))
self.index += 1
def pop(self):
if not self.is_empty():
return heapq.heappop(self.heap)[-1]
Q: Given a matrix, rotate it 90 degrees clockwise.
A: Here’s a Python function to rotate a matrix 90 degrees clockwise:
def rotate_matrix(matrix):
n = len(matrix)
m = len(matrix[0])
rotated = [[0] * n for _ in range(m)]
for i in range(n):
for j in range(m):
rotated[j][n-1-i] = matrix[i][j]
return rotated
Q: Implement a depth-first search (DFS) algorithm for a maze.
A: Here’s a Python implementation of the depth-first search (DFS) algorithm for solving a maze:
def dfs(maze, start, end):
rows = len(maze)
cols = len(maze[0])
visited = [[False] * cols for _ in range(rows)]
def dfs_util(row, col):
if row < 0 or row >= rows or col < 0 or col >= cols:
return False
if maze[row][col] == 1 or visited[row][col]:
return False
visited[row][col] = True
if (row, col) == end:
return True
if dfs_util(row + 1, col):
return True
if dfs_util(row - 1, col):
return True
if dfs_util(row, col + 1):
return True
if dfs_util(row, col - 1):
return True
return False
return dfs_util(start[0], start[1])
Q: Determine if a linked list contains a cycle.
A: Here’s a Python function to determine if a linked list contains a cycle:
class Node:
def __init__(self, value):
self.value = value
self.next = None
def has_cycle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Q: Implement a Trie data structure.
A: Here’s a Python implementation of a Trie data structure:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
Q: Given a string, find the longest substring without repeating characters.
A: Here’s a Python function to find the longest substring without repeating characters:
def longest_substring_without_repeating_chars(input_str):
max_length = 0
start = 0
char_map = {}
for i in range(len(input_str)):
if input_str[i] in char_map and start <= char_map[input_str[i]]:
start = char_map[input_str[i]] + 1
else:
max_length = max(max_length, i - start + 1)
char_map[input_str[i]] = i
return max_length