248 questions on data structures and algorithms, answered at full depth for embedded software, firmware, and senior technical roles. Built from the curriculum of Mastering Data Structures and Algorithms using C and C++, with every answer extended into the firmware context: ISRs, RTOS internals, DMA, cache behaviour, stack budgets, flash versus RAM, and worst case timing.
Every question is laid out the same way.
- Say this out loud is the thirty second spoken answer for the interview room.
- The full explanation is the real understanding, in plain words.
- Worked example is code or a memory diagram you can trace by hand.
- Why it matters in firmware is the layer that separates a senior candidate.
- Mistakes people make is what actually costs people the offer.
Each part ends with a one line per concept revision sheet, intended for the day before an interview.
How to use this guide
Reading it cold. Work through in order. Parts 1 and 2 carry the memory model that later parts assume: the flash and RAM map, alignment, padding, and the difference between visibility, atomicity, and ordering. Skipping them makes later answers look like trivia.
Preparing for a specific interview. Part 4 (Stack and Queue) and Part 3 (Linked Lists) carry the highest density of embedded specific material: ring buffers, ISR to task handoff, intrusive RTOS lists, pool allocators, and stack overflow detection. Part 6 (Sorting) and Part 7 (Complexity) carry the judgement questions about worst case versus average case.
The night before. Read only the revision sheets at the end of each part. There are seven of them, roughly thirty lines each.
Five themes run through the whole guide, and they are what an embedded interviewer is really assessing.
- Worst case over average case. Heap sort over quick sort, preallocation over rehashing, sorted arrays over hash tables. Wherever a deadline exists, the bound is the requirement.
- Static over dynamic. Fixed pools over
malloc,consttables in flash over runtime construction, capacity fixed at link time so the build fails on your desk rather than the product failing in the field. - Iteration over recursion. An explicit stack whose size appears in the linker map and whose overflow returns an error, instead of a call stack that silently corrupts a neighbouring task.
- Measure rather than assume. Cache behaviour, small n constants, and stack high water marks defeat theory regularly.
- Ask about constraints before proposing a solution. Input size, memory budget, deadline, and whether the data is static. The right structure follows from those four answers.
Contents
| Part | Sections |
|---|---|
| Part 1: C Fundamentals, Pointers and Memory | C and C++ Fundamentals, Pointers and Memory |
| Part 2: Arrays and Strings | Arrays, Strings |
| Part 3: Recursion and Linked Lists | Recursion, Linked Lists |
| Part 4: Stack and Queue | Stack, Queue |
| Part 5: Trees and Binary Search Trees | Trees, Binary Search Tree |
| Part 6: Heap and Sorting | Heap, Sorting |
| Part 7: Hashing and Complexity | Hashing, Complexity |
Question index
C and C++ Fundamentals
- Q1. Difference between C and C++?
- Q2. Stack vs heap memory?
- Q3. What happens during a function call?
- Q4. What is memory alignment?
- Q5. Why does structure padding happen?
- Q6. Difference between struct and class in C++?
- Q7. Explain pass by value.
- Q8. Explain pass by pointer.
- Q9. Explain pass by reference.
- Q10. Why use const?
- Q11. Static variable lifetime?
- Q12. Global variable lifetime?
- Q13. Automatic variables?
- Q14. Register keyword?
- Q15. Volatile keyword?
Pointers and Memory
- Q16. What is a pointer?
- Q17. Pointer arithmetic?
- Q18. Void pointer?
- Q19. Function pointer?
- Q20. Pointer to pointer?
- Q21. Wild pointer?
- Q22. Dangling pointer?
- Q23. Null pointer?
- Q24. Difference between NULL and nullptr?
- Q25. Double free problem?
- Q26. Memory leak?
- Q27. Shallow copy?
- Q28. Deep copy?
- Q29. Pointer to structure?
- Q30. Why use pointers?
- Q31. Pointer vs reference?
- Q32. Can a pointer point to a constant?
- Q33. Constant pointer?
- Q34. Pointer aliasing?
- Q35. How do you debug pointer corruption?
Arrays
- Q36. Static vs dynamic array?
- Q37. Array representation in memory?
- Q38. Row major formula?
- Q39. Column major formula?
- Q40. Time complexity of insertion in an array?
- Q41. Time complexity of deletion?
- Q42. Binary search?
- Q43. Why does binary search require a sorted array?
- Q44. Reverse an array?
- Q45. Rotate an array?
- Q46. Find the missing number?
- Q47. Duplicate detection?
- Q48. Pair sum, find two elements adding to a target?
- Q49. Merge two sorted arrays?
- Q50. Union of two sorted arrays?
- Q51. Intersection of two sorted arrays?
- Q52. Difference of two sorted arrays?
- Q53. Find max and min in one pass?
- Q54. Check whether an array is sorted?
- Q55. How do you increase the size of a dynamic array?
Strings
- Q56. Reverse a string.
- Q57. Reverse the words in a sentence.
- Q58. Palindrome check?
- Q59. String comparison?
- Q60. Anagram check?
- Q61. Find duplicate characters?
- Q62. Count vowels?
- Q63. Count words?
- Q64. Remove spaces?
- Q65. String validation?
- Q66. String tokenization?
- Q67. Implement strstr, substring search.
- Q68. Implement strcpy.
- Q69. Implement strlen.
- Q70. Implement strcmp.
- Q71. Why do C strings end with ‘\0’?
- Q72. UTF-8 vs ASCII?
- Q73. Common string bugs in interviews and in production?
Recursion
- Q74. What is recursion?
- Q75. Tail recursion?
- Q76. Head recursion?
- Q77. Tree recursion?
- Q78. Indirect recursion?
- Q79. Nested recursion?
- Q80. Fibonacci recursion?
- Q81. Memoization?
- Q82. Tower of Hanoi?
- Q83. Taylor series by recursion?
- Q84. Factorial?
- Q85. Power function?
- Q86. nCr by recursion?
- Q87. Recurrence relation?
- Q88. Space complexity of recursion?
- Q89. Stack overflow?
- Q90. Recursive linked list traversal?
- Q91. When is recursion a bad idea?
- Q92. Recursive binary search?
- Q93. Convert recursion to iteration.
Linked Lists
- Q94. Singly linked list.
- Q95. Doubly linked list.
- Q96. Circular linked list.
- Q97. Circular doubly linked list with a sentinel.
- Q98. Insert at the beginning.
- Q99. Insert at the end.
- Q100. Insert at a position.
- Q101. Delete a node.
- Q102. Reverse a list, iteratively.
- Q103. Recursive reverse.
- Q104. Find the middle node.
- Q105. Detect a loop.
- Q106. Floyd’s algorithm: find the loop start and its length.
- Q107. Remove duplicates.
- Q108. Sorted insert.
- Q109. Merge two sorted lists.
- Q110. Concatenate two lists.
- Q111. Find the intersection of two lists.
- Q112. Delete the nth node from the end.
- Q113. Reverse every k nodes.
- Q114. Clone a linked list with random pointers.
- Q115. Why choose a linked list over an array?
- Q116. Complexity comparison, array versus linked list.
- Q117. Memory overhead.
- Q118. Cache friendliness.
- Q119. Applications of circular lists.
- Q120. Linked lists in an RTOS.
- Q121. Free list and pool allocator implementation.
- Q122. Lock free linked list.
- Q123. Real embedded applications of linked lists.
Stack
- Q124. Stack implementation.
- Q125. Stack using an array.
- Q126. Stack using a linked list.
- Q127. Parentheses matching.
- Q128. Infix to postfix conversion.
- Q129. Postfix evaluation.
- Q130. Stack overflow.
- Q131. Stack underflow.
- Q132. The function call stack.
- Q133. Expression evaluation.
- Q134. Browser back implementation.
- Q135. Undo implementation.
- Q136. Depth first search using a stack.
- Q137. Embedded stack overflow detection.
- Q138. RTOS stack monitoring.
Queue
- Q139. Queue implementation.
- Q140. Circular queue.
- Q141. Deque, double ended queue.
- Q142. Priority queue.
- Q143. Queue using a linked list.
- Q144. Queue using an array.
- Q145. Queue using two stacks.
- Q146. Circular queue advantages.
- Q147. The embedded ring buffer.
- Q148. Producer consumer.
- Q149. ISR to task queue.
- Q150. DMA queue and descriptor chains.
- Q151. Lock free queue.
- Q152. RTOS queue.
- Q153. Queue applications.
Trees
- Q154. Binary tree.
- Q155. Complete binary tree.
- Q156. Full binary tree.
- Q157. Strict binary tree.
- Q158. Perfect binary tree.
- Q159. Height and depth.
- Q160. Preorder traversal.
- Q161. Inorder traversal.
- Q162. Postorder traversal.
- Q163. Level order traversal.
- Q164. Tree traversal by recursion.
- Q165. Iterative traversal.
- Q166. Build a tree from traversals.
- Q167. Count nodes.
- Q168. Count leaf nodes.
- Q169. Height calculation.
- Q170. Diameter of a tree.
- Q171. Lowest common ancestor.
- Q172. Serialize and deserialize a tree.
- Q173. Trees in embedded systems.
Binary Search Tree
- Q174. BST properties.
- Q175. BST search.
- Q176. BST insert.
- Q177. BST delete.
- Q178. Inorder successor.
- Q179. Inorder predecessor.
- Q180. Generate a BST from a sequence.
- Q181. Validate a BST.
- Q182. Balance factor.
- Q183. BST worst case.
- Q184. AVL versus plain BST, and AVL versus red-black.
- Q185. Red-black tree.
- Q186. BST complexity.
- Q187. Real applications of BSTs.
- Q188. BST interview pitfalls.
Heap
- Q189. Max heap.
- Q190. Min heap.
- Q191. Heapify.
- Q192. Heap insert.
- Q193. Heap delete, extract the root.
- Q194. Heap sort.
- Q195. Priority queue.
- Q196. Heap complexity.
- Q197. Scheduler implementation with a heap.
- Q198. Heaps in embedded systems.
Sorting
- Q199. Bubble sort.
- Q200. Selection sort.
- Q201. Insertion sort.
- Q202. Merge sort.
- Q203. Quick sort.
- Q204. Heap sort.
- Q205. Counting sort.
- Q206. Radix sort.
- Q207. Bucket sort.
- Q208. Shell sort.
- Q209. Which sorts are stable?
- Q210. Which sorts are in place?
- Q211. Worst cases.
- Q212. Best cases.
- Q213. Average cases.
- Q214. Which sort for embedded?
- Q215. Why does merge sort need extra memory?
- Q216. Quick sort pivot selection.
- Q217. Hybrid sorting.
- Q218. STL sort implementation.
Hashing
- Q219. Hash table.
- Q220. Hash function.
- Q221. Collision.
- Q222. Separate chaining.
- Q223. Linear probing.
- Q224. Quadratic probing.
- Q225. Double hashing.
- Q226. Load factor.
- Q227. Rehashing.
- Q228. Hash table complexity.
- Q229. Embedded lookup tables.
- Q230. Cache performance of hash tables.
- Q231. Perfect hashing.
- Q232. Bloom filter.
- Q233. Hash table applications, including LRU cache.
Complexity
- Q234. Big O.
- Q235. Big Omega.
- Q236. Big Theta.
- Q237. Time complexity.
- Q238. Space complexity.
- Q239. Amortized complexity.
- Q240. Complexity of recursive algorithms.
- Q241. Best case.
- Q242. Worst case.
- Q243. Average case.
- Q244. P, NP, and NP-complete.
- Q245. Tradeoffs.
- Q246. Optimization.
- Q247. Memory versus speed.
- Q248. Complexity interview examples.
The seven parts
| Part | Covers | Questions |
|---|---|---|
| Part 1 | C Fundamentals, Pointers and Memory | Q1–Q35 |
| Part 2 | Arrays and Strings | Q36–Q73 |
| Part 3 | Recursion and Linked Lists | Q74–Q123 |
| Part 4 | Stack and Queue | Q124–Q153 |
| Part 5 | Trees and Binary Search Trees | Q154–Q188 |
| Part 6 | Heap and Sorting | Q189–Q218 |
| Part 7 | Hashing and Complexity | Q219–Q248 |
Start at Part 1 if you are reading cold. Parts 1 and 2 carry the memory model the later parts assume.
Preparing for the architecture round as well? See Firmware Architecture Interview Questions: 100 Q&A.
Work with us
Kalapi Infotech builds firmware for connected embedded products — architecture and BSP work, RTOS and bare-metal development, secure boot and OTA infrastructure. If you are hiring for these roles, or building a product that needs them, we would be glad to talk.
