XML Sequence Delimiter
Posted on September 11, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
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 simple pattern based filter and recursion to achieve it. The delimiter is assumed to be comma (,).
[Read More]Counting sort
Posted on September 11, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items.
It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.
Example
For simplicity, consider the data in the range 0 to 9.
[Read More]Sorting a Stack using push,pop,isEmpty and peek
Posted on September 11, 2011
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Problem Definition: Sort a Stack using standard operations push,pop,isEmpty and peek.
This question is asked in cracking the coding interview. Other ways of asking the question
Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that
should be used to write this program: push | pop | peek | isEmpty Note - peek is equivalent to top() function in java, where you dont pop out the element but peek and see.
[Read More]Balanced Search tree
Posted on September 10, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Definition
A balanced search tree is a tree which can provide operations like insert, delete and search in O(lg n) where n is the height of tree and lg n is height.
Motivation behind Balanced Search tree
Properties of sorted array
Consider the sorted array. If we have a sorted array, what kinds of operations can we perform on it?
Binary search in O(logn) time. (We use binary search) Select element given ith order statistic in O(1) Computing min/max of array - O(1) Predecessor/Successor - O(1), just find that element and return one before/after it Rank - how many keys stored are less than or equal to the key - O(logn) Output in sorted order - O(n) Simply using a sorted array would be unacceptable for insertion/deletion because it could use O(n) time.
[Read More]AVL tree : Introduction
Posted on September 7, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Introduction
AVL Tree is a kind of binary search tree. Different from binary search tree is, it is self-balanced. The heights of two child subtress of node differ by at most one. Because of this, another name of AVL Tree is height-balanced.
These are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has Theta(lg n) height and hence Theta(lg n) worst case lookup and insertion times.
[Read More]Implement a Queue using two stacks
Posted on September 7, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Implement a Queue using two stacks.
Solution
Logic : We’ll implement a FIFO queue using two stacks.Lets call the stacks Instack and Outstack. Enqueue:
An element is inserted in the queue by pushing it into the Instack. ** Dequeue:**
An element is extracted from the queue by popping it from the Outstack. If the Outstack is empty then all elements currently in Instack are transferred to Outstack but in the reverse order.
[Read More]How to reverse a doubly linked list ?
Posted on September 7, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
I talked about how to reverse a singly linked list earlier. That was slightly tricky to understand.
Reversing a doubly linked list is relatively easy. The logic is : You need to keep on changing the next and previous pointers as you traverse the entire list. Here is the code snippet in Java :
**public** **void** **reverse**() { **if** (first == **null**) **return**; DoubleNode previous = first; DoubleNode current = first.
[Read More]All permutations of a string
Posted on September 7, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
small trick ,but a very nice solution for duplicat…
nikhil - Feb 4, 2014
small trick ,but a very nice solution for duplicates!!!!
Thanks Nikhil. :)
can u please write the main function for duplicate program. I ran the duplicate program and it is not giving me the desired output
All permutations of a string
Posted on September 7, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
Write a method to compute all permutations of a string.
Example
For a string of length n, there are n! permutations.
INPUT: “abc”
OUTPUT: “abc” “acb” “bac” “bca” “cab” “cba” So, we have 3! = 6 items for string abc.
Solution
There are several ways to do this. Common methods use recursion, memoization, or dynamic programming.
The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually.
[Read More]What is a data structure?
Posted on June 9, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
A data structure is encapsulation of data and relevant operations. It is referred to as an Abstract Data Type (ADT), signifying that the actual implementation is left open, subject to satisfying the intended meaning of the operations. For the most part the exact data representation is not presented; rather, all access to the data is through the operations.
The Java class is a perfect model for an ADT. In addition to the encapsulation with accessibility via operations only, the presentation of operations are in the modern object-oriented fashion in which the data takes precedence over the operation.
[Read More]