Top 20 Coding Interview Questions: Ace Your Technical Interview
Are you preparing for a coding interview at a top tech company? Whether you’re aiming for a position at a FAANG company (Facebook, Amazon, Apple, Netflix, Google) or any other tech giant, it’s crucial to be well-prepared for the technical interview. In this comprehensive guide, we’ll explore the 20 most common coding interview questions, provide insights on how to approach them, and offer tips to help you succeed in your next interview.
Why Coding Interviews Matter
Coding interviews are a critical part of the hiring process for software engineering positions. They allow companies to assess a candidate’s problem-solving skills, coding ability, and algorithmic thinking. By understanding and practicing these common questions, you’ll be better equipped to showcase your skills and land your dream job.
The 20 Most Common Coding Interview Questions
Let’s dive into the top 20 coding interview questions you’re likely to encounter:
1. Two Sum
Given an array of integers and a target sum, return the indices of two numbers in the array that add up to the target.
def two_sum(nums, target):
num_dict = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_dict:
return [num_dict[complement], i]
num_dict[num] = i
return []
# Example usage
print(two_sum([2, 7, 11, 15], 9)) # Output: [0, 1]
2. Reverse a Linked List
Given the head of a singly linked list, reverse the list and return the new head.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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
# Example usage
# Create a linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
# Reverse the linked list
new_head = reverse_linked_list(head)
# Print the reversed list
current = new_head
while current:
print(current.val, end=" ")
current = current.next
# Output: 5 4 3 2 1
3. Valid Parentheses
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
def is_valid_parentheses(s):
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
# Example usage
print(is_valid_parentheses("()[]{}")) # Output: True
print(is_valid_parentheses("([)]")) # Output: False
4. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new sorted list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_two_lists(l1, l2):
dummy = ListNode(0)
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
current.next = l1 if l1 else l2
return dummy.next
# Example usage
# Create two sorted linked lists
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)
# Merge the lists
merged = merge_two_lists(l1, l2)
# Print the merged list
current = merged
while current:
print(current.val, end=" ")
current = current.next
# Output: 1 1 2 3 4 4
5. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
def max_subarray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
# Example usage
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # Output: 6
6. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level)
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def level_order_traversal(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
# Example usage
# Create a binary tree
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(level_order_traversal(root))
# Output: [[3], [9, 20], [15, 7]]
7. Implement a Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
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
# Example usage
trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # Output: True
print(trie.search("app")) # Output: False
print(trie.starts_with("app")) # Output: True
trie.insert("app")
print(trie.search("app")) # Output: True
8. Implement a Queue using Stacks
Implement a first in first out (FIFO) queue using only two stacks.
class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, x):
self.stack1.append(x)
def pop(self):
self.peek()
return self.stack2.pop()
def peek(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def empty(self):
return not self.stack1 and not self.stack2
# Example usage
queue = MyQueue()
queue.push(1)
queue.push(2)
print(queue.peek()) # Output: 1
print(queue.pop()) # Output: 1
print(queue.empty()) # Output: False
9. Find the Kth Largest Element in an Array
Given an unsorted array, find the kth largest element in it.
import heapq
def find_kth_largest(nums, k):
return heapq.nlargest(k, nums)[-1]
# Example usage
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2)) # Output: 5
print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) # Output: 4
10. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s.
def longest_palindrome(s):
if not s:
return ""
start = 0
max_length = 1
for i in range(len(s)):
# Check for odd-length palindromes
left, right = i, i
while left >= 0 and right < len(s) and s[left] == s[right]:
if right - left + 1 > max_length:
start = left
max_length = right - left + 1
left -= 1
right += 1
# Check for even-length palindromes
left, right = i, i + 1
while left >= 0 and right < len(s) and s[left] == s[right]:
if right - left + 1 > max_length:
start = left
max_length = right - left + 1
left -= 1
right += 1
return s[start:start + max_length]
# Example usage
print(longest_palindrome("babad")) # Output: "bab" or "aba"
print(longest_palindrome("cbbd")) # Output: "bb"
11. Implement a LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
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
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
# Example usage
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # Output: 1
cache.put(3, 3)
print(cache.get(2)) # Output: -1
cache.put(4, 4)
print(cache.get(1)) # Output: -1
print(cache.get(3)) # Output: 3
print(cache.get(4)) # Output: 4
12. Implement a Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]
# Example usage
min_stack = MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
print(min_stack.get_min()) # Output: -3
min_stack.pop()
print(min_stack.top()) # Output: 0
print(min_stack.get_min()) # Output: -2
13. Rotate Image
You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).
def rotate_image(matrix):
n = len(matrix)
# Transpose the matrix
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()
# Example usage
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
rotate_image(matrix)
print(matrix)
# Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
14. Serialize and Deserialize Binary Tree
Design an algorithm to serialize and deserialize a binary tree.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Codec:
def serialize(self, root):
if not root:
return "null"
return f"{root.val},{self.serialize(root.left)},{self.serialize(root.right)}"
def deserialize(self, data):
def dfs():
val = next(values)
if val == "null":
return None
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
return node
values = iter(data.split(","))
return dfs()
# Example usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)
codec = Codec()
serialized = codec.serialize(root)
print(serialized) # Output: 1,2,null,null,3,4,null,null,5,null,null
deserialized = codec.deserialize(serialized)
print(codec.serialize(deserialized)) # Output: 1,2,null,null,3,4,null,null,5,null,null
15. Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
def word_break(s, word_dict):
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_dict:
dp[i] = True
break
return dp[n]
# Example usage
print(word_break("leetcode", ["leet", "code"])) # Output: True
print(word_break("applepenapple", ["apple", "pen"])) # Output: True
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"])) # Output: False
16. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
# Example usage
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]])) # Output: [[1,6],[8,10],[15,18]]
print(merge_intervals([[1,4],[4,5]])) # Output: [[1,5]]
17. Implement strStr()
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
def str_str(haystack, needle):
if not needle:
return 0
for i in range(len(haystack) - len(needle) + 1):
if haystack[i:i+len(needle)] == needle:
return i
return -1
# Example usage
print(str_str("hello", "ll")) # Output: 2
print(str_str("aaaaa", "bba")) # Output: -1
18. 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_index = {}
max_length = 0
start = 0
for i, char in enumerate(s):
if char in char_index and char_index[char] >= start:
start = char_index[char] + 1
else:
max_length = max(max_length, i - start + 1)
char_index[char] = i
return max_length
# Example usage
print(length_of_longest_substring("abcabcbb")) # Output: 3
print(length_of_longest_substring("bbbbb")) # Output: 1
print(length_of_longest_substring("pwwkew")) # Output: 3
19. Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
from collections import Counter
def min_window(s, t):
if not t or not s:
return ""
dict_t = Counter(t)
required = len(dict_t)
left = 0
right = 0
formed = 0
window_counts = {}
ans = float("inf"), None, None
while right < len(s):
character = s[right]
window_counts[character] = window_counts.get(character, 0) + 1
if character in dict_t and window_counts[character] == dict_t[character]:
formed += 1
while left <= right and formed == required:
character = s[left]
if right - left + 1 < ans[0]:
ans = (right - left + 1, left, right)
window_counts[character] -= 1
if character in dict_t and window_counts[character] < dict_t[character]:
formed -= 1
left += 1
right += 1
return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]
# Example usage
print(min_window("ADOBECODEBANC", "ABC")) # Output: "BANC"
print(min_window("a", "a")) # Output: "a"
20. Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
def find_median_sorted_arrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
left, right = 0, m
while left <= right:
partition_x = (left + right) // 2
partition_y = (m + n + 1) // 2 - partition_x
max_left_x = float('-inf') if partition_x == 0 else nums1[partition_x - 1]
min_right_x = float('inf') if partition_x == m else nums1[partition_x]
max_left_y = float('-inf') if partition_y == 0 else nums2[partition_y - 1]
min_right_y = float('inf') if partition_y == n else nums2[partition_y]
if max_left_x <= min_right_y and max_left_y <= min_right_x:
if (m + n) % 2 == 0:
return (max(max_left_x, max_left_y) + min(min_right_x, min_right_y)) / 2
else:
return max(max_left_x, max_left_y)
elif max_left_x > min_right_y:
right = partition_x - 1
else:
left = partition_x + 1
# Example usage
print(find_median_sorted_arrays([1, 3], [2])) # Output: 2.0
print(find_median_sorted_arrays([1, 2], [3, 4])) # Output: 2.5
Tips for Succeeding in Coding Interviews
Now that we’ve covered the most common coding interview questions, here are some tips to help you succeed in your next technical interview:
- Practice regularly: Solve coding problems on platforms like LeetCode, HackerRank, or CodeSignal to improve your problem-solving skills.
- Understand the fundamentals: Make sure you have a solid grasp of data structures, algorithms, and time/space complexity analysis.
- Communicate your thought process: Explain your approach and reasoning while solving problems during the interview.
- Ask clarifying questions: Ensure you fully understand the problem before diving into the solution.
- Consider edge cases: Think about potential edge cases and handle them in your solution.
- Optimize your solution: After implementing a working solution, consider ways to optimize it for better time or space complexity.
- Test your code: Write test cases and walk through your code to catch any bugs or errors.
- Learn from your mistakes: Review and understand the solutions to problems you couldn’t solve, and try to implement them on your own later.
- Stay calm and focused: Remember that interviewers are interested in your problem-solving process, not just the final answer.
- Practice mock interviews: Conduct mock interviews with friends or use online platforms to simulate real interview conditions.
Conclusion
Mastering these common coding interview questions and following the tips provided will significantly improve your chances of success in technical interviews. Remember that consistent practice and a solid understanding of fundamental concepts are key to performing well in coding interviews.
As you prepare for your interviews, consider using resources like AlgoCademy to enhance your coding skills and gain confidence in tackling complex problems. With dedication and the right approach, you’ll be well-equipped to ace your next coding interview and land your dream job in the tech industry.
