✅ Coding Interview Questions with Answers [Part-3] 💻🚀

21. Find the longest substring without repeating characters 
Use a sliding window with a set to track characters. 

def length_of_longest_substring(s):
    seen = set()
    left = max_len = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

22. Explain backtracking with N-Queens problem 
Backtracking tries placing a queen in each column, then recursively places the next queen if safe. If no safe position is found, it backtracks. 

def solve_n_queens(n):
    result = []
    board = [-1]×n

    def is_safe(row, col):
        for r in range(row):
            if board[r] == col or abs(board[r] - col) == abs(r - row):
                return False
        return True

    def backtrack(row=0):
        if row == n:
            result.append(board[:])
            return
        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                backtrack(row + 1)
                board[row] = -1

    backtrack()
    return result

23. What is a trie? Where is it used?
A Trie is a tree-like data structure used for efficient retrieval of strings, especially for autocomplete or prefix matching. 
Used in: 
- Dictionary lookups 
- Search engines 
- IP routing

24. Explain bit manipulation tricks 
- Check if number is power of 2: n & (n - 1) == 0 
- Count set bits: bin(n).count('1') 
- Swap without temp: x = x ^ y; y = x ^ y; x = x ^ y

25. Kadane’s Algorithm for maximum subarray sum 

def 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

26. What are heaps and how do they work? 
Heap is a binary tree where parent is always smaller (min-heap) or larger (max-heap) than children. Supports O(log n) insert and delete. 
Use Python’s heapq for min-heaps.

27. Find kth largest element in an array 

import heapq
def find_kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]

28. How to detect cycle in a graph? 
Use DFS with visited and recursion stack. 

def has_cycle(graph):
    visited = set()
    rec_stack = set()

    def dfs(v):
        visited.add(v)
        rec_stack.add(v)
        for neighbor in graph[v]:
              if neighbor not in visited and dfs(neighbor):
                return True
            elif neighbor in rec_stack:
                return True
        rec_stack.remove(v)
        return False

    for node in graph:
        if node not in visited and dfs(node):
            return True
    return False

29. Topological sort of a DAG 
Used to sort tasks with dependencies. 

def topological_sort(graph):
    visited, result = set(), []

    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for neighbor in graph.get(node, []):
            dfs(neighbor)
        result.append(node)

    for node in graph:
        dfs(node)
    return result[::-1]

30. Implement a stack using queues 

from collections import deque

class Stack:
    def init(self):
        self.q = deque()

    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()

    def top(self):
        return self.q[0]

    def empty(self):
        return not self.q

💬 Double Tap ♥️ For Part-4!