Zig-Zag World of Algorithm and Data Structures: March 2012

Tuesday, March 20, 2012

Postorder traversal of a binary tree without recursion

void BSTree::postorder()
{
stack<Node*> st;
set<Node*> visit;
if(root.get() == NULL)
return;
st.push(root.get());

while(!st.empty())
{
Node* curr = st.top();
if(curr->left.get() != NULL && visit.find(curr->left.get()) == visit.end())
st.push(curr->left.get());
else if(curr->right.get() != NULL && visit.find(curr->right.get()) == visit.end())
st.push(curr->right.get());
else
{
cout<<curr->data<<'\t';
visit.insert(curr);
st.pop();
}
}
}

Preorder traversal of a binary tree without recursion

void BSTree::preorder()
{
bool done = false;
stack<Node*> st;
Node* curr = root.get();

while(!done)
{
if(curr != NULL)
{
cout<<curr->data<<'\t';
st.push(curr);
curr = curr->left.get();
}
else
{
if(!st.empty())
{
curr = st.top()->right.get();
st.pop();
}
else
done = true;
}

}
}

Inorder traversal of a binary tree without recursion

void BSTree::inorder()
{
bool done = false;
stack<Node*> st;
Node* curr = root.get();
while(!done)
{
if(curr != NULL)
{
st.push(curr);
curr = curr->left.get();
}
else
{
if(!st.empty())
{
curr = st.top();
cout<<curr->data<<'\t';
st.pop();
curr = curr->right.get();
}
else
done = true;
}
}
}

Monday, March 19, 2012

Adobe Question: Url Encode a string

A buffer of infinite length is given. You need to change < to < and > to >

Solution:

void encode()
{
char str[2048] = "ab<bc>nn<";
int len = strlen(str);
int count = 0;
for(int i = 0; i < len; ++i)
{
(str[i] == '<' || str[i] == '>') && (++count);
}

int newLen = len + 3*count;
str[newLen] = '\0';
for(int i = newLen-1, j = len-1; j>=0; --j)
{
if(str[j] == '<' || str[j] == '>')
{
str[i--] = ';';
str[i--] = 't';
(str[j] == '<') && (str[i--] = 'l') || (str[i--] = 'g');
str[i--] = '&';
}
else
str[i--] = str[j];
}
cout<<'\n'<<str<<"\n\n";
}

Sunday, March 11, 2012

[Adobe] Find median of infinite stream of numbers

Problem: The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

For example, for arr = [1, 2, 3], the median is 1.
For example, for arr = [1, 2], the median is (1 + 2) / 2 = 1.5.

Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void AddNum(int num) adds the integer num from the data stream to the data structure.
double FindMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Approach: Use one max heap and one min heap in following way:

Max heap will be containing the numbers which are less than median.
Min heap will be containing the numbers which are greater than or equals to median.
Difference between the size of two heaps will never be greater than 1.

The numbers in max heap should be less than numbers in min heap so if the current number is less than or equal to the top of max heap then it will go to max heap otherwise it will go to min heap.

We just need to take care of the violation of third condition after insertion.

When we try to find the median, we can just see if max heap has more elements than min heap (case of number of elements are odd) then we can return it's top otherwise its the case of even number so we can safely return (top of max heap + top of min heap) / 2.

Implementation in C#:

public class IntMaxCompare : IComparer<int>
{
    public int Compare(int x, int y) => y.CompareTo(x);
}

public class MedianFinder 
{

    public MedianFinder() 
    {
        this.maxHeap = new PriorityQueue<int, int>(new IntMaxCompare());
        this.minHeap = new PriorityQueue<int, int>();
    }
    
    public void AddNum(int num) 
    {
        if (this.maxHeap.Count == 0 || this.maxHeap.Peek() >= num)
        {
            this.maxHeap.Enqueue(num, num);
        }
        else
        {
            this.minHeap.Enqueue(num, num);
        }
        if (this.maxHeap.Count > this.minHeap.Count + 1)
        {
            int elem = this.maxHeap.Dequeue();
            this.minHeap.Enqueue(elem, elem);
        }
        else if (this.maxHeap.Count < this.minHeap.Count)
        {
            int elem = this.minHeap.Dequeue();
            this.maxHeap.Enqueue(elem, elem);
        }
    }
    
    public double FindMedian() 
    {
        if (this.maxHeap.Count > this.minHeap.Count)
        {
            return (double) this.maxHeap.Peek();
        }
        return (this.maxHeap.Peek() + this.minHeap.Peek()) / 2.0;
    }

    PriorityQueue<int, int> maxHeap;
    PriorityQueue<int, int> minHeap;
}

Complexity: AddNum - O(logn), FindMedian - O(1)

Friday, March 9, 2012

Microsoft Question: Find diameter of a binary tree

Problem: The diameter or width of a tree is the number of nodes on the longest path between two leaves in the tree.

Example:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Approach: Diameter of a binary tree = MAX(height of left sub-tree + height of right sub-tree,
diameter of left sub-tree,
diameter of right sub-tree)

Implementation:

   int diameter(Node* node, int& height)
   {
       int lh = 0, rh = 0, ld = 0, rd = 0;
       if(node == NULL)
       {
           height = 0;
           return 0;
       }

       ld = diameter(node->left, lh);
       rd = diameter(node->right, rh);

       height = max(lh, rh) + 1;

       return MAX(lh + rh + 1, ld, rd);
   }

Complexity: O(n)

Home