Sort Linked list using Merge sort.

Sort Linked List using Merge Sort.


Given a Linked list, Sort it using Merge Sort Algorithm.

Merge sort is preferred algorithm for sorting a linked list, lets see why,
The way linked list is structured which doesn't allow random access makes some other algorithms like Quicksort perform poorly, So Merge sort is often preferred algorithm for sorting linked list.
 
Lets understand what is the input and the expected output.


Tower Of Hanoi

Tower Of Hanoi


Lets understand what is the input and the expected output.

So the question is, You have given a 3 Peg (Start peg, Auxiliary/helper peg and End Peg)
Start peg contains 3 disks of different sizes as shown. You have to move all the disk from Start peg to End peg using Auxiliary peg.


There are few rules that need to keep in mind,

1. Only one disk can be moved at a time.
2. Large size disk can't be placed on top of small sized disk.

Find Nth node from last in a linked list


Find Nth node from last in a linked list


Lets understand what is the input and the expected output.


Find middle element of the Linked list

Reverse a Linked list

Reverse a Linked list


Lets understand what is the input and the expected output.

Detect loop in linked list.

Detect loop in Linked list.
Identify start node of loop in Linked list.
Remove loop in Linked list.


What is Loop in Linked list?

Generally, the last node of the linked list points to NULL, which is a indication of end of list.
But in Linked list containing Loop, last node instead of pointing NULL, it points to some of the internal node/starting node/itself.
In this case, If we traverse the Linked list node one by one, our traversal will never ends as it goes in loop.

Check below images for better understanding on how Linked list containing loop looks like.



Number Range Spinner in Angular JS

Number Range Spinner.



Diameter of Binary Tree.

Find diameter of Binary Tree.


What is Diameter of a Binary Tree?

A longest path or route between any two nodes in a tree is called as Diameter/Width of binary tree.
The diameter of tree may or may not pass through the root.
The diagram below shows two trees each with diameter 7, diameter are shaded with blue nodes.

Diameter of node = height of Left sub tree of node + height of Right sub tree of node + 1 (node itself).

Find Kth largest element in BST(Binary Search Tree)

Find Kth largest element in Binary Search Tree.


Lets understand the problem statement correctly, What is the Input and the expected output.


Find Kth smallest element in BST(Binary Search Tree)

Find Kth smallest element in Binary Search Tree.


Lets understand the problem statement correctly, What is the Input and the expected output.


Heap Sort Algorithm

Heap Sort.


Before looking into Heap Sort, let's understand what is Heap and how it helps in sorting.

What is Complete Binary Tree?

A Complete binary tree is a binary tree in which every node other than the leaves has two children. In complete binary tree at every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Let's understand with simple words now,
If a Binary Tree is filled level by level, left to right (Left child followed by Right child.) then it is called complete binary tree.
If Right child is present without Left child then it is not complete.



Check If two strings are Anagrams.

Check 2 strings are anagrams of each other.


What is Anagram?

An anagram is a rearrangement of the letters of one word or phrase to another word or phrase, using all the original letters exactly once.

Example:
1. "evil" and "vile" is anagram of each other
2.
"dog" and "ogd" is anagram of each other
3. "burger" and "burgr" is not a anagram of each other

Find all subsets of a set (Power Set)

Print power set of any given set OR Print all subsets of a set OR
Find all subsets of a set OR Print all subset of an array.


Given a set of numbers, print all the possible subsets of it including empty set.

What is Power Set?

In mathematics, the power set (or powerset) of any set S, written P(S), is the set of all subsets of S, including the empty set and S itself.

Let's understand it with help of example.
Case 1:
Input:    Set(S)              = [1,2]
Output: PowerSet P(S) = [[ ], [2], [1], [2, 1]]

Case 2:
Input:    Set(S)              = [a,b,c]
Output: PowerSet P(S) = [[ ], [a], [b], [c], [a,b], [a, c], [b, c], [a, b, c]]

Solution


There can be many approach to solve this problem, here we will look at 2 simple approaches.
1. Using Tree representation approach.
2. Using Bit manipulation approach.

Tree Representation Approach


In this approach, we will draw a Tree like shown below,


Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

Word Ladder ( Doublets / Word-links / Word golf )


