[Flipkart][GFG] N meetings in one room

Problem: There is one meeting room in a firm. There are N meetings in the form of (start[i], end[i]) where start[i] is start time of meeting i and end[i] is finish time of meeting i.

What is the maximum number of meetings that can be accommodated in the meeting room when only one meeting can be held in the meeting room at a particular time?

Note: Start time of one chosen meeting can't be equal to the end time of the other chosen meeting.

Example:

Input:
N = 6
start[] = {1,3,0,5,8,5}
end[] =  {2,4,6,7,9,9}
Output: 
4
Explanation:
Maximum four meetings can be held with given start and end timings.
The meetings are - (1, 2),(3, 4), (5,7) and (8,9)

Input:
N = 3
start[] = {10, 12, 20}
end[] = {20, 25, 30}
Output: 
1
Explanation:
Only one meetings can be held
with given start and end timings.

Approach: We can sort these intervals based on start time and then the problem become super easy. You can look at the implementation to understand the rest of the approach.

Implementation in C#:

    public int maxMeetings(int[] start, int[] end, int n)

    {

        if (n == 0)

        {

            return 0;

        }

        Meeting[] meetings = new Meeting[n];

        for(int i = 0; i < n; ++i)

        {

            meetings[i] = new Meeting(start[i], end[i]);

        }

        Array.Sort(meetings, (m1, m2) => {

            return m1.Start.CompareTo(m2.Start);

        });

        int count = 1;

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

        {

            if (meetings[i].Start > meetings[i - 1].End)

            {

                ++count;

            }

            else

            {

                meetings[i] = meetings[i].End < meetings[i - 1].End ? 

                              meetings[i] : 

                              meetings[i - 1];

            }

        }

        return count;

    }

Complexity: O(nlogn)

[Amazon][GFG] Flattening a Linked List

Problem: Given a Linked List of size N, where every node represents a sub-linked-list and contains two pointers:

1. a next pointer to the next node,
2. a bottom pointer to a linked list where this node is head.

Each of the sub-linked-list is in sorted order.

Flatten the Link List such that all the nodes appear in a single level while maintaining the sorted order. 

Note: The flattened list will be printed using the bottom pointer instead of the next pointer.

Example:

Input:
5 -> 10 -> 19 -> 28
|     |     |     | 
7     20    22   35
|           |     | 
8          50    40
|                 | 
30               45
Output:  5-> 7-> 8- > 10 -> 19-> 20->
22-> 28-> 30-> 35-> 40-> 45-> 50.
Explanation:
The resultant linked lists has every 
node in a single level.
(Note: | represents the bottom pointer.)

Input:
5 -> 10 -> 19 -> 28
|          |                
7          22   
|          |                 
8          50 
|                           
30              
Output: 5->7->8->10->19->22->28->30->50
Explanation:
The resultant linked lists has every
node in a single level.

(Note: | represents the bottom pointer.)

Approach: We can treat every node as separate list where next pointer is bottom pointer. Now this will just become the problem of merging sorted lists.

That's all!

Implementation in Java:

    Node flatten(Node root)

    {

    if (root == null || root.next == null)

    {

        return root;

    }

    root.next = flatten(root.next);

    return merge(root, root.next);

    }

    

    private Node merge(Node node1, Node node2)

    {

        if (node1 == null)

        {

            return node2;

        }

        if (node2 == null)

        {

            return node1;

        }

        Node result = null;

        if (node1.data <= node2.data)

        {

            result = node1;

            result.bottom = merge(node1.bottom, node2);

        }

        else

        {

            result = node2;

            result.bottom = merge(node1, node2.bottom);

        }

        result.next = null;

        return result;

    }

Complexity: O(n) where n is total number of nodes in the list including the bottom nodes.

[Gfg] Number of inversions in an array

Problem: Find the number of pairs (i, j) of an array A indices with i < j and A[i] > A[j].

Example:

Input: arr[] = {8, 4, 2, 1}
Output: 6
Explanation: Given array has six inversions: (8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1).

Input: arr[] = {1, 20, 6, 4, 5}
Output: 5
Explanation: Given array has five inversions: (20, 6), (20, 4), (20, 5), (6, 4), (6, 5). 

Approach: We can use brute force approach using two loops where we go to every index 'i' and count number of indices on its right (i +1... n) where arr[i] > arr[j] where j = i + 1 ... n. This approach will work but is time consuming (O(n^2)).

We can use merge sort here, basically we can take advantage of merge process. Whenever we see there is an element in the left subarray (left...mid) say leftArr[i] which is greater than element in right subarray (mid + 1...right) say rightArr[j] then we can easily say we will get mid - i + 1 inversions right?

This is because both the arrays are sorted and if there is an element at index i,  leftArr[i] is greater than rightArr[j] then it is obvious that all the elements in leftArr[i....mid] will be greater than rightArr[j].

That's all!

Implementation in C#:

    class Solution

    {

        //Complete this function

        //Function to count inversions in the array.

        public long inversionCount(long[] arr)

        {

            long length = arr?.Length ?? 0;

            if (length <= 1)

            {

                return 0;

            }

            return this.CountInversionCount(arr, 0, length - 1);

        }

        

        private long CountInversionCount(long[] arr, long left, long right)

        {

            if (left >= right)

            {

                return 0;

            }

            long mid = left + (right - left) / 2;

            long leftInvCount = this.CountInversionCount(arr, left, mid);

            long rightInvCount = this.CountInversionCount(arr, mid + 1, right);

            long mergeInvCount = this.Merge(arr, left, mid, right);

            return leftInvCount + rightInvCount + mergeInvCount;

        }

        

        private long Merge(long[] arr, long left, long mid, long right)

        {

            List<long> temp = new List<long>();

            long i = left, j = mid + 1;

            long invCount = 0;

            while (i <= mid && j <= right)

            {

                if (arr[i] > arr[j])

                {

                    invCount += (mid - i + 1);

                    temp.Add(arr[j++]);

                }

                else

                {

                    temp.Add(arr[i++]);

                }

            }

            while (i <= mid)

            {

                temp.Add(arr[i++]);

            }

            while (j <=  right)

            {

                temp.Add(arr[j++]);

            }

            i = left;

            for (j = 0; j < temp.Count; ++j)

            {

                arr[i++] = temp[(int)j];

            }

            return invCount;

        }

    }

Complexity: O(nlogn)

[GFG][Amazon] Find the missing and repeating number

Problem: You are given an array of n+2 elements. All elements in the array are in range 1 to n and all elements occur once except two numbers which occur twice. Find the two repeating numbers.

Example:

Input: arr[] = {3, 1, 3}
Output: Missing = 2, Repeating = 3
Explanation: In the array, 2 is missing and 3 occurs twice 

Input: arr[] = {4, 3, 6, 2, 1, 1}
Output: Missing = 5, Repeating = 1

Approach: We are going to use xor here.

Implementation in C++:

vector<int> findTwoElement(vector<int> arr, int n)

{

        // code here

        int xor1 = arr[0];

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

        {

            xor1 ^= arr[i];

        }

        

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

        {

            xor1 ^= i;

        }

        

        int setBit = xor1 & ~(xor1 - 1);

        int x = 0, y = 0;

        for (int i = 0; i < n; ++i)

        {

            if (arr[i] & setBit != 0)

            {

                x ^= arr[i];

            }

            else

            {

                y ^= arr[i];

            }

        }

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

        {

            if (i & setBit != 0)

            {

                x ^= i;

            }

            else

            {

                y ^= i;

            }   

        }

        vector<int> result;

        result.push_back(x);

        result.push_back(y);

        return result;

    }

Complexity: O(n)