Interview Bite

If you’re preparing for a software developer or data engineer interview, you can’t ignore DSA (Data Structures and Algorithms). Top tech companies, including Google, Amazon, and Microsoft, rely heavily on DSA to assess problem-solving and analytical skills.

Here’s a carefully curated list of Top DSA Interview Questions you must prepare in 2025 — ideal for both freshers and experienced candidates.

---

🔢 1. What is the difference between an Array and a Linked List?

Array:

• Stored in contiguous memory
• Fixed size
• Fast random access

Linked List:

• Nodes linked using pointers
• Dynamic size
• Slower access but flexible insertions/deletions

---

🔁 2. Reverse a Linked List (Iterative)

pythonCopyEditdef reverse_linked_list(head):
    prev = None
    while head:
        next = head.next
        head.next = prev
        prev = head
        head = next
    return prev

✅ Asked by: Amazon, Flipkart

---

🔍 3. Binary Search Implementation

pythonCopyEditdef binary_search(arr, x):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high)//2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1

📌 Time Complexity: O(log n)

---

🧮 4. Find the Missing Number in an Array from 1 to n

pythonCopyEditdef missing_number(arr):
    n = len(arr) + 1
    total = n * (n + 1) // 2
    return total - sum(arr)

✅ Concepts: Math + Arrays

---

📚 5. Inorder Traversal of Binary Tree

pythonCopyEditdef inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

---

🌲 6. What is a Binary Search Tree (BST)?

A BST is a binary tree where:

• Left child < Parent
• Right child > Parent

Used for fast lookup, insertion, deletion.

---

🔁 7. Level Order Traversal of Tree (BFS)

pythonCopyEditfrom collections import deque
def level_order(root):
    if not root:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val)
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)

---

💡 8. What is Dynamic Programming?

DP is a technique to solve problems by storing solutions to sub-problems to avoid recomputation.

✅ Used for: Fibonacci, Knapsack, LCS

---

🧠 9. Longest Increasing Subsequence (DP)

pythonCopyEditdef LIS(nums):
    dp = [1]*len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

---

🎯 10. Two Sum Problem (Using HashMap)

pythonCopyEditdef two_sum(nums, target):
    seen = {}
    for i, val in enumerate(nums):
        if target - val in seen:
            return [seen[target - val], i]
        seen[val] = i

✅ Asked by: Google, Microsoft, Paytm

---

🧪 11. Cycle Detection in Directed Graph (DFS)

Track recursion stack during DFS traversal to detect cycles.

---

📌 12. Topological Sort of a DAG

Used when dependencies are involved (e.g., course scheduling, task execution).

✅ Algorithm: DFS or Kahn’s Algorithm

---

⚔️ 13. Dijkstra’s Algorithm (Shortest Path)

pythonCopyEditimport heapq
def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        current_dist, node = heapq.heappop(pq)
        for neighbor, weight in graph[node]:
            if dist[neighbor] > current_dist + weight:
                dist[neighbor] = current_dist + weight
                heapq.heappush(pq, (dist[neighbor], neighbor))
    return dist

---

🔁 14. What is a Heap?

Heap is a tree-based structure used to implement priority queues.

✅ Min-Heap: Smallest element at root
✅ Max-Heap: Largest element at root

---

📈 15. Kadane’s Algorithm (Max Subarray Sum)

pythonCopyEditdef max_subarray(nums):
    max_sum = current = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        max_sum = max(max_sum, current)
    return max_sum

---

✅ Final Tips

• Practice these questions on LeetCode, or HackerRank
• Understand time and space complexity for every solution
• Prepare real-world use cases and variations of each question