1st Question:

Find the maximum number of overlapping windows in a set of windows. I.e.

1 --- 10
2 --- 8
3 --- 4

Answer would be 2 ( 3 --- 4 window is overlapped by all the windows, and its length is 2)

This one I solved by sorting by the beginning of the windows and keeping track of the minimum value of the ends of the windows, and also the max overlapping windows so far. If the number of overlapping windows was the maximum, I would set the answer to be the length of the window. O(nlogn) complexity. Failed 2 corner cases that I was not able to look at. Moved to the next question. Not a good/detailed explanation but if you are really interested I will try to clarify any questions.

2nd Question:

2 operations: INSERT and VIEW

INSERT, 'milk', '4' is an example of insert, where milk is the name of the item and 4 is the price of the item

VIEW will view whatever item # the user is on, when the list of items is sorted from cheapest to most expensive, and if items are the same price, alphanumerically ascending. So for example, the first VIEW will view the 1st cheapest item, second VIEW will view the 2nd cheapest item, etc.

The interesting case is say you insert items with prices

3, 4

calling view will view 3, as it is the cheapest. Then if you insert after the fact

1, 5

the new sorted list of items will be

1, 3, 4, 5

and calling view will yield '3' again, since we are now looking for the 2nd cheapest item

I could not figure out a solution that was considerably faster than just sorting the list of items every time you need to view and then returning the kth element.

I thought about it for a long time and ended up just trying to do something with heaps, where I keep a maxHeap of size k with the top k cheapest elements, and a minHeap with the rest of the items. Then when inserting items, I rebalance and make sure that the maxHeap maintains size k and put the rest in minHeap. This seemed like there would be more cases where it is faster than simply resorting the list each time you add items, but the time complexity is generally the same (O(vnlogn), where v is the number of views and n is the size of the array at the time of viewing).

I was not able to complete my idea anyway as I thought on it for too long and started coding it too late.

Any better solutions are much appreciated! I still am not quite sure the correct solution to the 2nd one, and improvements on the first would be nice.