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 →
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 →
Replace all spaces in a string with “%20″
Problem: Write a C program that will replace all spaces with ‘%20′ Solution: The algorithm is as follows: 1. Count the number of spaces during the first scan of the string. 2. Parse the string again from the end and for each character: If a space is encountered, store “%20”. Else, store the character as … Read More →
Find Position of the only Set Bit
Problem: You are given a number having only one “1″ its binary representation,. You have to find position of it? Solution: First of all we will check if number is power of two, Beacuse then only its binary represenattion will contain only one “1″. After that, start from rightmost bit and one by one check … Read More →
Find if a no is Power of Two
Problem: Write a C program to find if a number is of power of 2? Solution: Method 1: (Using arithmetic) Keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes … Read More →
Move the Spaces to Front of the String
Problem: Given a string that has set of words and spaces, write a program to move the spaces to front of string, you need to traverse the array only once and need to adjust the string in place. string = “move these spaces to beginning” output =” movethesepacestobeginning” Solution: 1) Maintain two indices i and … Read More →
Boolean Matrix Question
Given a matrix of size n x m filled with 0′s and 1′s e.g.: 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 if the matrix has 1 at (i,j), fill the column j and row i with 1′s i.e., we get: 1 1 … Read More →
Find the number occurring odd number of times in an array
You are given an array of integers. All the numbers in array occurs even number of times except the one which occurs odd number of time. You have to find the number in O(N) time and constant space. For eg. 1,4,6,7,3,1,4,7,3,1,6 (given array) Output: 1 Solution: Take bitwise XOR of all the elements. We will … Read More →
Merge k sorted arrays
Given k sorted arrays of size n,merge them into an output array which is sorted. Solution (Using Min Heap): This solution is similar to method 4 of this post. Steps: i. Create a min heap of size k of first element of each array. Repeat steps from 2 to 4 n*k times: ii. Take the … Read More →
Search in a row wise and column wise sorted matrix
You are given an 2D array of MxN which is row and column wise sorted. What is the efficient way to search for an element? Steps: 1) Start from top right element 2) for loop compare this element e with x a) if they are equal then return its position b) e < x then … Read More →
Print all ancestors of a node in binary tree
Problem: Given a Binary tree and a node’s value, Write a function to print all the ancestors of the node. Thinking of solution??Think Recursively.This problem can be easily solved using recursion. We start from the root of the tree and keep going down the tree. When we reach the node with given value we return … Read More →
Print a Square Matrix in Spiral Form
Given a N*N square matrix. Write a code to print it in spiral order. Time Complexity : O(N^2)
What’s going on ?