Given two words, startWord and endWord, and a dictionary, find the length of shortest transformation sequence from startWord to endWord.
Rules:

1. Only one letter can be changed at a time.
2. Each intermediate word must exist in the dictionary.

Input
startWord     = CAT
endWord      = DOG
dictionary    = CAT, BAT, COT, COG, COW, RAT, BUT, CUT, DOG, WEB

Output

One shortest transformation is CAT –> COT –> COG –> DOG.
the program should return Path and its length 4.


Let's look at few more example and better understand problem statement.

There can be many paths for reaching from startWord to endWord, but we have to find shortest path possible.

Print Nodes in Bottom View of Binary Tree.


Print the bottom view of Binary Tree



Given a binary tree, print the nodes that is visible, when the tree is viewed from the bottom.


Let us first understand what we want to achieve? what is the input and what will be the expected output?


Bottom view means, when we look the tree from the bottom, the nodes that are visible will be called the bottom view of the tree. So in the above image,

Print Nodes in Top View of Binary Tree


Print the top view of Binary Tree



Given a binary tree, print the nodes that is visible, when the tree is viewed from the top.

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Top view means, when we look the tree from the top, the nodes that are visible will be called the top view of the tree. So in the above image,

Print a Binary Tree in Vertical Order. Find Vertical Sum of given Binary Tree.

Print Binary Tree in Vertical Order OR
Print the Binary Tree in Vertical Order Path OR
Vertical order traversal of a Binary Tree.
Find Vertical Sum of given Binary Tree


Given a binary tree, print it vertically.

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Note:
Vertical order traversal of Tree shown above will be 
Print data present at Line 1 ( 4 )
Print data present at Line 2 ( 2 )
Print data present at Line 3 ( 1, 5, 6 )
Print data present at Line 4 ( 3 )
Print data present at Line 5 ( 7 )

What is Load factor and Rehashing in Hashmap?

What is Load factor and Rehashing in Hashmap?


This is the famous interview question for experienced, So Let's see what it is all about.

Hashmap is very popular data structure and found useful for solving many problems due to O(1) time complexity for both get and put operation.
Before understanding Load Factor and Rehashing, It is important to understand below articles,
So please go through it if you are not aware of,


What is Hashmap & How hashmap API works?
What is Hashcode and How hashmap uses it? 
How time complexity of Hashmap Put and Get operation is O(1)?

Load Factor


When the total number of items in hashmap goes on increasing keeping the default initial capacity of hashmap 16, At one point of time, hashmap performance will start degrading and need to increase buckets for improving performance.

Load Factor is a measure, which decides when exactly to increase the hashmap capacity(buckets) to maintain get and put operation complexity of O(1).
Default load factor of Hashmap is 0.75f (i.e 75% of current map size).
You can also say, load factor is a measure "Till what load, hashmap can allow elements to put in it before its capacity is automatically increased"

Above line will make more sense with the help of an example,
Default capacity of Hashmap is 2^4 = 16 buckets.
Let say we have well implemented hashcode() method, which make sure that key-value pair will be well distributed across 16 buckets equally.

So, If there are 16 items in hashmap, then good hashcode method will distribute 1 item in each bucket. Searching for any item in this case will take only 1 look up.

Now, If there are 32 items in hashmap, then good hashcode method will distribute 2 item in each bucket. Searching for any item in this case will take maximum 2 look up.

Now, If there are 128 items in hashmap, then good hashcode method will distribute 8 item in each bucket. Searching for any item in this case will take maximum 8 look up.

If you observe, If the number of items in hashmap is doubled, still the maximum look up time in each bucket is not increasing very high and remain almost constant.

If say, the number of items goes on increasing in the map, then what will happen?
If the amount of item keeps on increasing and the number of buckets are fixed(16) then at one time, performance of hashmap will start degrading due to large number of items in each bucket.
hashmap capacity and load factor relation
Hashmap capacity and load factor relation

How time complexity of Hashmap get() and put() operation is O(1)? Is it O(1) in any condition?

How time complexity of Hashmap get() and put() operation is O(1)?


This is the famous interview question for the beginners as well as for experienced, So Let's see what it is all about.

Hashmap is very popular data structure and found useful for solving many problems due to O(1) time complexity for both get and put operation.
Before getting into Hashmap internals, Please read Hashmap basics and Hashcode.

