Sunday, March 2, 2014

Find the pivot element in the rotated sorted array

A sorted array is rotated around a pivot element. Find the pivot element in the rotated sorted array.
 
Analysis

Lets start with an example
Original array:           2, 4, 6, 8, 9, 10, 12, 15
Rotated array:           10, 12, 15, 2, 4, 6, 8, 9
Output:                      3


Sunday, February 23, 2014

Remove the duplicate elements in the string

Given a string, inplace remove the duplicate elements form the string.
For e.g. the given string is "codersstop is  a programming blog"
Result: "coderstp iagmnbl"

Approach:

Maintain a lookup table of the 256 entries to mark the occurrence of each of the characters, and only copy the elements which are occurring for the first time.
Below snippet of code removes the duplicate elements from the string

void removeDuplicate(char * s) {
    char a[256] = {0}, c = 0;
    int len = strlen(s);
    for(int i = 0; i < len; i++) {
        if(a[s[i]] == 0) s[c++] = s[i];
        a[s[i]] = 1;
    }
    s[c] = '\0';
}

Overall time complexity is O(n) and space complexity O(1)

Monday, February 3, 2014

Minimum distance between the two nodes of tree

Given a binary tree(not BST) and two nodes in the tree(not necessarily leaf nodes), find the minimum distance between them.

Approach:

The minimum distance can be computed by first finding the LCA of the two nodes, and then finding the heights of the all the three nodes(2 nodes + 1 LCA) from the root. 
(For finding the LCA in the binary tree refer to the previous post
and finding the height of the element in the binary tree is self explanatory.)