Friday, May 29, 2015

Quick Sort

Quick Sort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. It was invented by C.A.R. Hoare. it is still a very commonly used algorithm for sorting. it is a divide and conquer algorithm.

Algorithm:

The steps are as follows:
1. Pick an element, say P (the pivot).
2. Re-arrange the elements into 3 sub-blocks:
• Less than or equal to P say S1.
• P (the only element in the middle-block).
• Greater than or equal to P say S2.
3. Repeat the process recursively for S1 and S2.

Example:

Choosing Pivot:
1. Always pick first element as pivot.
2. Always pick last element as pivot.
3. Pick a random element as pivot.(Recommended)
4. Pick median as pivot.

Why is Quick Sort preferred for arrays?

Quick Sort in its general form is an in-place sort  whereas merge sort requires O(n) extra storage. Allocating and de-allocating the extra space used for merge sort increases the running time of the algorithm. Comparing average complexity we find that both type of sorts have O(nlogn) average complexity but the constants differ. For arrays, merge sort loses due to the use of extra O(n) storage space.

Implementation:

//Using random element as pivot
int partition(int arr[], int l, int r)
{
srand(time(NULL));
int pivot = rand() % (r - l + 1) + l;
std::swap(arr[l], arr[pivot]);
int j = l + 1;
for(int i = l+1; i <= r; ++i)
{
if(arr[i] < arr[l])
std::swap(arr[j++], arr[i]);
}
std::swap(arr[--j], arr[l]);
return j;
}

void quick_sort(int arr[], int l, int r)
{
if(l < r)
{
int p = partition(arr, l, r);
quick_sort(arr, l, p-1);
quick_sort(arr, p+1, r);
}
}

Complexity: O(nlogn)

Thursday, May 28, 2015

Problem: Sort the given linked list using merge sort.

Why merge sort is preferred over quick sort in case of linked list?

In case of linked lists merge sort is preferred due to difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes are not  adjacent in memory. Unlike array, in linked list, we can insert items in the middle in O(1) extra space and O(1) time. Therefore merge operation of merge sort can be implemented without extra space for linked lists.

In arrays, we can do random access as elements are continuous in memory. Unlike arrays, we can not do random access in linked list. Quick Sort requires a lot of this kind of access. In linked list to access i’th index, we have to travel each and every node from the head to i’th node as we don’t have continuous block of memory. Therefore, the overhead increases for quick sort. Merge sort accesses data sequentially and the need of random access is low.

Implementation:

//Public interface
void List::merge_sort()
{
}

void List::split(List::ListNode *source, ListNode *&front, ListNode *&back)
{
if(!source || !source->next)
{
front = source;
back = NULL;
return;
}

ListNode *fast = source->next, *slow = source;
while(fast != NULL)
{
fast = fast->next;
if(fast)
{
slow = slow->next;
fast = fast->next;
}
}

front = source;
back = slow->next;
slow->next = NULL;
}

List::ListNode* List::merge(List::ListNode *front, List::ListNode *back)
{
if(!front)
return back;
if(!back)
return front;
ListNode *final = 0;
if(front->data <= back->data)
{
final = front;
final->next = merge(front->next, back);
}
else
{
final = back;
final->next = merge(front, back->next);
}
return final;
}

void List::merge_sort(List::ListNode*& node)
{
if(!node || !node->next)
return;
ListNode *front = 0, *back = 0;
split(node, front, back);
merge_sort(front);
merge_sort(back);

node = merge(front, back);
}

Complexity: O(nlogn)

Tuesday, May 26, 2015

Microsoft Question: Given a list of events with start time and end time, find the events which have conflict with any other.

Problem: Given a list of events with start time and end time, find the events which have conflict with any other.

Solution: Problem can be solved using interval overlapping.

Complexity: O(n)

Flipkart Question: Find the minimum window in a large string which contains all characters of another string.

Problem: Given a large string S and a smaller string T. Find the minimum size window in the string S which contains all the characters of the string T.

