Some Important Searching and Sorting Related Problems with Hints

 1. Sliding Window Maximum, Difficulty: Hard

First Read the problem statement. In this problem, we have given a window that size is 'K', every time we have to move this window from left to right and pick the largest number from the window.

Suppose, our given array is A = {1,3,-1,-3,5,3,6,7} and Window size, K = 3

The window moving look like this,

       Window position            Max

[1  3  -1] -3  5  3  6  7           3

 1 [3  -1  -3] 5  3  6  7           3

 1  3 [-1  -3  5] 3  6  7           5

 1  3  -1 [-3  5  3] 6  7           5

 1  3  -1  -3 [5  3  6] 7           6

 1  3  -1  -3  5 [3  6  7]          7

SO, the ans is, {3,3,5,5,6,7}
First, see we can't solve this problem using Bruteforce {1<=Array size<=10^5} method, we need to optimize this.

Before solving the problem, think that we already know the first largest value of the first window, Now how can we get the 2nd window largest, and so on.

If we have a Container that can find the largest value at the same time we can remove the first value of the current window and insert the last value of the next window then the problem will be solved.

Container? is it Multiset? Priority queue? Think.

2. Towers, Difficulty: Easy

Read the problem statement, we have given an array of integers. We have to build some towers in the order of the given array.

How the tower of numbers look like? the first element is maximum, then the second element is less than the previous element, and so on.

Obviously, we cant solve this problem using the brute force method.
Again for solving this problem, we need a container that can give the information of the existence of exactly greater value than the current value at the same time it can erase any number.

3. Josephus Problem I, Difficulty: Easy

Very famous problem. Given n peoples, currently, they are in a circle.
Every time we have to remove the 2nd person. Initially, counting starts from 1.

The First observation of solving this problem is we have to consider every time that current child-size is odd or even, then simply we can pass the alive list to the current child list.

4. Room Allocation - Medium

This Problem is really easy to understand. You have given N person's Comming and Leaving time. You have to calculate how many rooms can be used and which person can be used in which room(room id).

For solving this problem, we have to maintain their id, current entry time, current leaving time, and most important we have to sort them by their entry time. At the same time, we have to handle the last person leaving time so that we can compare it with the current person's entry time so that the current person can use the previous person's room or not.

Solvable with Nlog(N) complexity.
Better understanding see my code.