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 Question: Find median of infinite stream of numbers

Use one max heap and one min heap.

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.

if count of total numbers are even then the new number will be inserted into min heap else it will go to max heap. We also need to remember that numbers in max heap should be less than numbers in min heap.

Code ::

class Container
{
public:
void insert(int val);
float median();

private:
vector<int> minHeap;
vector<int> maxHeap;
};

void Container::insert(int val)
{
if((minHeap.size() + maxHeap.size()) % 2 == 0)
{
if(maxHeap.size() > 0 && val < maxHeap[0])
{
maxHeap.push_back(val);
push_heap(maxHeap.begin(), maxHeap.end());
val = maxHeap[0];
pop_heap(maxHeap.begin(), maxHeap.end());
maxHeap.pop_back();
}
minHeap.push_back(val);
push_heap(minHeap.begin(), minHeap.end(), greater<int>());
}
else
{
if(minHeap.size() > 0 && val > minHeap[0])
{
minHeap.push_back(val);
push_heap(minHeap.begin(), minHeap.end(), greater<int>());
val = minHeap[0];
pop_heap(minHeap.begin(), minHeap.end(), greater<int>());
minHeap.pop_back();
}
maxHeap.push_back(val);
push_heap(maxHeap.begin(), maxHeap.end());
}
}

float Container::median()
{
int count = minHeap.size() + maxHeap.size();
if(count == 0)
return -1; //error value
if(count%2 == 0)
return (float)(minHeap[0] + maxHeap[0]) / 2;
else
return minHeap[0];
}

Friday, March 9, 2012

Microsoft Question: Find diameter of a binary tree

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

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)

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);
}

Thursday, January 5, 2012

Find Depth of a binary tree

int BSTree::getDepth(Node* node)
{
if(!node)
return 0;

int ld = getDepth(node->left);
int rd = getDepth(node->right);

return MAX(ld, rd) + 1;
}

Tuesday, January 3, 2012

Google Question: Find nth minimum in Binary Search Tree.

1. Without extra field in Node structure --

Do inorder traversal and count number of node visited. When count is equal to n return the node.
void BSTree::findNthElem(Node* node, int& n, int& retval)
{
if(!node && n)
retval = -1;
else if(n)
{
findNthElem(node->left, n, retval);
if(n)
{
n = n - 1;
if(n == 0)
retval = node->data;
findNthElem(node->right, n, retval);
}
}
}