Solution:
• Maintain two pointers to store the begin and end positions of the window, two hash tables needToFind to store total count of a character in T and found to store total count of a character met so far and a count variable to store the total characters in T that's met so far. When count equals T's length, a valid window is found.
• Each time the end pointer is advanced, we increment hasFound[S[end]] by one. Increment count by one if hasFound[S[end]] is less than or equal to needToFind[S[end]]. If count equals to lengh of T then begin pointer can be advanced until found[S[begin]] is greater than needToFind[S[begin]].
• Finally we just need to set minWindowSize to currentWindowSize if currentWindowSize is less than currentWindowSize.

Implementation:

bool minWindow(std::string S, std::string T, int &minWindowBegin,  int &minWindowEnd)
{
int lenS = S.size();
int lenT = T.size();
int needToFind[256] = {0};
int found[256] = {0};
for(int i = 0; i < lenT; ++i)
needToFind[T[i]]++;

int minWindowLen = INT_MAX;
int count = 0;
for(int begin = 0, end = 0; end < lenS; ++end)
{
if(needToFind[S[end]] == 0)
continue;
found[S[end]]++;
if(found[S[end]] <= needToFind[S[end]])
++count;
if(count == lenT)
{
while(needToFind[S[begin]] == 0 || found[S[begin]] > needToFind[S[begin]])
{
if(found[S[begin]] > needToFind[S[begin]])
--found[S[begin]];
++begin;
}
int currWindowLen = end - begin + 1;
if(currWindowLen < minWindowLen)
{
minWindowBegin = begin;
minWindowEnd = end;
minWindowLen = currWindowLen;
}
}
}

return count == lenT;
}

Complexity: O(n) where n is length of S.

Thursday, May 21, 2015

Flipkart Question: Clone a linked list with next and random pointer

Problem: Given a Linked List with one pointer of each node pointing to the next node and the second pointer can point to any node/ random node in the list . Write a program which to make a copy of this list.

Solution:
1. Create the copy each node in the list and insert it between node and its next.
2. Now copy the random pointer as follows:
• node->next->random = node->random->next
3. Restore the original and copy linked lists as follows:
• original->next = original->next->next
• copy->next = copy->next->next
Implementation:

List* List::copy()
{
while(itr)
{
itr->next = new ListNode(itr->data, itr->next);
itr = itr->next->next;
}

while(itr)
{
itr->next->random = itr->random->next;
itr = itr->next->next;
}

while(copyItr->next)
{
itr->next = itr->next->next;
copyItr->next = copyItr->next->next;
itr = itr->next;
copyItr = copyItr->next;
}

itr->next = NULL;

}

Complexity: O(n)

Friday, May 15, 2015

Merge overlapping Interval

Problem: Given a set of intervals, not necessarily in sorted order, merge all overlapping intervals into one.

Solution:
1. Sort all intervals according to their start time.
2. Push first one into a stack.
3. For each interval check if current interval overlaps with top of the stack; if no, then push it onto the stack else if its end time is more than top end time then change the end time of top with current interval's end time.
4. At the end stack will have the merged intervals.

Implementation:

struct Interval
{
int start;
int end;
};

bool compareInterval(Interval i1, Interval i2)
{
return i1.start < i2.start ? true : false;

}

void mergeInterval(Interval* intervals, int len)
{
if(intervals == 0 || len <= 0)
return;

std::sort(intervals, intervals + len, compareInterval);
std::stack<Interval> stInterval;
stInterval.push(intervals[0]);

for(int i = 1; i < len; ++i)
{
Interval tempInterval = stInterval.top();
if(tempInterval.end < intervals[i].start)
stInterval.push(intervals[i]);
else if(tempInterval.end < intervals[i].end)
{
tempInterval.end = intervals[i].end;
stInterval.pop();
stInterval.push(tempInterval);
}
}

std::cout<<"Merged Intervals:\n";
while (!stInterval.empty())
{
Interval interval = stInterval.top();
std::cout <<'['<<interval.start<<", "<< interval.end<<']'<<'\t';
stInterval.pop();
}

}

