Recursion Programming Questions

Print All Possible Words from Phone Digits

Print all possible words from phone number digits. This question is asked by companies like microsoft, google, facebook, Amazon. Lets see example input/output to understand this problem. For example if input number is 234, possible words which can be formed are (Alphabetical order): adg adh adi aeg aeh aei afg afh afi bdg bdh bdi Read More →

Robot in an MXN grid

Problem: A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid . How many possible unique paths are there? Approach 1(Recursion): Let NumberOfPaths(m, n) be Read More →

What is the Probability that a Knight Stays on Chessboard

knight_moves

Given the size of the chess board and initial position of the knight, what is the probability that after k moves the knight will be inside the chess board. Note:- 1) The knight makes its all 8 possible moves with equal probability. 2) Once the knight is outside the chess board it cannot come back Read More →

Break String into Dictionary Words

Given an English dictionary (implemented as a hashmap (word -> meaning)) and a string without spaces, output all possible combinations of valid English words that when combined, reproduce the input string. e.g. input: “programmerit” output: {{pro, gram, merit}, {program, merit}, {programmer, it}} output: Solution: Recursive implementation: The idea is simple, we consider each prefix and Read More →

Find nth Fibonacci Number in the Fibonacci sequence?

In the Fibonacci sequence, the first two numbers are 0 and 1 and each number after that is the sum of the previous two numbers in the sequence. So, the sequence looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21… and so on. The “0″ in the sequence is considered to be Read More →

Print Linked List Elements in Reverse order

Write a program to print elements of a linked list in reverse order by using same single linked list. Solution: We can solve this problem without actually reversing the linked list. Using recursion we have given the below solution. This implementation will be internally using stack to store each recursive function call. Complexity: O(N), where Read More →

Recursive Spiral Order Traversal of Tree

This is also called zig-zag order traversal of a binary tree. Approach: To print the nodes in spiral order, nodes at different levels should be printed in alternating order. To change the order of printing alt variable is used. If alt is 1 then printSpiralLevel() prints nodes from left to right else from right to Read More →

Recursive Level Order Traversal of a tree

Level order traversal is also called  breadth first traversal for the tree. Non-Recursive solution of the problem is – Non-recursive Level Order Traversal Approach: There are basically two functions in this method. One is to print all nodes at a given level (printLevel), and other is to get height of tree and print level wise nodes. Read More →

Reverse a Linked List using Recursion

Problem: To test both data structure and the recursion concept, a wonderful and confusing interview question asked to experienced people is “Reverse a linked list using recursion”. Solution: In recursive approach, we need to move to the end of the node. But must stop just before the end of the node, and we should have Read More →

Find the Minimum Element in the Rotated Sorted array

Problem : Find the minimum element in the rotated sorted array. For example we have array as – 1,3,6,9,12,15. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 12,15,1,3,6,9 Solution – The answer to this lies on the fact that if we can find the point on Read More →

How many possible ways the child can run up the ladder

A child is running up a ladder with n steps, and can hop either 1 step or 2 steps at a time. Calculate how many possible ways the child can run up the ladder. This problem is similar to Fibonacci Problem. Each step n can be reached from either two steps below (n-2) or one Read More →

Quick Sort

QuickSort is based on divide-and-conquer approach. QuickSort is inplace sorting algorithm.A sorting algorithm is said to be in-place if it requires very little additional space besides the initial array holding the elements that are to be sorted. The key to the Algorithm is the Partition Procedure, which rearranges the subarray a[p..r] in place. Partition selects Read More →