## Solving a maze by backtracking

Input : We are given a 2-D maze. The objective is to navigate our way through the maze and travel from the starting position to the specified end point (the goal position). We are supposed to search for a path from the starting position to the goal position till we either find one or exhaust all possibilities. In addition, we are asked to mark the ...

## Explain Catalan numbers.

Catalan numbers are a sequence of natural numbers that occur in various counting problems. This article aims to explain the intuition behind them ; how they are derived and how they come up in seemingly unrelated problems. Consider this "Suppose m = a+b where a=b, votes were cast in an election, with candidate A receiving a votes and candidate B re...

## Given a sequence of number, generate the lexicographically next permutation

Lexicographical order basically means dictionary order. A sequence is said to be lexicographically larger than another sequence, if it'll appear later in a dictionary. Eg, the following list is lexicographically sorted - ABC, ACB, BAC, BCA, CAB, CBA   Now, consider a sequence int a[] = {1,5,3,8,7,5,4,2}; By some trail and error, we can conclude tha...

## Find repeated Words Count in a String

This is a very common question where you have to find duplicate word in a given string. Let’s say you have a string This is a String with some duplicate words in it. duplicate words are printed with count by this program. Algorithm: We will first split the words withe “ ” (blank space) as a delimiter as in a sentence each word is separated by a spa...

## Find Longest Palindrome in sub string

Given a string, find the longest substring which is palindrome. For example, if the given string is “abacdfgdcaba”, the output should be “aba”. Logic:  One by one consider every character as center point of even and length palindromes For loop. Find the longest even length palindrome with center points as i-1 and i. (First While Loop). Find the lon...

## Find Character Count In a Given String

Here in this post we will find the count of each character in a given String. Lets Say for a given String “tuturself” the output should be the count of each word r=1, s=1, t=2, u=2, e=1, f=1, l=1 Now let us check the code for this: package com.tuturself.programs; import java.util.HashMap; import java.util.Map; public class CharacterCountIn...

## Given a set of elements now we need to print its powerset

Wikipedia defines powerset as the set of all subsets of S, including the empty set and S itself . Put simply, if the set S is as follows S = {1,2,3,4} Then Its powerset P = { {1},{2},{3},{4},{2,3},{2,4},{3,4},{1,3},{1,4},{1,2},{1,3,4},{1,2,3},{1,2,4},{2,3,4},{1,2,3,4},{empty} } Note that this contains the set itself as well as the empty set. Also n...

## Given a set of random strings, write a function that returns a set that groups all the anagrams together.

Anagram is a form of word play in which letters of a word are rearranged in such a way that a new word is formed. Consider we have a word rats now by rearranging the characters if we can get another word then the word will be an anagram of rats. Consider the following examples of anagram set: act, cat tab, bat tar, rat star,rats   Algorithm to solv...

## Write a function to convert an input string to an integer.OR write your own atoi function.

The atoi  function defined in stdlib.h in C converts a String to an int. The declaration of atoi( ) is as following : int atoi(const char *str); Here we are going to write our own atoi() implementation in Java. Remember in Java you convert a string to an integer using the parseInt method of the Java Integer class. The parseInt method converts the...

## How to Check Whether a Number is Palindrome or Not

Here we need to check if the given number is a Palindrome or not. We just need to reverses the digits of the input number using a loop. Then, if the resulting reversed number is equal to the input number , then it is a Palindrome otherwise not. The following is an example of a Palindrome number. Algorithm: 1. Loop until the input number become 0....

## Calculate GCD (Greatest common divisor) of 2 numbers recursively.

In mathematics, the greatest common divisor (gcd) of two positive numbers, when at least one of them is not zero, is the largest positive integer that is a divisor of both numbers. For example :  The GCD of 8 and 12 is 4. The GCD of 0 and 7 is 7. Now we need to calculate the GCD of 2 numbers recursively. Consider we have 2 numbers as input m,n. Fin...

## How to Swap Two Numbers without Temp or Third variable in Java?

How to swap two numbers without using a third variable is very common interview question. It can be asked in a campus interview or even for a Senior position. This question was first asked to me in my college days. When I was well prepared with all the approaches. But surprisingly again I faced the same question on an interview when I was 5 – 6 yea...

## What is a graph data structure and what are its uses?

Definition: A graph is a data structure that has nodes and vertices. The nodes are connected to each other via vertices. A graph can be a weighted graph or unweighted one. Also, it can be directed or undirected. We will discuss the types of graphs in coming posts.  Uses of a graph: Graphs are used for many practical applications in computer science...

## Graph representation – How do you represent a graph as an adjacency matrix?

In this post, we are going to cover how to represent a graph as an adjacency matrix. An adjacency matrix defines which nodes are connected in a graph in form of a 2D array. The size of the array is n*n, where n is the number of vertices in a graph.    Consider the graph shown above. It has got 6 vertices and thus its adjacency matrix will have 6*6 ...

## Graph representation – How do you represent a graph as an adjacency list?

In this post, we are going to study how to represent a graph as an adjacency list. An adjacency list is an array of the linked list. Each element of the array has a linked list associated with it, which contains the vertices adjacent to the vertex at the index of the array. Observe the above representation of the graph as an adjacency list. Each of...

## How would you implement a binary search?

When searching through a list, unless the list is sorted in some fashion, the only sure way to find a given value is to look at every value in the list. But if you are given a sorted list, or if you sort the list before searching, a binary search is a very efficient method to see if a given value is in the list : method binarySearch(list l, eleme...