[LeetCode] IPO

Problem: Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.

The answer is guaranteed to fit in a 32-bit signed integer.

Example:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6

Approach: We are going to be greedy here. Here are the steps for solving this problem:

1. Choose what pojects can be taken: We need to get all the projects that can be done using the current capital. Basically all the projects whose capital is less than or equal to current capital. (To do it efficiently we can first sort the projects based on capital and then enter into this step).
2. Choose the project with max profit from the above projects: Now that we have got all the projects that can be done based on current capital we need to choose the project with max profit among these projects. To do it, we can store doable projects in the max heap based on profit of projects. We need to add this project's profit to current capital

Using the above 2 steps repeatedly k times, we will get the maximum possible capital. That's all!

Implementation in C#: 

public class Project

{

    public int Capital {get; set;}

    public int Profit {get; set;}

    public Project(int capital = 0, int profit = 0)

    {

        this.Capital = capital;

        this.Profit = profit;

    }

}

public class IntMaxComparer : IComparer<int>

{

    public int Compare(int i, int j) => j.CompareTo(i);

}

public class Solution {

    public int FindMaximizedCapital(int k, int w, int[] profits, int[] capital)

    {

        int length = profits?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        var projects = this.GetSortedProjects(profits, capital);

        // Max heap

        var pq = new PriorityQueue<Project, int>(new IntMaxComparer());

        int currIndex = 0;

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

        {

            while(currIndex < length &&

projects[currIndex].Capital <= w)

            {

                pq.Enqueue(projects[currIndex],

projects[currIndex].Profit);

                ++currIndex;

            }

            if (pq.Count == 0)

            {

                break;

            }

            var qProject = pq.Dequeue();

            w += qProject.Profit;

        }

        return w;

    }

    private Project[] GetSortedProjects(int[] profits, int[] capital)

    {

        var projects = new Project[profits.Length];

        for (int i = 0; i < profits.Length; ++i)

        {

            projects[i] = new Project(capital[i], profits[i]);

        }

        Array.Sort(projects, (p1, p2) => {

            return p1.Capital.CompareTo(p2.Capital);

        });

        return projects;

    }

}

Complexity: O(nlogn + klogn)

[LeetCode] N-Queens II

Problem: The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 9

Approach: This is classic backtracking problem. We will take a boolean 2D array of size n x n and we treat it like a chess board. Now at reach row starting from 0 to n in order, we will try to place queen at every possible column. When we see we can place queen at the last row safely, we can increase the number of solution by 1.

We can reduce the space by just taking 3 arrays one for columns of size n, and 2 for two diagonals of size 2n but as you see in the constraint n is always less than or equal to 9, we don't have to worry about it and make our solution complex.

Implementation in C#:

    public int TotalNQueens(int n)

    {

        if (n <= 1)

        {

            return n;

        }

        bool[,] board = new bool[n,n];

        return this.TotalNQueens(board, 0, n);

    }

    private int TotalNQueens(bool[,] board, int currRow, int n)

    {

        if (currRow == n)

        {

            return 1;

        }

        int result = 0;

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

        {

            if (this.CanPlaceQueen(board, currRow, i, n))

            {

                board[currRow, i] = true;

                result += this.TotalNQueens(board, currRow + 1, n);

                board[currRow, i] = false;

            }

        }

        return result;

    }

    private bool CanPlaceQueen(bool[,] board, int row, int col, int n)

    {

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

        {

            if (board[i,col])

            {

                return false;

            }

        }

        int r = row, c = col;

        while (r >= 0 && c >= 0)

        {

            if (board[r, c])

            {

                return false;

            }

            --r;

            --c;

        }

        r = row;

        c = col;

        while (r >= 0 && c < n)

        {

            if (board[r, c])

            {

                return false;

            }

            --r;

            ++c;

        }

        return true;

    }

Complexity: O(n * !n)

[LeetCode] Snakes and Ladders

Problem: You are given an n x n integer matrix board where the cells are labeled from 1 to n^2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

• Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n^2)].
• This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
• If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
• The game ends when you reach the square n^2.

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

• For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return -1.

Example:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.

Approach: This is again a BFS problem. You can assume the snake and ladder board as a graph in which one cell is connected to another cell using snake or ladder. Now we need to find the path with minimum nodes from 1 to n*n, which is clearly a BFS problem.

Now the only thing we need is given the number next , we need to calculate it's cell (row, col).

