XML Sequence Delimiter

An XML  sequence delimiter might be required for processing XML streams without the boiler plate code that comes with well known XML Parsers. A simple use case might be converting xml transformations on the fly like producing a partial output of the xml transformation as the user punches the script, etc.  This one uses a … Continue reading

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)

Find minimum edit distance between two strings

This can be solved using Levenshtein distance. The solution below uses a temp matrix [0…n][0…m]. This is usually not a good approach for handling large strings. Other approaches are via hash functions. package strings; /** * Implements the Lavenshtein algorithm to find the minimum number of edits * to change one string to another * … Continue reading

Sorting a Stack using push,pop,isEmpty and peek

Problem Definition: Sort a Stack using standard operations  push,pop,isEmpty and peek. Solutions: 1. Use an additional array of size n, insert into array (Time Complexity O(n)). Use Counting Sort (Complexity O(n)). Memory overhead of O(m+n). 2. Use recursion with no additional space. The time complexity is O(n) and O(1) space complexity. The following code is … Continue reading