Time complexity of Hashmap get() and put() operation.


For detail explanation on hashmap get and put API, Please read this post How Hashmap put and get API works.

Hashmap works on principle of hashing and internally uses hashcode as a base, for storing key-value pair.
With the help of hashcode, Hashmap distribute the objects across the buckets in such a way that hashmap put the objects and retrieve it in constant time O(1).


Before looking into Hashmap complexity, Please read about Hashcode in details.

Let's understand time complexity with the help of an example,
how hashmap works internally in java with example


From the above example, it is clear that, put operation in hashmap requires,

How Hashmap data structure works internally? How hashcode and equals method work in hashmap? Explain with real time example.

Hashmap data structure works internally?
How hashcode and equals method work in hashmap?


This is the famous interview question for the beginners as well as for experienced, So Let's see what it is all about.

Hashmap is very popular data structure and found useful for solving many problems due to O(1) time complexity for both get and put operation.
Before getting into Hashmap internals, Please read Hashmap basics and Hashcode.

Internal working of Get and Put operation.


Hashmap store objects in key-value pair in a table.
  1. Objects are stored by method hashmap.put(key, value) and


  2. Objects are retrieved by calling hashmap.get(key) method.
For detail explanation on hashmap get and put API, Please read this post How Hashmap put and get API works.

Put Operation


Hashmap works on principle of hashing and internally uses hashcode as a base, for storing key-value pair.
With the help of hashcode, Hashmap stores objects and retrieves it in constant time O(1).


Lets recap "Employee Letter Box" example, we saw in last post on Hashcode.


What is Hashmap data structure? What is the need of Hashmap? How Hashmap data structure API works in Java? What is Hashcode? Can 2 objects have same hashcode?

What is Hashmap data structure?
What is the need of Hashmap?
How
Hashmap data structure API works in Java?
What is Hashcode?
Can 2 objects have same hashcode?


This is the famous interview question for the beginners as well as for experienced, So Let's see what it is all about. Hashmap is very popular data structure and found useful for solving many problems due to O(1) time complexity for both get and put operation.

What is the need of Hashmap data structure? What problem it solves?


When we have many objects and if we want to search a particular object among them, 
How to search??
(Say we have 100 Student object and we want to search Student having Roll No. 35, how to do?)

We pick one object and see, this is the object we are looking for? No. 

Pick next object and check again. Repeat the steps until we found the object.
Imagine the time it will take???


The time it will take to search a particular object will be even high if total objects are more.
This is where hashmap will come in picture.

Hashmap arranges the objects in such a way, that searching any object in hashmap will be done in almost O(1) complexity.
How arranging items in particular way can make searching faster. Lets see with example,

Ms. Khyati is working for XYZ Computers in Bangalore and for work assignment she has to relocate to Pune for 1 month.
Khyati noted down important house items to carry for 1 month and started packing like shown below,

She packed all items randomly in 2 boxes.


How PreparedStatement in Java prevents SQL Injection?

What is PreparedStatement in java?
Why use PreparedStatement in Java JDBC?
How prepared statement prevents SQL Injection?
Difference between Statement and PreparedStatement in Java?


This is the famous interview question for the beginners, So Let's see what it is all about.

SQL Injection is code injection technique where SQL is injected by user (as part of user input) into the back end query, and ultimately changes query purpose which upon execution gives harmful result.

Detailed explanation on SQL Injection: What is SQL Injection?


How can SQL Injection happen.


At server side, queries generally by themselves are not complete and require user data to make it complete, meaningful and executable.
"select * from user where username = ' " + username + " ' ";
Above query is not complete as it has dependency on username variable.

Now if username variable is filled by third party, then there are chances that user data contains SQL,

Take an example. Application is asking user to enter user name,
Enter user name:________________________

Enter user name:___jayesh'; delete from user where id='1__

At Server Side,

username = "jayesh'; delete from user where id='1"
Final Query = "select * from user where username = ' jayesh'; delete from user where id='1 ' ";

If you observe final query, upon execution it will delete the record from user table which was never the purpose of original query and this is called SQL Injection attack. 

Because of user data (which can be anything and uncontrolled) involvement in formation of query, SQL Injection attack can happen.