Implementation in C#:

    public int SnakesAndLadders(int[][] board)

    {

        int n = board?.Length ?? 0;

        if (n == 0)

        {

            return 0;

        }

        int numOfSteps = 0;

        Queue<int> queue = new Queue<int>();

        queue.Enqueue(1);

        HashSet<int> visited = new HashSet<int>();

        while (queue.Count > 0)

        {

            ++numOfSteps;

            int size = queue.Count;

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

            {

                int curr = queue.Dequeue();

                for (int j = 1; j <= 6; ++j)

                {

                    int next = curr + j;

                    // Reached target

                    if (next == n * n)

                    {

                        return numOfSteps;

                    }

                    int row = 0;

                    int col = 0;

                    // Get cell of the given number next

                    this.GetNextRowColumn(next, n, ref row, ref col);

                    // if curr cell is snake or stair

                    if (board[row][col] != -1)

                    {

                        next = board[row][col];

                    }

                    // Reached target

                    if (next == n * n)

                    {

                        return numOfSteps;

                    }

                    if (!visited.Contains(next))

                    {

                        visited.Add(next);

                        queue.Enqueue(next);

                    }

                }

            }

        }

        return -1;

    }

    private void GetNextRowColumn(int next, int n, ref int row, ref int col)

    {

        row = next / n;

        col = next % n;

        if (col == 0)

        {

            col = n;

            --row;

        }

        col = row % 2 == 0 ? col - 1 : n - col;

        row = n - 1 - row;

    }

Complexity: O(n^2)

[LeetCode] Maximum Sum Circular Subarray

Problem: Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Example:

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3.

Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Input: nums = [-3,-2,-3]
Output: -2
Explanation: Subarray [-2] has maximum sum -2.

Approach: This problem is an extension of Kadanes max sum problem. If you see if the max sum exist in the middle than Kadanes approach is sufficient but if the max sum exist in circular subarray then we need to come up with a different approach.

Let's say the other special sum in case of circular array is called circular sum. How does it look like:

So if you see above array, you will understand

circular sum = sum of prefix of array + sum of suffix of array.

Now we just need to get max of all such calculated circular sums. To do it efficiently, we can prepopulate a rightmax array where rightmax[i] is the max sum of subarray nums[i...n-1]. With this we can easily calculate the max sum which is:

max_sum = MAX(kadanes_max_sum, max_circular_sum)

This is time efficient but if you see the above approach is iterating the input array twice and is using extra space in the form of rightmax array. Let's try to do better.

If you see max_circular_sum is equal to total sum of array - kadanes_min_sum. Right! We can calculate it using kadanes min sum with same approach by which we get kadanes max sum. It's just that we need to use Min instead of Max in the algo.

The only exception will be when all the numbers are negative which is easy to handle as in that case we just need to return kadanes_max_sum.

That's all!

Implementation in C#:

Approach 1: Using extra space:

    public int MaxSubarraySumCircular(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        if (length == 1)

        {

            return nums[0];

        }

        int[] rightMax = new int[length];

        rightMax[length - 1] = nums[length - 1];

        int suffixSum = nums[length - 1];

        for (int i = length - 2; i >= 0; --i)

        {

            suffixSum += nums[i];

            rightMax[i] = Math.Max(suffixSum, rightMax[i + 1]);

        }

        int maxSum = int.MinValue;

        int circularSum = int.MinValue;

        int currSum = 0;

        int prefixSum = 0;

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

        {

            currSum = Math.Max(currSum, 0) + nums[i];

            maxSum = Math.Max(maxSum, currSum);

            prefixSum += nums[i];

            if (i < length - 1)

            {

                circularSum = Math.Max(circularSum, prefixSum + rightMax[i + 1]);

            }

        }

        return Math.Max(maxSum, circularSum);

    }

Approach 2: No extra space:

       public int MaxSubarraySumCircular(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        if (length == 1)

        {

            return nums[0];

        }

        int maxSum = int.MinValue;

        int currMaxSum = 0;

        int currMinSum = 0;

        int minSum = int.MaxValue;

        int totalSum = 0;

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

        {

            currMaxSum = Math.Max(currMaxSum, 0) + nums[i];

            maxSum = Math.Max(maxSum, currMaxSum);

            currMinSum = Math.Min(currMinSum, 0) + nums[i];

            minSum = Math.Min(currMinSum, minSum);

            totalSum += nums[i];

        }

        return totalSum == minSum ? maxSum : Math.Max(maxSum, totalSum - minSum);

    }

