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.



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.


Number Range Spinner is Angular JS directive which is used for incrementing-decrementing integer/decimal value using button   

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.

 


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,

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 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 a given two Binary Trees are Mirror Image of each other.


How to determine a given two Binary Trees are Mirror Image of each other?



Two Binary Trees are considered mirror image of each other if there left and right child of every node is inter-exchange. (Left child moved to Right and Right chile moved to Left)

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



Determine if Two Binary Trees are identical.


How to determine if two Binary Trees are Identical?



Two Binary Trees are considered equal if they are structurally identical and the nodes have the same value.
 

See below image for better understanding of which Trees are called Identical and which 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?



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.


Largest 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.

Delete a node in Binary Search Tree.

How to delete a Node in Binary Search Tree?


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.

Binary Tree Traversals - Inorder, Preorder, Postorder, Levelorder

What is Binary Tree Traversal?


From Wiki: 
In computer science, Graph traversal is the problem of visiting all the nodes of a graph in a particular manner, updating and/or checking their values along the way.  Tree traversal is a special case of graph traversal. 

Binary Search Tree sample:


There are 2 types of Graph traversal algorithms Breadth first traversal and Depth First traversal. Tree is a special kind of Graph in which Breadth first traversal and Depth First traversal is divided as follows,

1. Breadth First Traversal 
  1. Level Order Traversal
2. Depth First Traversal
  1. Preorder traversal
  2. Inorder traversal
  3. Postorder 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.

So start scanning a Binary Tree level by level and wherever we encounter vacant position, place a new Node there.

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.


Print all combinations/permutations of a string of length k that can be formed from a set of n characters

Find all n length Permutation of a given String.
OR
Print all possible strings 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

Case 1  
  Input: string=AB and length=2
  Output:
    AA
    AB
    BA
    BB
   
Case 2
   Input: string=ABC and length=2
   Output:
    AA
    AB
    AC
    BA
    BB
    BC
    CA
    CB
    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
  
    done.
  

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

package backtracking;

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);
  }
 }
 
}


You may also like to see


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.

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

Given a string of length n, print all permutation of the given string without Repetition . (Repetition of characters is NOT allowed)

   Case 1
      Input:   A
      output: A
     
  Case 2
      Input: AB
      output:
                AB
                BA
               
  Case 3
      Input:  ABC
      output:
                ABC
                ACB
                BAC
                BCA
                CAB
                CBA
 

Algorithm:


  
How many permutations is possible?

  Lets see how many permutation is possible for given n character String.
  In string "AB", n is 2
  In string "ABC", n is 3
  From above permutations displayed, we can see relation as n!.
  So for "AB", total permutations are 2! = 2.
  For "ABC", total permutations are 3! = 6.

How to print all permutation?

  It is very easy, Lets take an example of String "ABC"
 
  We will take recursive approach. In this approach important thing is 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 and removing the same character one by one 
  from original string. As we are removing one by one character from original string and adding it to "permutation" string,   So it is sure at one point length of original String will be 0 and length of 
"permutation" string will be 3.
 
  So base case is, when the length of our original string became 0, we will print the string  "permutation" and return.
 
  Now, how we will form "permutation" string is, 
       remove first character of original string and add it to "permutation" string and check the 
       length of original string which is not 0, true, so call function again,
       "string" = "BC" "permutation" = "A"
     
       remove first character of original string and add it to "permutation" string and check the 
       length of original string which is not 0, true, so call function again,
       "string" = "C" "permutation" = "AB"
     
      remove remaining character of original string and add it to "permutation" string and check the 
      length of original string which is not 0, false, so it is time to print the string "permutation".
      "string" = "" "permutation" = "ABC"
     
      1st permutation is ABC
      after returning from printing 1st permutation,
      "string" = "C" "permutation" = "AB" 
              Original string has only one character "C" whose permutation is covered, 
              no more permutation possible of one character string, so return,
      "string" = "BC" "permutation" = "A"
               From original string "ABC", we covered permutation keeping 
              "A", "B" at place and changing "C", which gave "ABC" as 1st permutation.
               Now, its time to work on 2nd character of original string

       Now,
       remove second character of original string and add it to "permutation" string and check the 
       length of original string which is not 0, true, so call function again,
       "string" = "B" "permutation" = "AC"
     
      remove remaining character of original string and add it to "permutation" string and check the 
      length of original string which is not 0, false, so it is time to print the string "permutation".
      "string" = "" "permutation" = "ACB"
     
      if we continue the same process in a loop, then we will get all our permutations 
      without repetition of characters.

Program to print all permutations of a string in Java

package backtracking;

public class StringPermutationWithoutRepetition {
 
 public static void main(String[] args) {
  permutation("ABC");
 }
 
