Set 2- Common 20 Interview questions and ans. Data Structures and Algorithms (DSA) with explanations and code
---
1. Two Sum (Array + Hashing)
Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
def two_sum(nums, target):
hashmap = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hashmap:
return [hashmap[complement], i]
hashmap[num] = i
Explanation:
We use a hash map to store numbers we've seen and their indices.
For each element num, we compute target - num (called complement).
If complement is already in the hash map, we found the answer.
Time complexity: O(n), Space: O(n)
2. Reverse a Linked List (Linked List)
Problem: Reverse a singly linked list.
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
def reverse_list(head):
prev = None
current = head
while current:
nxt = current.next
current.next = prev
prev = current
current = nxt
return prev
Explanation:
Iteratively reverse links: make current.next point to prev.
Move prev and current forward each step.
Time: O(n), Space: O(1)
3. Valid Parentheses (Stack)
Problem: Given a string containing '(', ')', '{', '}', '[' and ']', check if input is valid.
def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top = stack.pop() if stack else '#'
if mapping[char] != top:
return False
else:
stack.append(char)
return not stack
Explanation:
Push opening brackets to stack.
For closing brackets, pop and check if it matches the last open.
Stack should be empty at the end for it to be valid.
4. Maximum Subarray Sum (Kadane's Algorithm)
Problem: Find the contiguous subarray with the largest sum.
def max_subarray(nums):
max_current = max_global = nums[0]
for i in range(1, len(nums)):
max_current = max(nums[i], max_current + nums[i])
max_global = max(max_global, max_current)
return max_global
Explanation:
At each position, decide whether to continue the previous subarray or start new.
Keep track of max seen so far.
Time: O(n)
5. Inorder Traversal (Binary Tree)
Problem: Perform inorder traversal of a binary tree.
def inorder_traversal(root):
result, stack = [], []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
Explanation:
Use stack to simulate recursive traversal.
Go as left as possible, then visit node, then right.
Time: O(n)
6. Longest Common Subsequence (DP)
Problem: Given two strings text1 and text2, return the length of their longest common subsequence.
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m):
for j in range(n):
if text1[i] == text2[j]:
dp[i+1][j+1] = 1 + dp[i][j]
else:
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
return dp[m][n]
Explanation:
Use a 2D DP table where dp[i][j] is the length of LCS of text1[0:i] and text2[0:j].
If characters match, increment diagonal value; otherwise take max from left/top.
Time: O(mn), Space: O(mn)
7. N-Queens (Backtracking)
Problem: Place n queens on an n x n board such that no two queens threaten each other.
def solve_n_queens(n):
res = []
board = [-1] * n
def is_safe(row, col):
for prev_row in range(row):
if board[prev_row] == col or \
abs(board[prev_row] - col) == abs(prev_row - row):
return False
return True
def backtrack(row):
if row == n:
res.append(["."*col + "Q" + "."*(n-col-1) for col in board])
return
for col in range(n):
if is_safe(row, col):
board[row] = col
backtrack(row + 1)
backtrack(0)
return res
Explanation:
Place a queen in a column only if it’s safe (no vertical/diagonal threats).
Use backtracking to explore all combinations.
Time: O(n!), Space: O(n)
8. Sliding Window Maximum
Problem: Given an array and a window size k, return the maximum for each sliding window.
from collections import deque
def max_sliding_window(nums, k):
dq = deque()
result = []
for i in range(len(nums)):
while dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
Explanation:
Maintain deque of indices; ensure front has the max.
Remove indices that are out of the window or less than current value.
Time: O(n)
9. Lowest Common Ancestor (LCA) in Binary Tree
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
Explanation:
If current node is one of p or q, return it.
If both left and right have a result, current node is the LCA.
Time: O(n)
10. Longest Substring Without Repeating Characters
def length_of_longest_substring(s):
char_index = {}
left = max_len = 0
for right, c in enumerate(s):
if c in char_index and char_index[c] >= left:
left = char_index[c] + 1
char_index[c] = right
max_len = max(max_len, right - left + 1)
return max_len
Explanation:
Use sliding window; track last index of each character.
Move left pointer to skip duplicates.
Time: O(n)
___
Here is the continuation (items 11–20) in plain text:
---
11. Merge Intervals
Problem: Merge all overlapping intervals.
def merge(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
Explanation:
Sort by start time.
If current interval overlaps with the previous, merge them.
Time: O(n log n)
12. Detect Cycle in Linked List
Problem: Check if a linked list has a cycle.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Explanation:
Use Floyd’s cycle detection algorithm (tortoise and hare).
If fast and slow meet, there's a cycle.
Time: O(n), Space: O(1)
13. Word Break (DP)
Problem: Given a string and a dictionary, return true if the string can be segmented.
def word_break(s, wordDict):
dp = [False] * (len(s)+1)
dp[0] = True
wordSet = set(wordDict)
for i in range(1, len(s)+1):
for j in range(i):
if dp[j] and s[j:i] in wordSet:
dp[i] = True
break
return dp[-1]
Explanation:
Use DP where dp[i] is True if s[:i] can be segmented.
Check all j < i if s[j:i] is a word.
Time: O(n²)
14. Clone Graph (DFS)
Problem: Clone an undirected graph.
def clone_graph(node):
if not node:
return None
visited = {}
def dfs(n):
if n in visited:
return visited[n]
copy = Node(n.val)
visited[n] = copy
for neighbor in n.neighbors:
copy.neighbors.append(dfs(neighbor))
return copy
return dfs(node)
Explanation:
Use DFS with a visited map to avoid cycles.
Clone each node and its neighbors recursively.
Time: O(n)
15. Top K Frequent Elements (Heap)
Problem: Return k most frequent elements.
from collections import Counter
import heapq
def top_k_frequent(nums, k):
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
Explanation:
Use Counter to count frequency.
Use heapq.nlargest with frequency as key.
Time: O(n log k)
16. Course Schedule (Topological Sort)
Problem: Detect if a cycle exists in a course prerequisite graph.
from collections import defaultdict, deque
def can_finish(numCourses, prerequisites):
graph = defaultdict(list)
indegree = [0] * numCourses
for dest, src in prerequisites:
graph[src].append(dest)
indegree[dest] += 1
queue = deque([i for i in range(numCourses) if indegree[i] == 0])
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return count == numCourses
Explanation:
Kahn’s algorithm for topological sort.
If all courses can be taken (no cycles), return True.
Time: O(V + E)
17. Median of Two Sorted Arrays (Binary Search)
Problem: Find median of two sorted arrays.
def find_median_sorted_arrays(nums1, nums2):
A, B = nums1, nums2
if len(A) > len(B):
A, B = B, A
total = len(A) + len(B)
half = total // 2
l, r = 0, len(A) - 1
while True:
i = (l + r) // 2
j = half - i - 2
Aleft = A[i] if i >= 0 else float("-infinity")
Aright = A[i+1] if i+1 < len(A) else float("infinity")
Bleft = B[j] if j >= 0 else float("-infinity")
Bright = B[j+1] if j+1 < len(B) else float("infinity")
if Aleft <= Bright and Bleft <= Aright:
if total % 2:
return min(Aright, Bright)
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
elif Aleft > Bright:
r = i - 1
else:
l = i + 1
Explanation:
Binary search on the smaller array to partition both arrays correctly.
Time: O(log(min(m,n)))
18. Trie (Prefix Tree)
Problem: Implement a trie with insert, search, and startsWith.
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.end
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
Explanation:
Each node stores its children and a flag for word end.
Insert and search operate character by character.
19. Find Peak Element (Binary Search)
Problem: Find a peak element (greater than neighbors).
def find_peak_element(nums):
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] > nums[mid + 1]:
r = mid
else:
l = mid + 1
return l
Explanation:
Binary search for a peak.
If mid > mid+1, peak is on the left. Else on the right.
Time: O(log n)
20. Serialize and Deserialize Binary Tree
Problem: Convert binary tree to string and back.
class Codec:
def serialize(self, root):
def dfs(node):
if not node:
vals.append("N")
return
vals.append(str(node.val))
dfs(node.left)
dfs(node.right)
vals = []
dfs(root)
return ",".join(vals)
def deserialize(self, data):
def dfs():
val = next(vals)
if val == "N":
return None
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
return node
vals = iter(data.split(","))
return dfs()
Explanation:
Use pre-order traversal. Use "N" as placeholder for nulls.
Rebuild using iterator during deserialization.
Time: O(n)
Comments
Post a Comment