Complexity: O(n)

[Google][CareerCup] Json parser library

Problem: JSON parsing is an essential toolkit in modern web development. Whether you are on the client side or server side, these methods need to be fast, efficient and dependable. But what if one day, suddenly, all of the JSON parser libraries went missing. You have been called upon to save us all from impending doom.

Please re-implement the standard json parsing methods in your favorite language and restore the world to it's natural order. Please note that to simplify the things key is a string and value is either a string or a json object. No other data type is allowed.

You need to write following methods:

1. Constructor: Make an object of the class.
2. Serialize: Returns the json string.
3. Deserialize: Save the json string in a data structure.

Example:

Input: ["JsonParser", "Deserialize("{a:{h:hat},b:{c:{f:fish,g:goat},d:doll},e:elephant,i:{j:jar, k:kite,l:lion}}")", Serialize()]
Output: [None, None, "{a:{h:hat},b:{c:{f:fish,g:goat},d:doll},e:elephant,i:{j:jar, k:kite,l:lion}}"]

Approach: This can be done using many DS like trees, dictionary/map but I am using Linked List here with child pointer. As for me it looks like a list, where if value is another list of key value pair then we can say it is child otherwise it's simple data stored in the node.

Each comma ',' says this is next node. With this thought just look at the implementation to understand the solution in more details.

Please note that I haven't tested it throroughly so there might be some corner cases where the below program will fail but the approach will remain same.

Implementation in C#:

public class ListNode

{

    public string Key {get; set;}

    public string Value { get; set; }

    public ListNode Next {get; set;}

    public ListNode Child {get; set;}

    public ListNode(string key)

    {

        this.Key = key;

    }

}

public class JsonParser

{

    public JsonParser()

    {

        this.head = null;

    }

    

    public void Deserialize(string str)

    {

        this.Clear();

        int currIndex = 1;

        this.head = this.DeserializeToList(str, ref currIndex);

    }

    

    private ListNode DeserializeToList(string str, ref int currIndex)

    {

        // Nothing to consume

        if (currIndex >= str.Length)

        {

            return null;

        }

        int keyIndex = str.IndexOf(":", currIndex);

        // No key exist means wrong input

        if (keyIndex == -1)

        {

            return null;

        }

        // Get key

        string key = str.Substring(currIndex, keyIndex - currIndex);

        // Create the node

        ListNode node = new ListNode(key);

        // First case when value is string

        if (str[keyIndex + 1] != '{')

        {

            int bracketIndex = str.IndexOf("}", keyIndex + 1);

            int commaIndex = str.IndexOf(",", keyIndex + 1);

            int valIndex = Math.Min(bracketIndex, commaIndex);

            if (valIndex == -1)

            {

                valIndex = bracketIndex;

            }

            string val = str.Substring(keyIndex + 1, valIndex - (keyIndex + 1));

            node.Value = val;

            currIndex = valIndex + 1;

        }

        // Second case when value is JsonObject, Need to initialize child

        else

        {

            currIndex = keyIndex + 2;

            node.Child = this.DeserializeToList(str, ref currIndex);

        }

        // In case of closing bracket there is no next node.

        if (str[currIndex - 1] == '}')

        {

            node.Next = null;

            ++currIndex;

        }

        // In case of comma there is a next node.

        else

        {

            node.Next = this.DeserializeToList(str, ref currIndex);

        }

        // Current node is properly initialized now

        return node;

    }

    

    public string Serialize()

    {

        return this.SerializeToStr(this.head);

    }

    

    private string SerializeToStr(ListNode node, bool isNext = false)

    {

        if (node == null)

        {

            return "";

        }

        // In case of next we don't need to wrap around brackets

        string str = isNext ? "" : "{";

        str += node.Key + ":";

        // If value is null means child is there so serialize it first before moving

        // to next

        if (node.Value == null)

        {

            str += this.SerializeToStr(node.Child);

        }

        else

        {

            str += node.Value;

        }

        // Go to next node

        if (node.Next != null)

        {

            str += ("," + this.SerializeToStr(node.Next, true));

        }

        str += isNext ? "" : "}";

        return str;

    }

    

    public void Clear()

    {

        this.head = null;

    }

    

    private ListNode head;

}

Complexity: O(n) for both serialize and deserialize

[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.