Detailed explanation on: How can SQL Injection happen?

How PreparedStatement in Java prevents SQL Injection?


To understand this, Lets see steps involved in query execution.
1. Compilation Phase.

2. Execution Phase.

Whenever SQL server engine receives a query, It has to pass through below phases,

What is SQL Injection?

Explain SQL Injection along with example?


This is the famous interview question for the beginners, So Let's see what it is all about.

SQL Injection is code injection technique where SQL is injected by user (as part of user input) into the back end query. Injected SQL data alters the purpose of original query and upon execution can gives harmful result.

A SQL injection attack is very dangerous and attacker can,

  1. Read sensitive data from the database.
  2. Update database data (Insert/Update/Delete).
  3. Slowdown the complete Database system etc.

Boundary Traversal of Binary Tree.

Boundary Traversal of binary tree OR
Print Circumference of Binary Tree OR
Given a Binary Tree, Print its Perimeter OR
Print outside nodes of Binary Tree OR
Print Edge nodes of Binary Tree OR

Print Boundary of Binary Tree.


We have to print the boundary nodes of given Binary Tree in anti-clockwise starting from the root.

Let us first understand what we want to achieve? what is the input and what will be the expected output?


Zig Zag Traversal of Binary Tree.

Level order traversal in spiral form OR
Printing a Binary Tree in Zig Zag Level-Order OR
Print a binary tree in Zig Zag way.


Given a binary tree, write a program to print nodes of the tree in spiral order. You can also say it as Spiral order traversal of a tree. Let us first understand what we want to achieve? what is the input and what will be the expected output?
 

N Queens puzzle Optimized.

The N Queen is the problem of placing N Chess queens on an N×N chessboard so that no two queens attack each other.


Let us first understand what we want to achieve? what is the input and what will be the expected output?

You are given a chess board of N * N size, you have to place N Queens in chess board in such a way that no queens are attacking each other.

Sample Input and output for 4 * 4 chess board



Remember, Queens attacks on same row, on same column as well as diagonally.


N Queens Puzzle.

The N Queen is the problem of placing N Chess queens on an N×N chessboard so that no two queens attack each other.


Let us first understand what we want to achieve? what is the input and what will be the expected output?

You are given a chess board of N * N size, you have to place N Queens in chess board in such a way that no queens are attacking each other.

Sample Input and output for 4 * 4 chess board


Remember, Queens attacks on same row, on same column as well as diagonally.

Find the element that appears once others appears THRICE.

Find the element that appears once others appears THRICE.


Given an array of integers. All numbers occur thrice except one number which occurs once. Find the number in O(n) time & constant extra space.

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
Input: {17, 10, 17, 2, 17, 10, 10, 4, 4, 4}
Output: 2

Input: {17}
Output: 17

Input: {17, 17, 17, 2}


Output: 2

Algorithm


This problem can be solved in multiple ways but solution might not fulfill time and space complexity constraints given in problem statement.
Time complexity to solve this problem should not be greater then O(n)
Space complexity to solve this problem should not be greater then O(1)
Bit Manipulation will be helpful in this situation.

Before proceeding further lets just see XOR operation and facts.

Find the element that appears once others appears TWICE.

Find the element that appears once others appears TWICE.


Given an array of integers. All numbers occur twice except one number which occurs once. Find the number in O(n) time & constant extra space.

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
Input: {2, 3, 5, 4, 5, 3, 4}
Output: 2

Input: {2}
Output: 2

Input: {2,1,2}
Output: 1

Algorithm


This problem can be solved in multiple ways but solution might not fulfill time and space complexity constraints given in problem statement.
Time complexity to solve this problem should not be greater then O(n)
Space complexity to solve this problem should not be greater then O(1)
Bit Manipulation will be helpful in this situation.

Before proceeding further lets just see XOR operation and facts.

Construct a Binary Tree from In-order and Pre-order traversals.

How to construct a Binary Tree from given In order and Pre order traversals.


Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
Two traversals are given as input,
  int inorder[] =  {20, 30, 35, 40, 45, 50, 55, 60, 70};
  int preorder[] = {50, 40, 30, 20, 35, 45, 60, 55, 70};
By using above 2 given In order and Pre Order traversal, construct Binary Tree like shown below,


