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)

Merge sort for Linked List.

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()

{

if(head)

merge_sort(head);

}

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)

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.

[Flipkart][LeetCode] Copy List with Random Pointer

Problem: A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Approach:

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 in C#:

    public Node CopyRandomList(Node head)

    {

        if (head == null)

        {

            return null;

        }

        Node node = head;

        while (node != null)

        {

            Node next = node.next;

            node.next = new Node(node.val);

            node.next.next = next;

            node = next;

        }

        node = head;

        while (node != null)

        {

            node.next.random = node.random?.next;

            node = node.next.next;

        }

        node = head;

        Node copyHead = node.next;

        Node copyNode = copyHead;

        while (node != null)

        {

            node.next = node.next.next;

            copyNode.next = copyNode.next?.next;

            node = node.next;

            copyNode = copyNode.next;

        }

        return copyHead;    

    }

Complexity: O(n)

[Uber] Merge overlapping Interval

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

Example:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Approach:

1. Sort all intervals according to their start time, if start time is same then based on end time.
2. If current interval's start is lees than or equal to previous interval's end then we know that we can merge intervals. The new interval will be [previous interval' start, Max of current and previous end]. 
3. Else add the current interval to result.
4. Repeat 2-3 for every interval.

Implementation in C#:

    public int[][] Merge(int[][] intervals)

    {

        int length = intervals?.Length ?? 0;

        if (length <= 1)

        {

            return intervals;

        }

        Array.Sort(intervals, (i1, i2) => {

            int retVal = i1[0].CompareTo(i2[0]);

            if (retVal == 0)

            {

                return i1[1].CompareTo(i2[1]);

            }

            return retVal;

        });

        int currIndex = 0;

        for (int i = 1; i < length; ++i)

        {

            if (intervals[currIndex][1] >= intervals[i][0])

            {

                intervals[currIndex][1] = Math.Max(intervals[currIndex][1],

                                                   intervals[i][1]);

            }

            else

            {

                intervals[++currIndex] = intervals[i];

            }

        }

        int[][] result = new int[currIndex + 1][];

        Array.Copy(intervals, 0, result, 0, currIndex + 1);

        return result;

    }

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:

int maxSumWithoutAdjacentElem(int *arr, int len)
{
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)

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:

Implementation in C#:

    public class TrieNode

    {

        public const short ALPHABET_SIZE = 26;

        public TrieNode(char value)

        {

            this.Value = value;

            this.Childrens = new TrieNode[ALPHABET_SIZE];

        }

        public char Value { get; set; }

        public TrieNode[] Childrens { get; set; }

    }

    public class Trie

    {

        public const char EndOfWord = '#'; // Leaf node

        public const char CharOfWord = '*';

        public Trie()

        {

            this.root = new TrieNode('x'); // special charater for root

        }

        public void Insert(string word)

        {

            TrieNode node = root;

            foreach(char ch in word)

            {

                if (node.Childrens[ch - 'a'] == null)

                {

                    node.Childrens[ch - 'a'] = new TrieNode(CharOfWord);

                }

                node = node.Childrens[ch - 'a'];

            }

            node.Value = EndOfWord;

        }

        public bool Search(string word)

        {

            TrieNode node = this.root;

            foreach(char ch in word)

            {

                if (node.Childrens[ch - 'a'] == null)

                {

                    return false;

                }

                node = node.Childrens[ch - 'a'];

            }

            return node.Value == EndOfWord;

        }

        public bool StartsWith(string prefix)

        {

            TrieNode node = this.root;

            foreach (char ch in prefix)

            {

                if (node.Childrens[ch - 'a'] == null)

                {

                    return false;

                }

                node = node.Childrens[ch - 'a'];

            }

            return true;

        }

        public bool PatternSearch(string word)

        {

            return this.DFSPatternSearch(this.root.Childrens, word, 0);

        }

        private bool DFSPatternSearch(TrieNode[] nodes, string word, int startIndex)

        {

            if (startIndex == word.Length)

            {

                return false;

            }

            if (word[startIndex] == '.')

            {

                bool result = false;

                foreach(TrieNode node in nodes)

                {

                    if (node == null)

                    {

                        continue;

                    }

                    if (startIndex == word.Length - 1 && node.Value == EndOfWord)

                    {

                        return true;

                    }

                    if (this.DFSPatternSearch(node.Childrens, word, startIndex + 1))

                    {

                        result = true;

                    }

                }

                return result;

            }

            else if (nodes[word[startIndex] -  'a'] != null)

            {

                if (startIndex == word.Length - 1 && nodes[word[startIndex] -'a'].Value == EndOfWord)

                {

                    return true;

                }

                return this.DFSPatternSearch(nodes[word[startIndex] - 'a'].Childrens, word, startIndex + 1);

            }

            else

            {

                return false;

            }

        }

        private TrieNode root;

    }

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

[Microsoft][Google] Spiral order traversal of a matrix

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

Example:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Approach: Nothing to explain, just for loops. Have a look at implementation directly.

Implementation in C#:

    public IList<int> SpiralOrder(int[][] matrix)

    {

        List<int> result = new List<int>();

        int rows = matrix?.Length ?? 0;

        if (rows == 0)

        {

            return result;

        }

        int cols = matrix[0].Length;

        int startRow = 0, endRow = rows - 1;

        int startCol = 0, endCol = cols - 1;

        while (startRow <= endRow && startCol <= endCol)

        {

            for (int i = startCol; i <= endCol; ++i)

            {

                result.Add(matrix[startRow][i]);

            }

            for (int i = startRow + 1; i <= endRow; ++i)

            {

                result.Add(matrix[i][endCol]);

            }

            if (startRow < endRow && startCol < endCol)

            {

                for (int i = endCol - 1; i >= startCol; --i)

                {

                    result.Add(matrix[endRow][i]);

                }

                for (int i = endRow - 1; i > startRow; --i)

                {

                    result.Add(matrix[i][startCol]);

                }

            }

            ++startRow;

            --endRow;

            ++startCol;

            --endCol;

        }

        return result;

    }

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)

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 in C++:

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)