Complexity: O(nlogn)

Synopsys Question: Check if any two intervals overlap among the given n intervals

Problem: Given n intervals, each interval having start and end time, check if any two intervals overlap or not.

Solution:
1. Sort all intervals according to their start time.
2. In the resultant sorted array, if start time of current interval is less than end of previous interval, then there is an overlap.
Implementation:

struct Interval
{
int start;
int end;
};

bool compareInterval(Interval i1, Interval i2)
{
return i1.start < i2.start ? true : false;
}

bool isOverlap(Interval *arr, int len)
{
if(arr == 0 || len == 0)
return false;

std::sort(arr, arr + len, compareInterval);
for(int i = 1; i < len; ++i)
{
if(arr[i].start < arr[i-1].end)
return true;
}
return false;
}

Complexity: O(nlogn)

Synopsys Question: Find the maximum sum in an array with no two elements are adjacent

Problem: Find the maximum sum in an array such that no two elements are adjacent.

Solution:

Maintain two sums for each element of the given array:
1. sum1 = Max sum including the previous element
2. sum2 = Max sum excluding the previous element
Now:
1. Max sum excluding the current element = max(sum1, sum2)
2. Max sum including the current element = arr[i] + sum2
At the end max of the sum1 and sum2 will be our resultant value.

Implementation:

{
if(arr == NULL || len == 0)
return -1; //Error value

int sumIncludingCurr = arr[0], sumExcludingCurr = 0;

for(int i = 1; i < len; ++i)
{
int tempExcludingSum = max(sumIncludingCurr, sumExcludingCurr);
sumIncludingCurr = sumExcludingCurr + arr[i];
sumExcludingCurr = tempExcludingSum;
}

return max(sumIncludingCurr, sumExcludingCurr);
}

Complexity: O(n)

Tuesday, May 12, 2015

Trie

A Trie (from retrieval), is a multi-way tree structure useful for storing strings over an alphabet. It has been used to store large dictionaries of English (say) words in spelling-checking programs and in natural-language "understanding" programs. Using Trie, search complexities can be brought to optimal limit (key length).

Example:

Given the following strings:
an, ant, all, allot, alloy, aloe, are, ate, be
the corresponding Trie would be:

A simple implementation:

#define ALPHABET_SIZE 26
#include<string>

class Trie
{
public:
Trie();
void insert(std::string key);
int search(std::string key);
private:
struct Trie_Node
{
int value; //For leaf nodes
Trie_Node *children[ALPHABET_SIZE];
Trie_Node();
};
Trie_Node *m_root;
int m_count;
};

Trie::Trie_Node::Trie_Node():value(0)
{
for(int i = 0; i < ALPHABET_SIZE; ++i)
{
children[i] = 0;
}
}

Trie::Trie():m_root(new Trie_Node()), m_count(0)
{

}

void Trie::insert(std::string key)
{
int len = key.size();
Trie_Node *itr = m_root;
++m_count;
for(int i = 0; i < len; ++i)
{
int index = key[i] - 'a';
if(!itr->children[index])
itr->children[index] = new Trie_Node();
itr = itr->children[index];
}
itr->value = m_count;
}

int Trie::search(std::string key)
{
int len = key.size();
Trie_Node *itr = m_root;
for(int i = 0; i < len; ++i)
{
int index = key[i] - 'a';
if(!itr->children[index])
return 0;
itr = itr->children[index];
}
if(itr)
return itr->value;
return 0;
}

Complexity: O(n) for both insertion and search where n is the length of pattern

Wednesday, May 6, 2015

Microsoft Question: Spiral order traversal of a matrix

Problem: Given a 2D array, print it in spiral form.

Implementation:

void spiralPrint(int **arr, int row, int col)
{
if(row == 0 || col == 0 || arr == 0)
return;
if(row == 1 && col == 1)
std::cout<<arr[0][0]<<'\t';
int cBeg = 0, cEnd = col, rBeg = 0, rEnd = row;
while(cBeg < cEnd && rBeg < rEnd)
{
for(int i = cBeg; i < cEnd; ++i)
std::cout<<arr[rBeg][i]<<'\t';
++rBeg;
for(int i = rBeg; i <rEnd; ++i)
std::cout<<arr[i][cEnd - 1]<<'\t';
--cEnd;
if(rBeg < rEnd)
{
for(int i = cEnd - 1; i >= cBeg; --i)
std::cout<<arr[rEnd - 1][i]<<'\t';
--rEnd;
}
if(cBeg < cEnd)
{
for(int i = rEnd - 1; i >= rBeg; --i)
std::cout<<arr[i][cBeg]<<'\t';
++cBeg;
}
}
}

Complexity: O(row*col)

Queue

Queue is also an abstract data type in which the elements are inserted from one end called REAR/BACK, and the deletion of existing elements takes place from the other end called as FRONT/HEAD. This makes queue as FIFO data structure, which means that element inserted first will also be removed first.

Enqueue():

Adding the element into the back of the queue.

Dequeue():

Removing the element from the front of the queue.

Following image will explain these operations better:

Implementation:

template<class T>
class Queue
{
public:
Queue<T>(){}
void enque(T elem);
void deque();
T front();
bool empty();
~Queue(){}
private:
std::list<T> m_list;
};

template<class T>
void Queue<T>::enque(T elem)
{
m_list.push_back(elem);
}

template<class T>
void Queue<T>::deque()
{
m_list.pop_front();
}

template<class T>
T Queue<T>::front()
{
return m_list.front();
}

template<class T>
bool Queue<T>::empty()
{
return m_list.empty();
}

Complexity: O(1) for all of the above operations.

Stack

A stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added.

Push():

Insert new elements into the top of the Stack. Following image will explain it better:

Pop():

Delete an element from the top of the stack. Following image will explain it better:

Implementation:

template<class T>
class Stack
{
public:
Stack<T>(){}
void push(T elem);
void pop();
T top();
bool empty();
~Stack(){}
private:
std::list<T> m_list;
};

template<class T>
void Stack<T>::push(T elem)
{
m_list.push_front(elem);
}

template<class T>
void Stack<T>::pop()
{
m_list.pop_front();
}

template<class T>
T Stack<T>::top()
{
return m_list.front();
}

template<class T>
bool Stack<T>::empty()
{
return m_list.empty();
}

Complexity: O(1) for all of the above operations

Amazon Question: Implement queue using stacks

Problem: Given a stack data structure that supports standard operations like push() and pop(), implement a queue using given stack data structure.

Solution: Use two stacks.

Implementation:

class Queue
{
public:
Queue(){}
void insert(int i);
int remove();
bool isEmpty();
~Queue(){}
private:
std::stack<int> st1, st2;
};

void Queue::insert(int i)
{
st1.push(i);
}

int Queue::remove()
{
if(isEmpty())
return -1; //Error

if(st2.empty())
{
while(!st1.empty())
{
st2.push(st1.top());
st1.pop();
}
}

int retval = st2.top();
st2.pop();
return retval;
}

bool Queue::isEmpty()
{
return st1.empty() && st2.empty();
}

Complexity: insert - O(1), remove - O(n)

Implement stack using two queues

Problem: Given a queue data structure that supports standard operations like enqueue() and dequeue(), implement a Stack using given queue data structure.

Approach: Stack can be implemented using two queues. There are two ways to implement it; one by making push operation costly and one by making pop operation costly.
I am preferring the way in which pop operation is costly as push operations are always more than or equal to pop operations. Following are the steps for push and pop -

push(i)
1. Enqueue i to q1.
pop()
1. One by one dequeue each item except the last element from q1 and enqueue to q2.
2. Dequeue the last item of q1, this will be the return value.
3. Swap the names of q1 and q2 (pointers).
4. Return the item obtained in step 2.

