SDE - 1

In computing, a page fault is an exception for the memory management unit (MMU) when a process accesses a memory page without proper preparations.

Page replacement algorithm is needed to decide which page needs to be replaced when the new page comes in. Whenever a new page is referred to and is not present in memory, the page fault occurs, and the Operating System replaces one of the existing pages with a newly needed page.

You have given a sequence of pages in an array ‘Pages’ of length ‘N’ and memory capacity ‘C’. You have to find the number of page faults using the Least Recently Used (LRU) Algorithm. Initially, memory doesn't contain any pages.

For example:

'N' = 7, 'C' = 4, pages = [1, 2, 1, 4, 2, 3, 5].

For the first four pages, memory allocated with four pages, {1, 2, 1, 4}, page fault = 3.

For fifth, page number 2 is required, which is already present, page fault = 3.

Then, page number 3 is required, replaces LRU 2, page fault = 4.

Then, page number 5 is required, replaces LRU 1, page fault = 5.

The total page fault is 5.

You live in a Ninja town which is in the form of a N * M grid. In this town, people travel from one place to another by jumping over the buildings which are present in each cell of the grid. It is Christmas eve, and Santa wants to give gifts and chocolates to the kids who live in the building which is present at the cell (N - 1, M - 1). Initially, Santa is present on cell (0, 0). Since Santa is in a hurry, help him find a path from starting point to the endpoint with the least amount of time.

The Santa may go only from one building to any of its adjacent buildings which is present either to the right or to the bottom or bottom right cell i.e. if the current position is (x, y), he may go to (x + 1, y + 1) or (x + 1, y) or (x, y + 1) given that the new coordinates are in the grid. The time taken to reach from one building to another is equal to the absolute difference between the heights of buildings.

Note:

1. The heights of the buildings are positive.
2. Santa starts from the cell (0, 0) and he has to reach the building (N - 1, M - 1).
3. Santa cannot leave the grid at any point of time.

You are given ‘N’ cubes in an array ‘ARR’ in a certain order, and your task is to build towers using them. Whenever two cubes are on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower or begin a new tower. What is the minimum possible number of towers?

For example:

Given ‘N’ = 3, ‘ARR’[] = 3, 2, 1.
The answer will be one because you can stack one over two over 3. Therefore only these can be inserted in the same tower.

You have been given an array/list 'HEIGHTS' of length ‘N. 'HEIGHTS' represents the histogram and each element of 'HEIGHTS' represents the height of the histogram bar. Consider that the width of each histogram is 1.

You are supposed to return the area of the largest rectangle possible in the given histogram.

For example :

In the below histogram where array/list elements are {2, 1, 5, 6, 2, 3}.

The area of largest rectangle possible in the given histogram is 10.

Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.

Example :

Merge Sort Algorithm -

Merge sort is a Divide and Conquer based Algorithm. It divides the input array into two-parts, until the size of the input array is not ‘1’. In the return part, it will merge two sorted arrays a return a whole merged sorted array.

The above illustrates shows how merge sort works.

Note :

It is compulsory to use the ‘Merge Sort’ algorithm.