More than a Pathshala
What is the best case, average case and worst case time complexity of Insertion sort?
The best case, average case and worst case time complexity of Insertion sort is listed below:
Best Case | Average Case | Worst Case | |
Insertion Sort | O(n) | O(n^{2}) | O(n^{2}) |
When insertion sort will have best case time complexity?
The best case in insertion sort algorithm will occur when the given list of element is in sorted order. During each iteration, the first remaining element of the input is only compared with the elements of the sorted subsection of the array. Hence, the best case time complexity of insertion sort is O(n)
How will you check whether given binary tree is balanced or not?
A binary tree is said to be balanced if the difference between the depth of the left and right subtrees of every node is not greater than one.
For example:-
In above example, the maximum difference between the depth of left subtree and right subtree of any node is not greater than 1. Hence above tree is balanced binary tree.
Given a string, you have to reverse the words inside it. Example "This is cool question" –> "question cool is This". Design an algorithm and implement it. You are not allowed to use String.Split()
method.
You can achieve the solution using below steps:
noitseuq looc si sihT
question cool is This
What is difference between height and depth of tree?
Depth: The depth of any node is the number of edges from the node to the tree's root node. A root node will have a depth of 0.
Height: The height of any node is the number of edges on the longest downward path between that node and a leaf. A leaf node will have a height of 0.
For a given tree of node "n", what will be the number of possible trees that can be formed?
The possible number of trees that can be formed of node "n" = 2^{n} - n
Let S be a set of n integers. One can create a data structure for S so that determining whether an integer x belongs to S can be performed in O(1) time in the worst case. What will be the data structure?
Using Perfect Hashing
the above requirement can be achieved.