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)