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

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]]

SolutionThere 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, 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.

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

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 awareof,

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)?

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.

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,

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.

I'm Jayesh Patel, author of "JavaByPatel". I'm not a professional blogger but when time permits, love to share in-depth solutions to common Interview questions asked. Any questions/feedback, Please drop a mail at jayeshmaheshpatel@gmail.com