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.