Construct a Binary Tree from In-order and Level-order traversals.

How to construct a Binary Tree from given In order and Level order traversals.


Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
Two traversals are given as input,
        int[] inOrder =    { 4, 2, 6, 5, 7, 1, 3 };
        int[] levelOrder = { 1, 2, 3, 4, 5, 6, 7 };

By using above 2 given In order and Level Order traversal, construct Binary Tree like shown below,



Connect nodes at same level in a binary tree using constant extra space.

How to connect nodes at same level using constant extra space? OR
Populate next right pointers for each Tree Node? OR
Connect nodes of a binary tree at same Level?


Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
 Binary Tree is given to you, 
  1. some node of  tree has both left and right child present,
  2. some node of tree has only left child present and
  3. some node of tree has only right child present, 
  4. nextRight pointer of all the node initially is null.  
Our task is to connect nextRight pointer of each node to its adjacent node. 
  1. If the immediate adjacent node is not present then connect to next adjacent node and 
  2. If next adjacent node is not present then connect to next to next adjacent node and 
  3. If next to next adjacent node is not present then search until you find the adjacent node along the same Level and connect to it.
  4. If the adjacent node is not present at same level then connect it to null.
See below image for better understanding the problem statement.


Connect nodes at same level in a Binary Tree.

How to connect nodes at same level using Queue? OR
Populate next right pointers for each Tree Node? OR
Connect nodes of a binary tree at same Level?


Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
 Binary Tree is given to you,
  1. some node of  tree has both left and right child present,
  2. some node of tree has only left child present and
  3. some node of tree has only right child present, 
  4. nextRight pointer of all the node initially is null. 
Our task is to connect nextRight pointer of each node to its adjacent node.  
  1. If the immediate adjacent node is not present then connect to next adjacent node and 
  2. If next adjacent node is not present then connect to next to next adjacent node and 
  3. If next to next adjacent node is not present then search until you find the adjacent node along the same Level and connect to it.
  4. If the adjacent node is not present at same level then connect it to null. 


Structure of the given Binary Tree Node is like following:
package javabypatel.tree;

class Node{
 private int data;
 private Node left;
 private Node right;
 private Node nextRight;  <---- New pointer introduced to connect to adjacent Node.
}


See below image for better understanding the problem statement.


Check if two trees are mirror images of each other

How to check if two binary trees are mirror images of each other?


In this post we will look at algorithm to check if two trees are mirror images of each other with Java program.

See below image for better understanding of which Trees are called Mirror Image of each other

check if two trees are mirror images
Check if two trees are mirror images of each other

Check if two binary trees are identical

Check if two binary trees are identical or not?


In this post we will check if given binary trees are identical or not using recursive approach.
 
See below image for better understanding of which Trees are called Identical and which not.
check if two binary trees are identical or not in Java
Check if two binary trees are identical or not

Binary Search Tree Operations ( Add a node in Binary Search Tree, Search a node in Binary Search Tree ).

How to Add a Node and Search a Node in Binary Search Tree?


Let's see how to insert a node in binary search tree (BST) and search a node in binary search tree.

What is Binary Search Tree?
In computer science, Binary Search Trees (BST), sometimes called Ordered or sorted binary trees, are a particular type of containers: data structures that store "items" (such as numbers, names and etc.) in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key (e.g., finding the phone number of a person by name).
More: https://en.wikipedia.org/wiki/Binary_search_tree


While adding a Node in a Binary Search Tree, it should follow below rules,
  1. All values descending on the Left side of a node should be less than (or equal to) the node itself. 
  2. All values descending on the Right side of a node should be greater than (or equal to) the node itself.
If Tree follows above protocol for all the Nodes of a tree, then Tree is called a Binary Search Tree. See below image to get better understanding of Binary Search Tree rules.
add a node in binary search tree in java
Insert node in binary search tree in Java

Maximum Sum Contiguous Subarray using Kadane's algorithm.

Find the maximum-sum subarray of an array. OR
Explain Kadane's Algorithm to solve the Maximum Sum Subarray OR
Find Largest Sum Contiguous Subarray.

The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.
max sum contiguous subarray in java
Max sum contiguous subarray solution

Delete a node in Binary Search Tree in Java