Implementation:

class Stack
{
public:
Stack():m_q1(new std::queue<int>()), m_q2(new std::queue<int>()){}
void push(int i);
int pop();
bool isEmpty();
~Stack(){delete m_q1; delete m_q2;}
private:
std::queue<int> *m_q1, *m_q2;
};

void Stack::push(int i)
{
m_q1->push(i);
}

int Stack::pop()
{
if(isEmpty())
return -1; //Error
while(m_q1->size() > 1)
{
int temp = m_q1->front();
m_q2->push(temp);
m_q1->pop();
}

int retVal = m_q1->front();
m_q1->pop();
std::queue<int>* tempQ = m_q1;
m_q1 = m_q2;
m_q2 = tempQ;
return retVal;
}

bool Stack::isEmpty()
{
return m_q1->empty();
}

Complexity: push - O(1), pop - O(n)

Tuesday, May 5, 2015

Print leaves of binary tree

Problem: Print all the leaves of a binary tree.

Approach: Do inorder traversal and print node's data only if node is a leaf.

Implementation:

void BSTree::printLeaves(Node* node)
{
if(node)
{
printLeaves(node->left);
if(!node->left && !node->right)
std::cout<<node->data<<'\t';
printLeaves(node->right);
}
}

Complexity: O(n)

Boundary traversal of a binary tree

Problem: Given a binary tree, print boundary nodes of the binary tree anti-clockwise starting from the root.

Solution: Problem can be solved using three steps:

1. Print the left boundary in top-down manner.
2. Print all leaf nodes from left to right (sorted according to their horizontal distance).
3. Print the right boundary in bottom-up manner.
All of these steps can be achieved by tweaking leftView, printLeaves and rightView of a binary tree.

Implementation:

#define mapIntToIntVect std::map<int, std::vector<int>>

void BSTree::printLeavesWithHD(Node* node, int hd, mapIntToIntVect& mapDistToNodeVect)
{
if(node)
{
printLeavesWithHD(node->left, hd - 1, mapDistToNodeVect);
if(!node->left && !node->right)
mapDistToNodeVect[hd].push_back(node->data);
printLeavesWithHD(node->right, hd + 1, mapDistToNodeVect);
}
}

void BSTree::printLeavesWithHD()
{
if(!root)
return;
mapIntToIntVect mapDistToNodeVect;
printLeavesWithHD(root, 0, mapDistToNodeVect);
for(mapIntToIntVect::iterator it = mapDistToNodeVect.begin(); it != mapDistToNodeVect.end(); ++it)
{
for(int i = 0; i < it->second.size(); ++i)
{
std::cout<<it->second[i]<<'\t';
}
}
}

void BSTree::leftBoundaryWithNoLeaves(Node* node)
{
std::queue<Node*> q[2];
bool turn = 0;
q[turn].push(node);
while(!q[turn].empty())
{
if(q[turn].front()->left || q[turn].front()->right)
std::cout<<q[turn].front()->data<<'\t';
while(!q[turn].empty())
{
Node* temp = q[turn].front();
if(temp->left)
q[!turn].push(temp->left);
if(temp->right)
q[!turn].push(temp->right);
q[turn].pop();
}
turn = !turn;
}
}

void BSTree::rightBoundaryWithNoLeavesAndRoot(Node* node)
{
std::queue<Node*> q[2];
std::stack<int> st;
bool turn = 0;
q[turn].push(node);
while(!q[turn].empty())
{
int dataToPrint = 0;
bool printRightBoundary = false;
while(!q[turn].empty())
{
Node* temp = q[turn].front();
if(temp->left)
q[!turn].push(temp->left);
if(temp->right)
q[!turn].push(temp->right);
q[turn].pop();
if(temp->left || temp->right)
printRightBoundary = true;
else
printRightBoundary = false;
dataToPrint = temp->data;
}
if(printRightBoundary)
{
st.push(dataToPrint);
}
turn = !turn;
}
while(st.size() > 1)
{
std::cout<<st.top()<<'\t';
st.pop();
}
}

