the complexity is O(n^2) . since each node is visi…
Unknown - May 1, 2013
the complexity is O(n^2) . since each node is visit multiple times as the traversal is top bottom and not bottom up.
Find Diameter of Binary Tree
So this question asks us to find Number of Nodes on the Longest Path in Binary Tree so one thing is sure that this path comprises on two leaves with maximum distance in BT..isn’t it
PS:Don’t confused with finding the maximum distance between two nodes in Binary Tree(as it doesn’t involves 2 leaves)
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.
[Read More]
Row consisting max continuous chain of 1’s in an n * n grid
Problem: Given an n * n grid consisting of only ZEROs and ONEs, such that if in a row a ZERO is present all elements to the right of it will be ZEROs. Thus, a row can start with ONEs and end in only ZEROs, there cannot be a mix and match. You need to find the row with maximum ONEs in a given row. For example in the grid below,
[Read More]
Leveling sectors in a circle
Problem : How to make the surface of the circular plot level in minimum number of moves
Detail:
The circular plot is divided into sectors. Each of these sectors has a level which is indicated by an integer. The sector can be either above the earth surface, in which case the integer is positive, or below the earth surface, when it will be negative. She can choose two consecutive sectors and increase the level of both the sectors by 1 at a time, which will be counted as one move.
[Read More]
Reverse the words in a sentence in place
Problem Given a sentence you have to reverse it word by word.
Example
That is, given a sentence like this :
I am a good boy
The in place reverse would be:
boy good a am I
Solutions Method1 - Reverse the sentence first and then words again
First reverse the whole string and then individually reverse the words
I am a good boy
<————->
yob doog a ma I
[Read More]
Find nth largest value in a BST
Hi there I was just going through your this post a… bakwasscoder - Jun 5, 2012Hi there
I was just going through your this post and had a small doubt.
Shouldn’t we do a stack based iterative traversal to get the correct value in this code ? This recursive may give wrong result as it will start counting after the rightmost element has been found. This element won’t be the nth largest in BST.
[Read More]
Find nth largest value in a BST
Simplest solution is to do a reverse in order search and maintain a global counter.
ReverseInOrder(Tree T, n)
1. if (T->right != null ) ReverseInOrder(T->right)
2. if (count==n) return T. Else count++
3. if (T->left != null ) ReverseInOrder(T->left)
Sorting a Stack using push,pop,isEmpty and peek
Problem Definition: Sort a Stack using standard operations push,pop,isEmpty and peek.
This question is asked in cracking the coding interview. Other ways of asking the question
Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that
should be used to write this program: push | pop | peek | isEmpty Note - peek is equivalent to top() function in java, where you dont pop out the element but peek and see.
[Read More]
Interview Questions on Binary Search tree
Given a binary tree,create the copy of the tree. Given a binary tree, count the number of nodes in the tree. Given a binary tree, find the maximum depth the number of nodes along the longest path from the root node down to the farthest leaf node. Write a code to find the minimum and maximum value in binary search tree Print the BST in increasing order…to put this in different way, it simply means to print in inorder traversal Print the post order traversal (recursive) Print the paths in binary search tree from root to leaves.
[Read More]
Why is manhole cover circular?
Reasons for the shape include:
A round manhole cover cannot fall through its circular opening, whereas a square manhole cover may fall in if it were inserted diagonally in the hole. (AReuleaux triangle or other curve of constant width would also serve this purpose, but round covers are much easier to manufacture. The existence of a “lip” holding up the lid means that the underlying hole is smaller than the cover, so that other shapes might suffice.
[Read More]