How to delete a Node in Binary Search Tree in Java?


Let's see how to delete a node in binary search tree with example and java program. 

There are 3 cases that need to be considered while deleting a node from Binary Search Tree.
  1. Node to delete has no children that is no left child and no right child present. Case 1 in below image. 
  2. Node to delete has only one child either left child or right child present. Case 2 in below image.
  3. Node to delete has both child that is left child and right child present. Case 3 in below image.
delete a node in binary search tree
Delete a node in binary search tree cases

Binary Tree Traversals - Inorder, Preorder, Postorder, Levelorder

What is Binary Tree Traversal?


Binary tree traversal is a way to read a tree by visiting each node in a particular manner. 
We will look into three popular binary tree traversal, Inorder, Preorder and Postorder along with example.

Note: Tree traversal (Inorder, Preorder and Postorder) are classified as a part of Graph traversal because Tree is a special kind of Graph.

There are mainly 2 types of Graph traversal algorithms Breadth first traversal and Depth First traversal and is divided as follows,
  1. Depth First Traversal
    1. Inorder traversal
    2. Preorder traversal
    3. Postorder traversal
  2. Breadth First Traversal
    1.  Level Order Traversal 

Add a node in Binary Tree and not a Binary Search Tree.

How to add a Node in Binary Tree and not a Binary Search Tree?


To add a Node in a Binary Tree, Let us first fix our protocol of how we are going a insert a node in Binary Tree.

Before going further, I would like to clear the difference between Binary Tree and Binary Search Tree, you are welcome to skip this part if you are already aware of,

Binary Tree: A tree is called Binary Tree if each node of tree has no more than 2 child node.
sample binary tree
Binary Tree Example
If you want to look at popular Binary tree traversals, 

Binary Search Tree: It is a special type of Binary Tree where it follow below rules,
  1. Nodes on left subtree must have value less than the parent node.
  2. Nodes on right subtree must have value greater than the parent node.
binary search tree example
Sample Binary Search Tree

How to add a Node in Binary Tree:

For adding a node in Binary tree we just need to make sure we are not breaking the rule of Binary tree that is, "each node of tree has no more than 2 child node".

So to add a node, we will start scanning a Binary Tree level by level and wherever we encounter a Node which has no child node or has only one child node, that would be our target node to insert a new Node

See below image to get better understanding of position of a new Node to insert. Given a binary tree, we need to add a Node with value 8 marked in dotted lines below in its correct position.
add a node in binary tree algorithm
Add a node in binary tree

Print all possible strings of length K that can be formed from a set of N characters in Java

Find all n length Permutation of a given String.
OR
Print all combinations/permutations of a string of length k that can be formed from a set of n characters. OR.
Print all possible combinations of k elements from a given string of size n

Print all possible strings of length K that can be formed from a set of N characters in Java. Lets see sample input and output below,

Case 1  
Input: string=AB and length=2
Output:

  1. AA
  2. AB
  3. BA
  4. BB
Case 2
Input: string=ABC and length=2
Output:

  1. AA
  2. AB
  3. AC
  4. BA
  5. BB
  6. BC
  7. CA
  8. CB
  9. CC  

Algorithm:


How many permutations is possible?

How many permutations is possible can be calculated using k^r where,
  k = length of unique characters to use.
  r = number of places to fill. 


In first example above, 
k=2(A,B), r=2(all permutations of length 2 is required) 
= 2^2 = 4 permutations possible.

In second example above, 

k=3(A,B,C), r=2(all permutations of length 2 is required)
3^2 = 9 permutations possible.
 

How to print all permutation?

It is very easy, Lets take an example of String "ABC" and we are told to generate permutations of length 3.    

using formula k^r we can see, 3^3 = 27 permutations possible.
We will take recursive approach i
n this approach important thing is base case.

Base Case: 

We will try to make each permutation by adding characters one by one to the temporary
string "permutation" that need to be printed.
We will add the characters to the string "permutation" until the length of it is 3 as we want to find permutations of length 3.
  
So base case is, when the length of our string "permutation" matches given length, 

we will print the string "permutation" and return.
 

Working:
  
Now, how we will form "permutation" string is,
we have string "ABC" and we want to find all permutation of it consisting of length 3.
  
How we can do is,

