SDE - Intern

Greedy approach can be applied to solve this problem. We sort the start and end time pairs for each meeting on the basis of the end time. Then we compare if the next meeting's start time is greater than the previous meeting's end time. If the start time is greater, we can count this meeting and we increase our meeting counter otherwise this meeting can't take place. In this manner, we traverse through all the meeting pairs, comparing in a greedy fashion and checking if the meeting can take place or not.
Time Complexity : O(nlogn)

Concept of min heap can be applied here. In each iteration, we need to pick the rope with minimum length because the value picked first will be included in the final answer multiple times. Hence, for minimum cost, we pick the longer length ropes later. 
Approach :
First of all, build minHeap (priority queue) from the given array of rope length. 
In each iteration:
1) Extract two ropes with minimum length from the minHeap.
2) add the length of both the ropes to the cost. 
3) add the cost to the result and push the cost (sum of length of two ropes) again in the minHeap.
The final result will be the minimum cost.

The basic idea is to use modified pre-order traversal. In this modified pre-order traversal, we keep track of horizontal distance of the node being visited from the root. We also keep track of height of that node. During this traversal, we use an ordered map that stores node's horizontal distance as key and value as tuple (current node's value, current node's level) if the node being visited is the bottommost node seen at its horizontal distance. 
Algorithm :
1. Perform a preorder traversal to calculate the level of each node of the binary tree.
2. Consider a hash map and store the height into the map, where the key is the horizontal distance of the ith node and the value is a pair (p, q), where p is the value of the node and q is the height of the node.
3. For every node:
Add the node to the resultant map if it is the first node to have the current horizontal distance.
Else, if a node is already present for the particular distance, replace the previous node with the current node, if the node has a height greater than the previous node.

DFS can be used for serializing and de-serializing. Process root node and then make recursive calls for left and right child.
For serializing the tree into a list : 
1. If node is null, store -1 in list to denote a null link. Return. 
2. Store the data at current node in list.
3. Call function recursively for left and right subtrees.
4. Return the list.
If we serialize using preorder traversal, apply the same preorder procedure to recursively build the tree. Take the keys from the array one by one and build the tree accordingly. The de-serialize function takes two arguments, i.e., the list of values and an index.
1. The base case would be true either when index passed is out of bound or if the value at index position is -1, return NULL in that case. 
2.Create new node for storing current element.
3. Call function recursively for left and right subtrees.
4. Return the tree.

Using a virtual destructor, we can release the memory allocated by a derived class object or instance. In addition, we can delete instances of the derived class using a base class object pointer. The base class destructor uses the virtual keyword so that both the base class and the derived class destructor will be called at run time. However, the derived class will be called first and then the base class to free up the memory.