Most Asked Programming Interview Questions: A Comprehensive Guide

Most Asked Programming Interview Questions

Programming interviews are a crucial part of the hiring process in the tech industry. They assess your problem-solving skills, coding proficiency, and understanding of data structures and algorithms. This blog post compiles some of the most frequently asked programming interview questions across various topics such as Arrays, Linked Lists, Strings, Binary Trees, Graphs, and Dynamic Programming.

Arrays

1. How is an array sorted using Quicksort?

• Answer: Quicksort is a divide-and-conquer algorithm that selects a ‘pivot’ element and partitions the array around the pivot, so that elements less than the pivot are on the left, and those greater are on the right. The process is then recursively applied to the sub-arrays.

   def quicksort(arr):
       if len(arr) <= 1:
           return arr
       pivot = arr[len(arr) // 2]
       left = [x for x in arr if x < pivot]
       middle = [x for x in arr if x == pivot]
       right = [x for x in arr if x > pivot]
       return quicksort(left) + middle + quicksort(right)

2. How do you reverse an array?

• Answer: Reversing an array involves swapping the elements from the start with the elements from the end, moving towards the center.

   def reverse_array(arr):
       start, end = 0, len(arr) - 1
       while start < end:
           arr[start], arr[end] = arr[end], arr[start]
           start += 1
           end -= 1
       return arr

3. How do you remove duplicates from an array?

• Answer: Duplicates can be removed by converting the array into a set, which inherently removes duplicates, and then converting it back to a list.

   def remove_duplicates(arr):
       return list(set(arr))

4. How do you find the 2nd largest number in an unsorted integer array?

• Answer: You can find the 2nd largest number by first finding the maximum, then removing all occurrences of it, and finally finding the new maximum.

   def second_largest(arr):
       first = second = float('-inf')
       for num in arr:
           if num > first:
               second = first
               first = num
           elif first > num > second:
               second = num
       return second

Linked Lists

1. How do you find the length of a linked list?

• Answer: Traverse the linked list from the head to the end, counting the nodes.

   class Node:
       def __init__(self, data):
           self.data = data
           self.next = None

   def length_of_linked_list(head):
       count = 0
       current = head
       while current:
           count += 1
           current = current.next
       return count

2. How do you reverse a linked list?

• Answer: Reverse a linked list by iterating through it and reversing the pointers.

   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

3. How do you find the third node from the end?

• Answer: Use two pointers, with one starting three nodes ahead. When the first pointer reaches the end, the second pointer will be at the third node from the end.

   def third_from_end(head):
       first = head
       second = head
       for _ in range(3):
           if first is None:
               return None
           first = first.next
       while first:
           first = first.next
           second = second.next
       return second

4. How are duplicate nodes removed in an unsorted linked list?

• Answer: Use a hash set to keep track of seen values as you iterate through the list, removing duplicates as you go.

   def remove_duplicates(head):
       if not head:
           return None
       seen = set()
       current = head
       seen.add(current.data)
       while current.next:
           if current.next.data in seen:
               current.next = current.next.next
           else:
               seen.add(current.next.data)
               current = current.next
       return head

Strings

1. How do you check if a string contains only digits?

• Answer: Use the isdigit() method to check if all characters in the string are digits.

   def is_digit_only(s):
       return s.isdigit()

2. How can a given string be reversed?

• Answer: Reverse the string by slicing it.

   def reverse_string(s):
       return s[::-1]

3. How do you find the first non-repeated character?

• Answer: Use a dictionary to count the frequency of each character, then return the first character with a count of 1.

   def first_non_repeated(s):
       count = {}
       for char in s:
           count[char] = count.get(char, 0) + 1
       for char in s:
           if count[char] == 1:
               return char
       return None

4. How do you find duplicate characters in strings?

• Answer: Use a dictionary to count characters and return those with a count greater than 1.

   def find_duplicates(s):
       count = {}
       duplicates = []
       for char in s:
           count[char] = count.get(char, 0) + 1
       for char, c in count.items():
           if c > 1:
               duplicates.append(char)
       return duplicates

Binary Trees

1. How are all leaves of a binary tree printed?

• Answer: Use a recursive function to traverse the tree and print nodes with no children.

   class TreeNode:
       def __init__(self, value):
           self.left = None
           self.right = None
           self.value = value

   def print_leaves(root):
       if root:
           if not root.left and not root.right:
               print(root.value)
           print_leaves(root.left)
           print_leaves(root.right)

2. How do you check if a tree is a binary search tree?

• Answer: Use a recursive function to ensure each node follows the binary search tree properties.

   def is_bst(node, left=float('-inf'), right=float('inf')):
       if not node:
           return True
       if not (left < node.value < right):
           return False
       return (is_bst(node.left, left, node.value) and
               is_bst(node.right, node.value, right))

3. How is a binary search tree implemented?

• Answer: Implement a binary search tree with insert, search, and delete operations.

   class BSTNode:
       def __init__(self, value):
           self.left = None
           self.right = None
           self.value = value

       def insert(self, value):
           if value < self.value:
               if self.left:
                   self.left.insert(value)
               else:
                   self.left = BSTNode(value)
           else:
               if self.right:
                   self.right.insert(value)
               else:
                   self.right = BSTNode(value)

       def search(self, value):
           if value < self.value:
               return self.left.search(value) if self.left else False
           elif value > self.value:
               return self.right.search(value) if self.right else False
           return True

https://updategadh.com/category/final-year-projects

4. Find the lowest common ancestor in a binary tree?

• Answer: Use recursion to find the lowest common ancestor by checking the position of the nodes in relation to the root.

   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

Graph

1. How to detect a cycle in a directed graph?

• Answer: Use depth-first search (DFS) with a recursion stack to detect cycles in a directed graph.

   def is_cyclic(graph, v, visited, rec_stack):
       visited[v] = True
       rec_stack[v] = True
       for neighbor in graph[v]:
           if not visited[neighbor]:
               if is_cyclic(graph, neighbor, visited, rec_stack):
                   return True
           elif rec_stack[neighbor]:
               return True
       rec_stack[v] = False
       return False

   def has_cycle(graph):
       visited = [False] * len(graph)
       rec_stack = [False] * len(graph)
       for node in range(len(graph)):
           if not visited[node]:
               if is_cyclic(graph, node, visited, rec_stack):
                   return True
       return False

2. **How to detect a cycle in an undirected graph?**

• Answer: Use depth-first search (DFS) while keeping track of the parent node to detect cycles in an undirected graph.

   def is_cyclic_undirected(graph, v, visited, parent):
       visited[v] = True
       for neighbor in graph[v]:
           if not visited[neighbor]:
               if is_cyclic_undirected(graph, neighbor, visited, v):
                   return True
           elif parent != neighbor:
               return True
       return False

   def has_cycle_undirected(graph):
       visited = [False] * len(graph)
       for node in range(len(graph)):
           if not visited[node]:
               if is_cyclic_undirected(graph, node, visited, -1):
                   return True
       return False

https://updategadh.com/category/interview-question

3. Find the total number of strongly connected components?

• Answer: Use Kosaraju’s algorithm or Tarjan’s algorithm to find strongly connected components.

   from collections import defaultdict

   class Graph:
       def __init__(self, vertices):
           self.graph = defaultdict(list)
           self.V = vertices

       def add_edge(self, u, v):
           self.graph[u].append(v)

       def dfs(self, v, visited):
           visited[v] = True
           for neighbor in self.graph[v]:
               if not visited[neighbor]:
                   self.dfs(neighbor, visited)

       def fill_order(self, v, visited, stack):
           visited[v] = True
           for neighbor in self.graph[v]:
               if not visited[neighbor]:
                   self.fill_order(neighbor, visited, stack)
           stack.append(v)

       def get_transpose(self):
           g = Graph(self.V)
           for i in self.graph:
               for j in self.graph[i]:
                   g.add_edge(j, i)
           return g

       def find_sccs(self):
           stack = []
           visited = [False] * self.V
           for i in range(self.V):
               if not visited[i]:
                   self.fill_order(i, visited, stack)
           gr = self.get_transpose()
           visited = [False] * self.V
           scc_count = 0
           while stack:
               i = stack.pop()
               if not visited[i]:
                   gr.dfs(i, visited)
                   scc_count += 1
           return scc_count

4. Find whether a path exists between two nodes of a graph?

• Answer: Use depth-first search (DFS) or breadth-first search (BFS) to determine if a path exists between two nodes.

   def dfs_path_exists(graph, start, end, visited):
       visited[start] = True
       if start == end:
           return True
       for neighbor in graph[start]:
           if not visited[neighbor]:
               if dfs_path_exists(graph, neighbor, end, visited):
                   return True
       return False

   def path_exists(graph, start, end):
       visited = [False] * len(graph)
       return dfs_path_exists(graph, start, end, visited)

5. Find the minimum number of swaps required to sort an array.

• Answer: Use cycle detection in graphs where the array elements represent the vertices, and edges are defined by element positions.

   def min_swaps(arr):
       n = len(arr)
       arr_pos = [*enumerate(arr)]
       arr_pos.sort(key=lambda it: it[1])
       visited = {k: False for k in range(n)}
       swaps = 0
       for i in range(n):
           if visited[i] or arr_pos[i][0] == i:
               continue
           cycle_size = 0
           j = i
           while not visited[j]:
               visited[j] = True
               j = arr_pos[j][0]
               cycle_size += 1
           if cycle_size > 0:
               swaps += (cycle_size - 1)
       return swaps

https://updategadh.com/category/php-project

Dynamic Programming

1. Find the longest common subsequence?

• Answer: Use dynamic programming to build a table that compares the substrings of the two sequences.

   def lcs(X, Y):
       m = len(X)
       n = len(Y)
       L = [[None] * (n + 1) for i in range(m + 1)]
       for i in range(m + 1):
           for j in range(n + 1):
               if i == 0 or j == 0:
                   L[i][j] = 0
               elif X[i - 1] == Y[j - 1]:
                   L[i][j] = L[i - 1][j - 1] + 1
               else:
                   L[i][j] = max(L[i - 1][j], L[i][j - 1])
       return L[m][n]

2. Find the longest common substring?

• Answer: Use dynamic programming to build a table and track the longest substring.

   def longest_common_substring(X, Y):
       m = len(X)
       n = len(Y)
       result = 0
       length = [[0] * (n + 1) for i in range(m + 1)]
       for i in range(m + 1):
           for j in range(n + 1):
               if i == 0 or j == 0:
                   length[i][j] = 0
               elif X[i - 1] == Y[j - 1]:
                   length[i][j] = length[i - 1][j - 1] + 1
                   result = max(result, length[i][j])
               else:
                   length[i][j] = 0
       return result

3. Coin change problem?

• Answer: Use dynamic programming to find the minimum number of coins needed to make up a given amount.

   def coin_change(coins, amount):
       dp = [float('inf')] * (amount + 1)
       dp[0] = 0
       for coin in coins:
           for x in range(coin, amount + 1):
               dp[x] = min(dp[x], dp[x - coin] + 1)
       return dp[amount] if dp[amount] != float('inf') else -1

4. Box stacking problem?

• Answer: Use dynamic programming to find the maximum height of stackable boxes.

   class Box:
       def __init__(self, h, w, d):
           self.h = h
           self.w = w
           self.d = d

   def max_stack_height(boxes):
       n = len(boxes)
       all_rotations = []
       for box in boxes:
           all_rotations.append(Box(box.h, max(box.w, box.d), min(box.w, box.d)))
           all_rotations.append(Box(box.w, max(box.h, box.d), min(box.h, box.d)))
           all_rotations.append(Box(box.d, max(box.h, box.w), min(box.h, box.w)))
       all_rotations.sort(key=lambda box: box.w * box.d, reverse=True)
       max_height = [0] * len(all_rotations)
       for i in range(len(all_rotations)):
           max_height[i] = all_rotations[i].h
       for i in range(1, len(all_rotations)):
           for j in range(0, i):
               if (all_rotations[i].w < all_rotations[j].w and
                       all_rotations[i].d < all_rotations[j].d):
                   max_height[i] = max(max_height[i], max_height[j] + all_rotations[i].h)
       return max(max_height)

5. Count the number of ways to cover a distance?

• Answer: Use dynamic programming to count the number of ways to cover a given distance with 1, 2, or 3 steps.

   def count_ways(n):
       res = [0] * (n + 1)
       res[0] = 1
       res[1] = 1
       res[2] = 2
       for i in range(3, n + 1):
           res[i] = res[i - 1] + res[i - 2] + res[i - 3]
       return res[n]

Tags

• Programming Interviews
• Coding Questions
• Arrays
• Linked Lists
• Strings
• Binary Trees
• Graphs
• Dynamic Programming
• Data Structures and Algorithms
• Technical Interview Preparation

programming interview,coding interview,coding interview questions and answers,c programming questions asked in interview,programming interview questions and answers,c programming interview questions and answers,c programming interview questions,c programming interview questions and answers for freshers,programming,programming interview question and answer,important c programming questions,google coding interview questions,algorithm interview questions interview questions and answers,job interview questions and answers,how to answer interview questions,interview tips,job interview questions,common interview questions,job interview tips,interview questions,common interview questions and answers,interview preparation,job interview,interview,hr interview questions,tough interview questions,hardest interview questions,freshers interview questions,most common interview questions,30 interview questions