SDE - 2

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.

You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to return the list of all pairs of elements such that each sum of elements of each pair equals 'S'.

Note:

Each pair should be sorted i.e the first value should be less than or equals to the second value. 

Return the list of pairs sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value should come first.

Given an unsorted array of integers, you have to move the array elements in a way such that all the zeroes are transferred to the end, and all the non-zero elements are moved to the front. The non-zero elements must be ordered in their order of appearance.

For example, if the input array is: [0, 1, -2, 3, 4, 0, 5, -27, 9, 0], then the output array must be:

[1, -2, 3, 4, 5, -27, 9, 0, 0, 0].

Expected Complexity: Try doing it in O(n) time complexity and O(1) space complexity. Here, ‘n’ is the size of the array.

You have been given a binary tree of 'N' nodes. Print the Spiral Order traversal of this binary tree.

For example

For the given binary tree [1, 2, 3, -1, -1, 4, 5, -1, -1, -1, -1]
    1
   / \
  2   3
     / \
    4   5

Output: 1 3 2 4 5

Design instagram

Ninja has to design a 2 players game Tic-Tac-Toe played on an ‘N’ * ‘N’ grid.

Ninja has to assume the following rules while playing the game:

This game is played between two people (Player 1 and Player 2). Player 1 chooses ‘X' and Player 2 chooses ‘O’ to mark their cells. A move is guaranteed to be valid and is placed on an empty block.

A player who successfully places 'N' of their marks in a horizontal, vertical, or diagonal row wins the game. Once a winning condition is reached, no more moves are allowed.

As Ninja is busy planning his strategy, he asks you for help. Your task is to complete the function ‘move(row, col, player)’ where ‘row’ and ‘col’ represent the current row and column of the grid ‘player’ P (either 1 or 2) chooses to place his sign.

The function must return an integer which is either 0, 1, and 2 representing:

0: No one wins.
1: Player 1 wins.
2: Player 2 wins.

Example:

Let us assume if ‘N’ = 3 and player 1 places ‘X’ and player 2 places ‘O’ on the board.

Design debugger