Saturday, May 6, 2023

Top 25 Recursion Interview Questions Answers for Coding Interviews

Recursion is often dreaded by programmers as its very difficult for many programmers to visualize and understand, but it's a useful problem solving technique which often result in better, simpler and more concise code than their iterative solutions. That begin said, it's often difficult to come up when to use recursion to solve a coding problem. In general, you should use recursion if a problem can be broken down into sub-problems which are exactly the same as original problem. For example, finding a node in a binary tree. If you are asked to find a node with give value in a binary tree than you can solve this with recursion. Why? because you can breakdown the problem into subproblems which are exactly the same like finding a node in binary tree is same as finding the node in left subtree and right subtree.


This is the key. Once you understand that half of the battle is won, the rest is just how to write the recursive solution, and that's where these practice questions will help you. 

In this article, I'll give you some tips to identify when to use recursion as well as some common recursion based coding problems. Once you have gone through them, you will be able to use the concepts you learned to solve a complex real-world problems and also gain the confidence to deal with any recursion related problem in coding interview.

In the past, I have shared dynamic programming questions, system design questions as well data structure and algorithms questions for programmers, which you can also use for a comprehensive practice. 




20+ Recursion based Coding Problems with Solutions

Without wasting any more of your time, here are some of the most common problems which are based upon recursion.

1. Write a method to check if a node exists in a binary tree or not. If the node exists then return true otherwise return false. 

Example
1
/ \
2 3 , findNode(5) ==> true, findNode(10) == false
/ \ / \
4 5 6 7


2. Write a program to find all permutations of a given String? (solution)

3. Given a binary tree, write a method checkBST() to determine if it is a Binary Search Tree. The method should return true if the given tree is a valid binary search tree or false otherwise. 
Example
20
/ \
15 30
/ \
14 18

output ==> true

20
/ \
30 15
/ \
14 18

output ==> false

4. Write a program to reverse a linked list using recursion in Java or any other programming language? (solution)

5. Write a program to find the Nth number in the Fibonacci series (solution)
Example: Fibonacci series starts with double 1 and where next number is sum of previous two number, like 1 1 2 3 5 8 13 
fibonacci(2) = 1
fibonacci(4) = 3
fibonacci(5) = 3

6. Given a binary tree, Write a method findMaxSumLevel to return the level that has the maximum sum. In case the tree is empty return -1. This problem is also known as Find Max Sum Level Problem. 
Example
0 1
/ \
1 2 3 ==> 2
/ \ / \
2 4 5 6 7


7. Write a program to find the greatest common divisor or GCD of a given number? (solution)

8. Write a program to convert a decimal number to a binary number? (solution)

9. Write a program to print pre-order traversal of binary tree? (solution)

10. Write a program to print in-order traversal of binary tree using recursion? (solution)



11. Write a program to print post-order traversal of binary tree? (solution)

12. Write a program to check if a given linked list is a palindrome? (solution)

13. Write a program to check if a given String is a palindrome()? (solution)

14. Write a program to remove duplicates from an unsorted linked list? (solution)

15. Write a program to remove all adjacent duplicates from a string? (solution)

16. Write a program to calculate the sum of digits in a given String? (solution)

17. Write a program to find the length of a given linked list? (solution)

18. Write a program to reverse a given Stack? (solution)

19. Write a program to implement a quicksort algorithm using recursion? (solution)

20. Write a method countLeaves() to find the total number of leaf nodes in a binary tree. If there are no leaf nodes, return 0 (solution) 

Example
1
/ \
2 3 ==> # count = 4
/ \ / \
4 5 6 7

21. Write a Program to print number 1 to 100 without using loop in Java? (solution)





Tips to Solve Coding Problems with Recursion

When faced with coding problems, there are few things you can consider to decide whether you should use recursion or not such as:

1. If a problem can be broken down into smaller sub-problems that can be solved in the same ways as the original problem

2. If the iterative solution of a problem has an arbitrary number of loops.

3. Problems involving recursive data structures like string, linked list, and binary trees.

These are not hard-and-fast rules but provides enough hints to decide when to use recursion. If you are wondering what is a recursive data structure or why we called a string, linked list, and binary tree a recursive data structure then let me tell you that, we call them a recursive data structure because if you take one element out of them they are still the same.

For example, if you take one node out of the binary tree, it's still a binary tree, similarly with string and linked list. Another thing, you can apply all algorithms into a subset in the same way as you apply to the original data structure. For example, the pre-order traversal will work in a full tree in the same way it works in the left or right subtree.

Recursive data structure and tips for coding interivews





Best Resources to learn Recursion for Coding Interviews

As I said, Recursion is often dreaded by developers, but it's an important problem-solving technique and you just can't afford to ignore that. Luckily now there are many courses that you can take to level up your Recursion skill and add this powerful style into your problem-solving skills.

Without wasting any more of your time, here are a couple of useful resources to learn Recursion in-depth, particularly for coding interviews.

1. Recursion for Coding Interviews in Java

This is an excellent course to master Recursion for coding interviews. In this course, you will not only learn how to solve coding problems with recursion but also how and when to use recursion with different data types and data structures. 

You will also be tested with some of the most common recursion interview questions to build the knowledge and confidence needed to solve complex real-world problems and unknown problems on real coding interviews. 

Just in case if you are not familiar with JavaScript, this course is also available with Python and Java and you should use it in the language you are most comfortable with.

Top 10 Recursion Interview Questions for Coding Interviews

Educative as a platform is also a great resource for coding interviews and you can get all of their course access by just $14.9 per month by joining Educative subscription. I highly recommend this to anyone preparing for programming job interviews.


That's all about some of the best, most common Recursion interview questions. You have not only learned how to solve frequently asked recursive problems but also how and when to apply recursion. This is an important skill that will go a long way in your career. I am sure, now you should have more confidence and knowledge to solve the recursion-based problems in real interviews.

Some Useful Resources for Coding Interviews:
Thanks for reading this article so far. If you find these recursion interview questions useful then please share them with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you need more practice, including dozens more problems and solutions for each pattern, check out Grokking Dynamic Programming Patterns for Coding Interviews on Educative. It's an excellent, text-based interactive course to build your Dynamic programming skills. 

at

No comments:

Post a Comment