Are you preparing for a coding interview? Whether you’re a fresh graduate or an experienced developer looking to switch jobs, mastering common coding interview questions is crucial. In this comprehensive guide, we’ll walk you through the top 10 coding interview questions frequently asked by major tech companies, including the FAANG (Facebook, Amazon, Apple, Netflix, Google) giants. We’ll not only present the problems but also provide detailed solutions and explanations to help you ace your next technical interview.
1. Two Sum
The “Two Sum” problem is a classic algorithmic question that tests your ability to work with arrays and hash tables efficiently.
Problem Statement:
Given an array of integers nums and an integer target, return indices of the two numbers in the array such that they add up to the target. You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].Solution:
While a brute force approach using nested loops would work, it’s not efficient for large inputs. Instead, we can use a hash table to solve this problem in O(n) time complexity:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> numMap;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (numMap.find(complement) != numMap.end()) {
return {numMap[complement], i};
}
numMap[nums[i]] = i;
}
return {}; // No solution found
}
};This solution uses a hash map to store each number and its index. As we iterate through the array, we check if the complement (target – current number) exists in the hash map. If it does, we’ve found our pair and return their indices. If not, we add the current number and its index to the hash map.
2. Reverse a Linked List
Reversing a linked list is a fundamental problem that tests your understanding of pointer manipulation and linked list operations.
Problem Statement:
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]Solution:
We can solve this problem iteratively by using three pointers: previous, current, and next.
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
};This solution works by iteratively changing the next pointer of each node to point to its previous node. We use a temporary variable nextTemp to store the next node before we change the current node’s next pointer.
3. Valid Parentheses
The “Valid Parentheses” problem tests your ability to work with stacks and handle string manipulation.
Problem Statement:
Given a string s 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.
- Every close bracket has a corresponding open bracket of the same type.
Example:
Input: s = "()[]{}"
Output: true
Input: s = "([)]"
Output: falseSolution:
We can use a stack to keep track of opening brackets and check if they match with closing brackets:
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else {
if (st.empty()) return false;
if (c == ')' && st.top() != '(') return false;
if (c == '}' && st.top() != '{') return false;
if (c == ']' && st.top() != '[') return false;
st.pop();
}
}
return st.empty();
}
};This solution pushes opening brackets onto the stack. When a closing bracket is encountered, we check if it matches the top of the stack. If it does, we pop the top element. If it doesn’t match or the stack is empty, the string is invalid. At the end, the stack should be empty for a valid string.
4. Merge Two Sorted Lists
This problem tests your ability to work with linked lists and merge algorithms.
Problem Statement:
You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.
Example:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]Solution:
We can solve this problem by creating a dummy node and building the merged list from there:
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
if (list1) tail->next = list1;
if (list2) tail->next = list2;
return dummy.next;
}
};This solution compares the values of nodes from both lists and adds the smaller one to the merged list. We continue this process until we exhaust one of the lists. Then, we append any remaining nodes from the non-empty list.
5. Maximum Subarray
The “Maximum Subarray” problem tests your understanding of dynamic programming and the Kadane’s algorithm.
Problem Statement:
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.Solution:
We can solve this problem using Kadane’s algorithm:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < nums.size(); i++) {
currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
};This solution maintains two variables: maxSum for the overall maximum sum, and currentSum for the maximum sum ending at the current position. We iterate through the array, updating currentSum and maxSum as we go.
6. Binary Tree Level Order Traversal
This problem tests your understanding of tree traversal and breadth-first search (BFS) algorithms.
Problem Statement:
Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Example:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]Solution:
We can solve this problem using a queue to perform a breadth-first search:
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector<int> currentLevel;
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
currentLevel.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(currentLevel);
}
return result;
}
};This solution uses a queue to process nodes level by level. For each level, we process all nodes currently in the queue, adding their values to the current level’s result and enqueueing their children for the next level.
7. Climbing Stairs
The “Climbing Stairs” problem is a classic dynamic programming question that tests your ability to recognize and solve problems with overlapping subproblems.
Problem Statement:
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 stepSolution:
We can solve this problem using dynamic programming:
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
vector<int> dp(n+1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};This solution uses a bottom-up approach. We start with the base cases (1 and 2 steps) and build up to n. The number of ways to reach step i is the sum of the ways to reach step i-1 and i-2.
8. Best Time to Buy and Sell Stock
This problem tests your ability to optimize for maximum profit and work with arrays.
Problem Statement:
You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.Solution:
We can solve this problem by keeping track of the minimum price seen so far and the maximum profit:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int maxProfit = 0;
for (int price : prices) {
minPrice = min(minPrice, price);
maxProfit = max(maxProfit, price - minPrice);
}
return maxProfit;
}
};This solution iterates through the prices once. At each step, we update the minimum price seen so far and calculate the potential profit if we sell at the current price. We keep track of the maximum profit seen.
9. Longest Palindromic Substring
This problem tests your ability to work with strings and implement dynamic programming or expand-around-center techniques.
Problem Statement:
Given a string s, return the longest palindromic substring in s.
Example:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.Solution:
We can solve this problem using the expand-around-center technique:
class Solution {
public:
string longestPalindrome(string s) {
if (s.length() < 2) return s;
int start = 0, maxLength = 1;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = max(len1, len2);
if (len > maxLength) {
start = i - (len - 1) / 2;
maxLength = len;
}
}
return s.substr(start, maxLength);
}
private:
int expandAroundCenter(const string& s, int left, int right) {
while (left >= 0 && right < s.length() && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1;
}
};This solution considers each character as a potential center of a palindrome and expands around it. We consider both odd-length palindromes (centered at a single character) and even-length palindromes (centered between two characters).
10. Implement Trie (Prefix Tree)
This problem tests your understanding of tree data structures and ability to implement a more complex data structure from scratch.
Problem Statement:
Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns trueSolution:
Here’s an implementation of a Trie:
class TrieNode {
public:
TrieNode* children[26];
bool isEndOfWord;
TrieNode() {
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
isEndOfWord = false;
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEndOfWord = true;
}
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return node->isEndOfWord;
}
bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
int index = c - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return true;
}
};This implementation uses a TrieNode class to represent each node in the trie. Each node has an array of 26 child pointers (for lowercase English letters) and a boolean flag to indicate if it’s the end of a word. The Trie class provides methods to insert words, search for words, and check if any word starts with a given prefix.
Conclusion
Mastering these top 10 coding interview questions will significantly boost your chances of success in technical interviews. These problems cover a wide range of topics including arrays, linked lists, strings, trees, dynamic programming, and data structures like stacks and tries. Remember, the key to success in coding interviews is not just knowing the solutions, but understanding the underlying concepts and being able to explain your thought process clearly.
As you prepare, make sure to practice implementing these solutions, analyze their time and space complexities, and consider alternative approaches. Also, don’t forget to verbalize your thought process as you solve problems – this is a crucial skill that interviewers look for.
Keep in mind that while these questions are common, they’re just a starting point. Real interviews may involve variations of these problems or entirely different questions. The skills you develop in solving these problems – problem-solving, algorithmic thinking, and code optimization – will serve you well regardless of the specific questions you encounter.
Good luck with your interview preparation, and remember that consistent practice is key to success in coding interviews!