void BSTree::boundaryTraversal()
{
if(!root)
return;
leftBoundaryWithNoLeaves(root);
printLeavesWithHD();
rightBoundaryWithNoLeavesAndRoot(root);
}

Complexity: O(n)

Level order traversal of a binary tree

Problem: Write a method to print level order traversal of a binary tree.

Approach: Use queue.

Implementation:

void BSTree::levelOrder()
{
if(!root)
return;
std::queue<Node*> nodesQ;
nodesQ.push(root);
while(!nodesQ.empty())
{
Node* temp = nodesQ.front();
std::cout<<temp->data<<'\t';
if(temp->left)
nodesQ.push(temp->left);
if(temp->right)
nodesQ.push(temp->right);
nodesQ.pop();
}
}

Complexity: O(n)

Bottom view of binary tree

Problem: Bottom view of a binary tree is the set of nodes visible when the tree is viewed from the bottom. Write a program to print the bottom view of a binary tree.

Approach: Do level order traversal of given binary tree and calculate horizontal distance of each node and then print only the last node at the particular horizontal distance.

Implementation:

#define mapIntToInt std::map<int, int>

struct NodeDist
{
Node* node;
int horizDist;
NodeDist(Node* nd, int hd):node(nd), horizDist(hd){}
};

void BSTree::bottomView()
{
if(!root)
return;

std::queue<NodeDist*> nodeDistQ;
mapIntToInt mapDistToNode;
nodeDistQ.push(new NodeDist(root, 0));
while(!nodeDistQ.empty())
{
NodeDist* temp = nodeDistQ.front();
mapDistToNode[temp->horizDist] = temp->node->data;
if(temp->node->left)
nodeDistQ.push(new NodeDist(temp->node->left, temp->horizDist - 1));
if(temp->node->right)
nodeDistQ.push(new NodeDist(temp->node->right, temp->horizDist + 1));
nodeDistQ.pop();
delete temp;
}

for(mapIntToInt::iterator it = mapDistToNode.begin(); it != mapDistToNode.end(); ++it)
{
std::cout<<it->second<<'\t';
}
}

Complexity: O(n)

Top view of binary tree

Problem: Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Write a program to print the top view of a binary tree.

Approach: Do level order traversal of given binary tree and calculate horizontal distance of each node and then print only the first node at the particular horizontal distance.

Implementation:

#define IntSet std::set<int>

struct NodeDist
{
Node* node;
int horizDist;
NodeDist(Node* nd, int hd):node(nd), horizDist(hd){}
};

void BSTree::topView()
{
if(!root)
return;

std::queue<NodeDist*> nodeDistQ;
IntSet distSet;
nodeDistQ.push(new NodeDist(root, 0));
while(!nodeDistQ.empty())
{
NodeDist* temp = nodeDistQ.front();
if(distSet.find(temp->horizDist) == distSet.end())
{
distSet.insert(temp->horizDist);
std::cout<<temp->node->data<<'\t';
}
if(temp->node->left)
nodeDistQ.push(new NodeDist(temp->node->left, temp->horizDist - 1));
if(temp->node->right)
nodeDistQ.push(new NodeDist(temp->node->right, temp->horizDist + 1));
nodeDistQ.pop();
delete temp;
}
}

Complexity: O(n)

Vertical order traversal of binary tree

Problem: Given a binary tree, print it vertically.

Example:

12
/      \
10       30
/  \        / \
8  11  25  40
\           \     \
9        28   50

The output of print this binary tree vertically will be:
8
10 9
12 11 25
30 28
40
50

Solution: Using preorder traversal, we can recursively calculate horizontal distances. For every horizontal distance we maintain a list of nodes in hash.
Horizontal distance (hd) of root is 0, a left edge is considered as -1 and right edge as +1 horizontal distance. For example in the given example tree the hd of 8 is -2, hd of 11 is 0 and hd of 50 is +3.

