SDE - Intern

This problem can be solved as follow:
For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such an area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate the area with ‘x’ as the smallest bar? We need to know the index of the first smaller (smaller than ‘x’) bar on the left of ‘x’ and the index of the first smaller bar on the right of ‘x’. Let us call these indexes ‘left index’ and ‘right index’ respectively.
We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from the stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as the smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and the index of the previous item in the stack is the ‘left index’. Following is the complete algorithm.

1) Create an empty stack.

2) Start from the first bar, and do the following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1.
……a) If the stack is empty or hist[i] is higher than the bar at top of the stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of the stack, then keep removing the top of the stack while the top of the stack is greater. Let the removed bar be hist[tp]. Calculate the area of the rectangle with hist[tp] as the smallest bar. For hist[tp], the ‘left index’ is the previous (previous to tp) item in the stack, and the ‘right index’ is ‘i’ (current index).

3) If the stack is not empty, then one by one remove all bars from the stack and do step 2.b for every removed bar.

I solved this problem using the concept of connected components.

If we draw a graph (with intervals as nodes) that contains undirected edges between all pairs of intervals that overlap, then all intervals in each connected component of the graph can be merged into a single interval.

Algorithm
With the above intuition in mind, we can represent the graph as an adjacency list, inserting directed edges in both directions to simulate undirected edges. Then, to determine which connected component each node is in, we perform graph traversals from arbitrary unvisited nodes until all nodes have been visited. To do this efficiently, we store visited nodes in a Set, allowing for constant time containment checks and insertion. Finally, we consider each connected component, merging all of its intervals by constructing a new Interval with start equal to the minimum start among them and end equal to the maximum end.

This algorithm is correct simply because it is basically the brute force solution. We compare every interval to every other interval, so we know exactly which intervals overlap. The reason for the connected component search is that two intervals may not directly overlap, but might overlap indirectly via a third interval.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n−1 such centers.

You might be asking why there are 2n−1 but not n centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have an even number of letters (such as "abba") and their center is between the two 'b's.

time complexity: O(n^2)

I wrote the code for the same using Bubble Sort and wrote a compare function according to the new alphabetical order. The interviewer then asked me to explain the time complexity of the sorting algorithm and also a few other questions related to other sorting algorithms like which are better in which scenarios etc…

I used the hashing concept in the compare function and an array for the same, he then asked me to write code without using any extra space and asked me to explain time and space complexity.