 private static void permutation(String string) {
  printPermutation(string,"");
 }

 private static void printPermutation(String string, String permutation) {
  
  if(string.length()==0){
   System.out.println(permutation);
   return;
  }
  
  for (int i = 0; i < string.length(); i++) {
   char toAppendToPermutation = string.charAt(i);
   String remaining = string.substring(0, i) + string.substring(i + 1);
   
   printPermutation( remaining,  permutation + toAppendToPermutation);
  }  
 }

}

Time Complexity:


Time complexity of program to print all permutations of a string is O(n*n!).

How it comes to (n * n!)

From the above stack trace picture of a program you can see, for printing permutation of string "ABC" i.e. 3 character word, what it does is 

Outer:
Keeping A at place, it finds all the permutations of remaining string, then,
          Inner:
          Keeping B at place, it finds all the permutations of remaining string, then,
                     keeping C at place, it finds all the permutations of remaining string, then,
          Change B to C and find all the permutations of remaining string, then, 
                     ...........
           ...............             
Keeping B at place, it finds all the permutations of remaining string, then,
           ...........
           ...........
Keeping C at place, it finds all the permutations of remaining string.

How many times Outer: label has to print is number of characters present in word.
that is n
How many times Inner: label has to print is number of permutations of a character present in word.
this brings n!
 
Now, if we read this line again,
Keeping Outer character at place, find all permutation of Inner sting, then replace 
Outer character at place, and again find all permutation of Inner sting, and 
so on till end of Outer character.

hence the complexity is O(n * n! )

You may also like to see


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

Print all combinations/permutations of a string of length k that can be formed from a set of n characters.

Print all subsets of a given set.



Enjoy !!!!

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

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

Given a string of length n, print all permutation of the given string. Repetition of characters is allowed

   Case 1
      Input:   A
      output: A
     
  Case 2
      Input: AB
      output:
                AA
                AB
                BA
                BB
               
  Case 3
      Input:  ABC
      output:
                AAA
                AAB
                AAC
                ABA
                ABB
                ABC
                ACA
                ACB
                ACC
                BAA
                BAB
                BAC
                BBA
                BBB
                BBC
                BCA
                BCB
                BCC
                CAA
                CAB
                CAC
                CBA
                CBB
                CBC
                CCA
                CCB
                CCC
 

Algorithm:


  
How many permutations is possible?

  Lets see how many permutation is possible for given n character String.
  In string "AB", n is 2
  In string "ABC", n is 3
  From above permutations displayed, we can see relation as n^n.
  So for "AB", total permutations are 2^2 = 4.
  For "ABC", total permutations are 3^3 = 27. How to print all permutation?

  It is very easy, Lets take an example of String "ABC"
 
  We will take recursive approach. In this approach important thing is base case.
  We will try to make each permutation by adding characters one by one to the temporary String 
  that need to be printed.
 
  As our string is of length 3, so we will add the characters to the temporary string that needs 
  to be printed till the length is 3 as permutation string length will be 3.
 
  So base case is, when the length of our temporary string that needs to be printed is 3, 
  print and return.
 
  Now, how we will form temporary string is, 
       add first character of string to temporary string and check the length of 
       temporary string which is less then 3, true, so call function again,
       tempString = "A"
     
      add first character of string to temporary string and check the length of
      temporary string which is less then 3, true, so call function again,
      tempString = "AA"
     
      add first character of string to temporary string and check the length of
      temporary string which is less then 3, false, so print and return
      tempString = "AAA"
     
      1st permutation is AAA
      after returning from printing 1st permutation, tempString will be again "AA"
     
      Now appending "B" to "AA" will make our 2nd permutation that is "AAB", print and return.
      Now appending "C" to "AA" will make our 3rd permutation that is "AAC", print and return.
     
      from this we can see, that keeping "AA" common and adding "A", "B", "C" that is 
      each character of String, we are getting permutation.
      if we continue the same for 2nd position and then for 1st position of temporary string then 
      we will get all our permutations.


Java Program to print permutation of string with repetition

package backtracking;

public class StringPermutationWithRepetition {

 public static void main(String[] args) {
  printPermutationOfStrings("ABC");
 }
 
 private static void printPermutationOfStrings(String str){
  printPermutation(str, "");
 }
 
 private static void printPermutation(String str, String stringToPrint){
  if(stringToPrint.length()==str.length()){
   System.out.println(stringToPrint);
   return;
  }
  for (int i = 0; i < str.length(); i++) {
   printPermutation(str, stringToPrint + str.charAt(i));
  }
 }
}


You may also like to see


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

Print all combinations/permutations of a string of length k that can be formed from a set of n characters.

Print all subsets of a given set.



Enjoy !!!! 

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