In this post, we have discussed the most common interview problems and their solutions using Python. These problems include array manipulation, string manipulation, linked list manipulation, sorting and searching, dynamic programming, and more. We have provided solutions in Python for each problem to help you prepare for your interviews effectively.
1. Reverse a String
Write a Python function to reverse a given string.
def reverse_string(s):
return s[::-1]
2. Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
def two_sum(nums, target):
d = {}
for i, num in enumerate(nums):
complement = target - num
if complement in d:
return [d[complement], i]
d[num] = i
return None
3. Palindrome
Check if a given string is a palindrome, ignoring non-alphanumeric characters and considering case.
def is_palindrome(s):
s = ''.join(c for c in s if c.isalnum()).lower()
return s == s[::-1]4. Longest Common Prefix
Find the longest common prefix of an array of strings.
def longest_common_prefix(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
while not s.startswith(prefix):
prefix = prefix[:-1]
return prefix
5. Merge Intervals
Given a list of intervals, merge overlapping intervals.
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or interval[0] > merged[-1][1]:
merged.append(interval)
else:
merged[-1] = (merged[-1][0], max(merged[-1][1], interval[1]))
return merged
6. Binary Search
Implement binary search in a sorted 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
7. Maximal Subarray Sum
Find the contiguous subarray with the largest sum in an array of integers.
def max_subarray_sum(nums):
max_sum = float('-inf')
current_sum = 0
for num in nums:
current_sum += num
max_sum = max(max_sum, current_sum)
current_sum = max(0, current_sum)
return max_sum
8. Matrix Rotation
Rotate an N x N matrix (in-place) by 90 degrees clockwise
def rotate_matrix(matrix):
n = len(matrix)
for i in range(n // 2):
for j in range(i, n - i - 1):
temp = matrix[i][j]
matrix[i][j] = matrix[n - j - 1][i]
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
matrix[j][n - i - 1] = temp
return matrix
9. LRU Cache
Implement a Least Recently Used (LRU) cache with constant time complexity for get and put operations.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key, value):
if key in self.cache:
self.cache.pop(key)
elif len(self.cache) == self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
10. Valid Parentheses
Given a string containing only characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
def is_valid_parentheses(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
11. Maximum Depth of Binary Tree
Find the maximum depth of a binary tree.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_depth(root):
if not root:
return 0
return max(max_depth(root.left), max_depth(root.right)) + 1
12. Climbing Stairs
Given a staircase with n steps, find the number of distinct ways to climb to the top, where you can climb 1 or 2 steps at a time.
def climb_stairs(n):
if n == 1:
return 1
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
13. Merge Two Sorted Lists
Merge two sorted linked lists into a new sorted linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_two_lists(l1, l2):
dummy = ListNode()
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
if l1:
current.next = l1
if l2:
current.next = l2
return dummy.next
14 Valid Sudoku
Determine if a 9×9 Sudoku board is valid.
def isValidSudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for i in range(9):
for j in range(9):
val = board[i][j]
if val == ".":
continue
if val in rows[i] or val in cols[j] or val in boxes[(i // 3) * 3 + j // 3]:
return False
rows[i].add(val)
cols[j].add(val)
boxes[(i // 3) * 3 + j // 3].add(val)
return True
rows, cols, and boxes are three sets of sets, each representing the numbers seen in each row, column, and 3×3 box of the Sudoku board, respectively. These sets will be used to keep track of the numbers seen in each row, column, and box as we iterate through the board.
The function iterates through each cell in the Sudoku board using two nested loops, with i representing the row index and j representing the column index.
For each cell, the function checks if the value (val) is an empty cell, represented by a period (.). If it is, the function skips to the next iteration of the loop, as empty cells do not affect the validity of the Sudoku board.
If the cell is not empty, the function checks if the value val is already present in the corresponding row, column, and box. It does this by checking if val is present in the sets rows[i], cols[j], and boxes[(i // 3) * 3 + j // 3], which represent the numbers seen in the current row, column, and box, respectively.
If val is already present in any of the sets, it means that the number is repeated in the same row, column, or box, which violates the rules of Sudoku. In this case, the function immediately returns False, indicating that the Sudoku board is invalid.
If val is not present in any of the sets, the function adds it to the sets rows[i], cols[j], and boxes[(i // 3) * 3 + j // 3] to keep track of the numbers seen so far.
After iterating through all the cells in the board, if no repeated numbers are found, the function returns True, indicating that the Sudoku board is valid, as per the rules of Sudoku.
15 Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
def length_of_longest_substring(s):
char_map = {}
start = 0
max_len = 0
for i, char in enumerate(s):
if char in char_map and char_map[char] >= start:
start = char_map[char] + 1
char_map[char] = i
max_len = max(max_len, i - start + 1)
return max_len
16. Product of Array Except Self
Given an array of integers, return an array where the output at each index is the product of all elements in the array except the element at that index.
BECOME APACHE KAFKA GURU – ZERO TO HERO IN MINUTES
ENROLL TODAY & GET 90% OFF
def product_except_self(nums):
n = len(nums)
output = [1] * n
left_product = 1
right_product = 1
for i in range(n):
output[i] *= left_product
left_product *= nums[i]
for i in range(n - 1, -1, -1):
output[i] *= right_product
right_product *= nums[i]
return output
17. Container With Most Water
Given an array of non-negative integers representing the heights of bars in a bar chart, find the area of the largest rectangle that can be formed by any two bars.
def max_area(heights):
max_area = 0
left = 0
right = len(heights) - 1
while left < right:
h = min(heights[left], heights[right])
w = right - left
area = h * w
max_area = max(max_area, area)
if heights[left] < heights[right]:
left += 1
else:
right -= 1
return max_area
18. Rotate Image
Given an n x n matrix representing an image, rotate the image by 90 degrees (clockwise) in place.
def rotate(matrix):
n = len(matrix)
for i in range(n // 2):
for j in range(i, n - i - 1):
temp = matrix[i][j]
matrix[i][j] = matrix[n - j - 1][i]
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
matrix[j][n - i - 1] = temp
These are just a few examples of common interview problems and their solutions using Python. It’s important to practice solving different types of problems to improve your problem-solving skills and prepare for interviews.
Remember to understand the problem thoroughly, come up with an efficient solution, and test your code with various inputs to ensure its correctness. Good luck with your interview preparation!