First lets see how many permutation possible of length 1 of given string "ABC".
Answer is 3.
     A
     B
     C

So we can see that if we fill our third position by keeping first 2 place common, filled by "A", 

and only changing last place to possible permutation of length 1, we will get 3 permutations.
    
     A A A
     A A B
     A A C
  
and now if we repeat the same, but this time we will change the second position and then again iterate over possible permutation of length 1, we will again get 3 permutations.
    
     A B A
     A B B
     A B C
  
and now if we repeat the same, but this time we will change the second position and then again iterate over possible permutation of length 1, we will again get 3 permutations.
  
     A C A
     A C B
     A C C
  
and now if we repeat the same, but this time we can't change the second position as we have covered second place for all possible characters "A", "B" and "C" keeping "A" at first place fixed.
 

So, Now it is the time to change the first place position which is till now covered only for "A".
So this time we will change the first place position to "B" and again we will repeat above steps.
  
    B A A
    B A B
    B A C
  
    then,
  
    B B A
    B B B
    B B C
  
    then,
  
    B C A
    B C B
    B C C
  
So, now it is the time to change the first place position which is till now covered only for 

"A" and "B".
We will change the first place position to "C" and again we will repeat above steps.

    C A A
    C A B
    C A C
  
    then,
  
    C B A
    C B B
    C B C
  
    then,
  
    C C A
    C C B
    C C C

Print all possible strings of length k that can be formed from a set of n characters
Stack trace of printing all possible strings of length K that can be formed from a set of N characters

Program to print all combinations of string of length k in Java

package javabypatel;

public class GenerateAllPermutationOfNBits {

 public static void main(String[] args) {
  permutation("ABC", "", 2);
  permutationOfBinaryNumbers("", 2);
 }
 
 private static void permutation(String str, String prefix, int lengthOfPermutationString){
  if(prefix.length()==lengthOfPermutationString){
   System.out.println(prefix);
  }else{
   for (int i = 0; i < str.length(); i++) {
    permutation(str, prefix + str.charAt(i), lengthOfPermutationString);
   }
  }
 }
 
 private static void permutationOfBinaryNumbers(String prefix, int lengthOfPermutationString){
  if(prefix.length()==lengthOfPermutationString){
   System.out.println(prefix);
  }else{
   permutationOfBinaryNumbers(prefix + "1", lengthOfPermutationString);
   permutationOfBinaryNumbers(prefix + "0", lengthOfPermutationString);
  }
 }
 
}

Another approach

package javabypatel;

import java.util.Arrays;

public class GenerateAllPermutationOfNBits {

    public void printCombination(int[] arr, int i, int lengthOfCombination, int combinationSet) {
        if (i == lengthOfCombination) {
            System.out.println(Arrays.toString(arr));
            return;
        }

        for (int j=0; j<combinationSet; j++) {
            arr[i] = j;
            printCombination(arr, i+1, lengthOfCombination, combinationSet);
        }
    }

    public void printCombinationOfGivenSet(char[] arr, int i, int lengthOfCombination, char[] combinationSet) {
        if (i == lengthOfCombination) {
            System.out.println(Arrays.toString(arr));
            return;
        }

        for (int j=0; j<combinationSet.length; j++) {
            arr[i] = combinationSet[j];
            printCombinationOfGivenSet(arr, i+1, lengthOfCombination, combinationSet);
        }
    }

    public static void main(String[] args) {
        GenerateAllPermutationOfNBits obj = new GenerateAllPermutationOfNBits();
        int lengthOfCombination = 2; //(length of the combination to generate)
        int combinationSet = 2;
        //(2 means use 0 and 1 while generating combination)
        //(3 means use 0, 1 and 2 while generating combination)

        obj.printCombination(new int[lengthOfCombination], 0, lengthOfCombination, combinationSet);

        System.out.println("Print from Given set...");
        char[] combinationSetArr = new char[]{'A', 'B', 'C'};
        obj.printCombinationOfGivenSet(new char[lengthOfCombination], 0, lengthOfCombination, combinationSetArr);
    }
}

Write a program to print all permutations of a given string without repetition. (Repetition of characters is not allowed).

Write a program to print all permutations of a given string with repetition. (Repetition of characters is allowed).

Print all subsets of a given set.


Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.