Implementation:

#define mapIntToIntVect std::map<int, std::vector<int>>

void BSTree::verticalOrder(Node *node, int horizDist, mapIntToIntVect& mapDistToNodesVect)
{
if(!node)
return;
mapDistToNodesVect[horizDist].push_back(node->data);
verticalOrder(node->left, horizDist - 1, mapDistToNodesVect);
verticalOrder(node->right, horizDist + 1, mapDistToNodesVect);
}

void BSTree::verticalOrder()
{
int hd = 0;
mapIntToIntVect mapDistToNodesVect;
verticalOrder(root, hd, mapDistToNodesVect);

std::map<int, std::vector<int>>::iterator it;
for(it = mapDistToNodesVect.begin(); it != mapDistToNodesVect.end(); it++)
{
for(int i = 0; i < it->second.size(); ++i)
{
std::cout<<it->second[i]<<'\t';
}
std::cout<<std::endl;
}
}

Complexity: O(n)

Monday, May 4, 2015

Right view of binary tree

Problem: Right view of a binary tree is set of nodes visible when tree is visited from right side. Write a program to print the right view of a binary tree.

Approach: Do level order traversal and print the last node in every level.

Implementation:

//Public interface
void BSTree::rightView()
{
if(root)
rightView(root);
}

//Actual implementation
void BSTree::rightView(Node* node)
{
std::queue<Node*> q[2];
bool turn = 0;
q[turn].push(node);
while(!q[0].empty() || !q[1].empty())
{
if(!q[turn].empty())
{
int dataToPrint = 0;
while(!q[turn].empty())
{
Node* temp = q[turn].front();
if(temp->left)
q[!turn].push(temp->left);
if(temp->right)
q[!turn].push(temp->right);
q[turn].pop();
dataToPrint = temp->data;
}
std::cout<<dataToPrint<<'\t';
turn = !turn;
}
}
}

Complexity: O(n)

Left view of binary tree

Problem: Left view of a binary tree is set of nodes visible when tree is visited from left side. Write a program to print the left view of a binary tree.

Approach: Do level order traversal and print the first node in every level.

Implementation:

//Public interface
void BSTree::leftView()
{
if(root)
leftView(root);
}

//Actual implementation
void BSTree::leftView(Node* node)
{
std::queue<Node*> q[2];
bool turn = 0;
q[turn].push(node);
while(!q[0].empty() || !q[1].empty())
{
if(!q[turn].empty())
{
std::cout<<q[turn].front()->data<<'\t';
while(!q[turn].empty())
{
Node* temp = q[turn].front();
if(temp->left)
q[!turn].push(temp->left);
if(temp->right)
q[!turn].push(temp->right);
q[turn].pop();
}
turn = !turn;
}
}
}

Complexity: O(n)

Maximum Product Subarray

Problem: Find the contiguous sub-array within an array which has the largest product.

Solution: When the array has only positive elements then the product of all elements will be answer but when there are negative elements the problem becomes a bit complex. Following are the steps for solving this problem -
1. If current element is positive then max product can be achieved by multiplying current element with max product calculated so far.
2. If current element is negative then max product can be achieved by multiplying current element with min product calculated so far.
3. Current element might be a starting position for max product sub-array.

Implementation:

int maxProductSubArray(int *arr, int len)
{
if(arr == NULL || len == 0)
return 0;
if(len == 1)
return arr[0];

int prevMax = arr[0], prevMin = arr[0];
int maxProduct = arr[0];
for(int i = 1; i < len; ++i)
{
int currMax = max3(prevMax * arr[i], prevMin * arr[i], arr[i]);
int currMin = min3(prevMax * arr[i], prevMin * arr[i], arr[i]);
maxProduct = max(maxProduct, currMax);
prevMax = currMax;
prevMin = currMin;
}
return maxProduct;
}

Complexity: O(n)