Given a BST T and a node N in T such that all leaf nodes are connected in doubly linkedlist fashion, find height of the node N in T.
Dec 19, 2009
Mar 19, 2008
largest common structurally similar sub tree
Given two trees as input, find the largest common structurally equivalent sub tree between the two trees. (The largest common sub tree corresponds to the common sub tree having the maximum number of total nodes ).
Mar 17, 2008
find nth max element in BST(Binary search tree)
Without using any extra space. Tree can be traversed only once.
Feb 22, 2008
Sorting for large data sizes
I have a computer file containing 1,000,000 non-negative integers, in no particular order. Imagine that they are the membership numbers of people who are enrolled in my internet club. A new person wants to join the club, and we need to find an unused number to allocate to them. How would you find, in a reasonable time, a number that was not already in the file?
Hint: Use Selection trees for finding the first missing integer among those 1,000,000 integers. The in memory amount of data that we have to keep is very small.
Reference: http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch6.html
Feb 17, 2008
Blogs, Tagging and Summary Problem
(Originally mentioned by Ghai uncle, this is an extended problem of the same kind)
A blogger just wrote a review on movie "Shivaji" starring Rajnikant and tagged it as "Rajnikant movie, Shivaji, movie review". For better surfing experience of the blogger, the blogging portal (your firm) wants to develop following features:
1. The moment the blogger posts his review, he is shown a list of other reviews on this movie. (To make it simple, the list contains links to blogs from his friends only)
2. There is an option to list all such blogs in a page. The listing page contains a shortest summary from each link containing all the tags and the tags highlighted properly in different colors in the summary. So for example, "Rajnikant movie" will be colored red, "Shivaji" would be colored blue, "movie review" will be colored green in the summary; however "Rajnikant" merit no coloring and "shivaji movie" merit coloring of "shivaji" only and likewise.
How would you do it?
Hint: There are essentially three problems:
1. finding blog links with similar tags.
2. finding shortest summary of text from a document containing all the tags in it.
3. finding out occurrences of a set of keywords/tags in a document.