Diameter of a Binary Tree
Posted on December 19, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
The diameter of a tree T is the largest of the following quantities:
[Read More]Remove Character From String1 which are present in String2
Posted on December 19, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
You are given two strings, remove the characters from the first string which are present in the second string.
Algorithm: Let first input string be “test string” and the string which has characters to be removed from first string be “mask”
1: Initialize:
res_ind = 0 /* index to keep track of processing of each character in i/p string */
ip_ind = 0 /* index to keep track of processing of each character in the resultant string */
[Read More]Longest increasing subsequence
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 11 minutes
| Kinshuk Chandra
Longest Increasing Subsequence has been a classic Dynamic Programming problem. O(N^2) has been around for a while but more interesting is the following O(n log n) solution.
Problem Input : Sequence of integers (or any comparable items)
Output : Longest increasing subsequence of the sequence, which may not be contiguous.
For example : We have sequence : 1,8,2,7,3,6,4,5 which has the longest increasing subsequence : 1,2,3,4,5.
Note that the numbers are non-contiguous.
[Read More]Vertical Sum of a Binary Tree
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
please explain doubly linked list method in words Anonymous - Apr 6, 2014please explain doubly linked list method in words
Added the basic algo for that:
1. Start with the root node and empty double list listNode
2. Add the value of the rootNode to the current listNode
3. Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively.
4. Similarly for right node
Please let me know if I have not explained it properly.
[Read More]Vertical Sum of a Binary Tree
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Question : Find vertical sum of given binary tree.
Example:
1 / \\ 2 3 / \\ / \\ 4 5 6 7 The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7
[Read More]Prove that number between twin primes is divided by 6
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A Twin Prime number is a prime number which differs from other prime number by two. eg (5,7), (11,13), (17,19), (29,31), (41,43), (59,61)…….. Prove that number between twin primes is divisible by 6. Solution 1:
all prime numbers are of the form 6x+1 or 6x-1
so to be twin primes they should be 6x-1 and 6x+1 for some x
so the number netween them is 6x which is divided by 6
[Read More]How can you properly devide the hotel charges?
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem: Three people check into a hotel. They pay $30 to the manager, and go to their room. The manager finds out that the room rate is $25 and gives $5 to the bellboy to return. On the way to the room the bellboy reasons that $5 would be difficult to share among three people so he pockets $2 and gives $1 to each person. Now each person paid $10 and got back $1.
[Read More]Passengers and Random Seats in Airplane
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem : 100 passengers are boarding an airplane with 100 seats.
Everyone has a ticket with his seat number. These 100 passengers boards the airplane in order.
However, the first passenger lost his ticket so he just took a random seat.
For any subsequent passenger, he either sits on his own seat or, if the seat is taken, he takes a random empty seat.
What’s the probability that the last passenger would sit on his own seat ?
[Read More]Find whether a given number N is of the form 2^x + 2^y (^ means exponentiation, x and y are positive).
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Devise an algorithm to find whether a given number N is of the form 2^x + 2^y (^ means exponentiation, x and y are positive).
Solution
The solution is using bitmaps (arrays of bits)
1. Initialization will take O(N) but checking for existence will be done in O(1)
2. Bitmap array will be char[M/8] since a char is 8 bits long
Complexities :
Time : O(N) in initialization, O(1) in access
[Read More]Find out the matching socks
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem : Michael have ten pairs of black socks, eight pairs of white socks and seven pairs of green socks. Everything is mixed in a draw. As there is no light he were not able to identify the color of the socks. How many of the socks did he want to take to match one pair ?
Solution: The answer is 4 since in worst case all 3 socks taken first will be different color then the 4th one would be repetition.
[Read More]