I visit many colleges and universities (mostly technical). Following is my feedback: Continue reading »

Given a pointer to the root node of the tree, write code to find if it is an Almost Complete Binary Tree or not?

A Binary Tree of depth d is Almost Complete iff:

- The tree is Complete Binary Tree (All nodes) till level (d-1).
- At level d, (i.e the last level), if a Node is present, then all the Nodes to the left of that node should also be present.

For example, the left tree below is NOT an Almost Complete Binary Tree but the right tree is an Almost Complete Binary Tree

NOT Almost Complete Almost Complete Binary Tree -------------------- --------------------------- _ A _ | _ A _ / \ | / \ B C | B C / \ / \ | / \ / \ D E F G | D E F G / \ / \ | / \ H I J K | H I

The left tree is not almost complete because in the last level, the nodes left to Node-J are missing (children of Node-E).

Continue reading »

What improvement has java-8 made that performance of HashMap.get() function call is fast by 20% in Java-8. Continue reading »

It is almost impossible to design a generic hash system without collision. In case of collision, it need to be handled. There are multiple ways of handling collision. Separate chaining is one of such techniques.

You may solve the simple probability, *“Given a set of n randomly chosen people, what is the probability of two people having same birthday?”*

You may also solve, * “At least how many people need to be picked to make the probability 100% that at least two of them have same birthday?”*

Answer to the second question is 367, because there are 366 possible birthdays (including Feb-26).

The question now is, *“At least how many people need to be picked to make the probability 99.9% that at least two of them have same birthday?”*

Answer is 70.

And if the question is,*“At least how many people need to be picked to make the probability 50% that at least two of them have same birthday?”*

Answer is 23.

Let us design a data structure in which we want to store numbers (taking it for simplicity, else it can be anything). We want to minimise the time taken by the following three operations:

**Insertion**, time taken to insert a new value.**Deletion**, time taken to remove an existing value.**Searching**, time taken to search for a value in the data structure and see if it is present or not.

Which data structure do you suggest ?

Doctor gave you two types of medicine tablets (pils) A and B, and asked you to take one from each daily. The two tablets are in different bottles and look exactly same

One day, while taking the pills, you open Bottle-A and tap one pill out in your hand. Then you open the second bottle to take one pill from it, but accidentally two pills pop out from the bottle on your hand. Now you have 1 A-Pill and 2 B-Pills in your hand and you cannot distinguish them.

The pills are very expensive and you do not want to throw them, neither can you afford to take wrong pills. What should you do?

Continue reading »

Given a binary tree and two values. Find if these values appear in sibling nodes in the tree. For example, if tree is

Then 2 and 6 are siblings but 6 and 9 are not siblings (they are cousin nodes).

A valid mathematical expression can also have duplicate parenthesis as shown below:

((a+b)) (((a+(b)))+(c+d))

Write code to find if an expression has duplicate parenthesis. You may assume that expression does not have any white spaces. Continue reading »

Print Next Greater Element for every element in the array. The Next greater Element of element x is first greater element on its right side.

Elements for which no greater element exist, next greater element is -1.

Example: - For any array, rightmost element always has next greater element as -1. - All elements of an array sorted in decreasing order have next greater element as -1. - For input array {5, 9, 1, 15}, the next greater elements of each element are as follows. {9, 15, 15, -1} - For input array {20, 17, 15, 10}, the next greater elements are {-1, -1, -1, -1}