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]
Flipping Coins on the table
Problem: There are twenty coins sitting on the table, ten are currently heads and tens are currently tails. You are sitting at the table with a blindfold and gloves on. You are able to feel where the coins are, but are unable to see or feel if they heads or tails. You must create two sets of coins. Each set must have the same number of heads and tails as the other group.
[Read More]
How to reverse a stack in place ?
Reverse a stack, using just push(), pop(), top() operations, in its place itself.
You can not assign any known memory address.
Solution:
Simple methodology for this problem is, take last element from the stack i.e. you need to empty the stack [do it recursively, keeping other elements in memory].
Push the last element in the stack again.
Now while pushing each of earlier elements, first empty whole stack and then push them.
[Read More]
Reaching the door of Heaven
Problem: A person dies, and he arrives at the gate to heaven. There are three doors in the heaven. one of them leads to heaven. another one leads to a 1-day stay at hell, and then back to the gate, and the other leads to a 2-day stay at hell, and then back to the gate. every time the person is back at the gate, the three doors are reshuffled. How long will it take the person to reach heaven?
[Read More]
Random Selection from a Linked List
There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.
Conditions : Use random number function rand() that returns a number between 0 and 1. It must be done in O(N) time Solution:
1. Take 2 arrays R[K] and Num[K]
[Read More]
Use some Datastructure to get O(1) stack operations
Design a datastructure to implement a stack such that ALL of push(), pop() and getMax() functions work in O(1) time. You have infinite memory at your disposal.
Also note that function getMax() just returns the element with maximum value in the stack and NOT delete it from the stack like what pop() does.
Insight : compress the information using diff
PUSH :
if stack empty
push(elem)
push(elem)
else
min = pop()
push(elem-min)
push(min)
POP :
min = pop()
elem = pop()
if elem is -ve
push(min-elem) // earlier min
return min
else
push(min)
return elem + min
MIN :
min = pop()
push(min)
return min
O(n+1) space and constant operations for pop push min
Next Greater Element in an array
i have used 2nd approach to code this question but…
Anonymous - May 6, 2014
i have used 2nd approach to code this question but i am getting wrong answer in test case:
No of elements in Array :5
Array:(1,5,4,7,8)
see code https://ideone.com/jmgV62
Thanks for your code mate :)
Next Greater Element in an array
Problem Given an array, print the next greater element for every element. Elements for which no greater element exist, print next greater element as -1.
Example For the elements of the array [4, 5, 2, 25, 20, 11, 13, 21, 3] greater elements are as follows.
4 –> 5
5 –> 25
2 –> 25
25 –> -1
20 –> 21
11 –> 13
13 –> 21
21 –> -1
[Read More]
Folding BSTs
Given a binary tree, find out if the tree can be folded or not.
Eg : tree (a) can be folded, but (b) cannot be folded
(a) 10 / \\ 7 15 \\ / 9 11 (b) 10 / \\ 7 15 / / 5 11 The tree can be folded only if its left subtree is mirror image of its right subtree or vice versa( considering their organization only not node valves.
[Read More]