SDE - 1

Ninja and his friend are playing a game. They are having ‘N’ piles and each pile contains ‘A[i]’ amount of stones in it. Ninja will make the first move.

In each move, a player can choose any pile and remove any number of stones ( at least one ) from that pile. The player who cannot make a move loses the game.

Assuming both players play optimally, output 1 if Ninja wins the game and 0 if Ninja loses the game.

Example :

N = 3
A = [ 3, 4, 5 ]

Explanation : 

One of the optimal ways to play the game is : 

Ninja removes 3 stones from the first pile : [ 0, 4, 5 ].
Friend removes 3 stones from the second pile : [ 0, 1, 5 ].
Ninja removes 3 stones from the third pile : [ 0, 1, 1 ].
Friend removes 1 stone from the second pile : [ 0, 0, 1 ].
Ninja removes 1 stones from the third pile : [ 0, 0, 0 ].

Thus Ninja wins the game here.

Ninja Coin is a famous crypto-currency in Ninja Land. Ninja has an array/list ‘PRICE’ of size ’N’ where ‘PRICE[i]’ is the price of a Ninja Coin on an ith day in INR, where 0 <= 'i' <= N-1.

The span of the Ninja Coin price on an ith day is defined as the maximum number of consecutive days (starting from the ith day and going backward) for which the price of a Ninja Coin was less than or equal to its price at ith day.

Your task is to return an array/list of size ‘N’ where the ith integer is the span of Ninja Coin price on an ith day. Go through the example for more clarity.

For Example :

Let the price of Ninja Coin for 5 consecutive days is [4, 2, 3, 3, 7].

Then the span of Ninja Coin on the 0th day is 1 because we cannot move backward from day 0.

The span of Ninja Coin on the 1st day is 1 because the price on day 0 is 4 which is greater than 2, so the only day 1 is counted.

The span of Ninja Coin on the 2nd day is 2 because the price on day 2 and day 1 is less than or equal to 3 and then on day 0 price is 4 which is greater than 3, so we count day 2 and day 1.

The span of Ninja Coin on the 3rd day is 3 because the price on day 3, day 2, and day 1 is less than or equal to 3, and on day 0 price is 4 which is greater than 3, so we count day 3, day 2, and day 1.

The span of Ninja Coin on the 4th day is 5 because its value is higher than all previous days values.    

Thus you should return an array/list [1, 1, 2, 3, 5].

You are given a binary search tree of integers with N nodes. You are also given references to two nodes 'P' and 'Q' from this BST.

Your task is to find the lowest common ancestor(LCA) of these two given nodes.

The lowest common ancestor for two nodes P and Q is defined as the lowest node that has both P and Q as descendants (where we allow a node to be a descendant of itself)

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

For example:

'P' = 1, 'Q' = 3
tree = 2 1 4 -1 -1 3 -1 -1 -1,

The BST corresponding will be- 

Here, we can clearly see that LCA of node 1 and node 3 is 2.

Given a sequence of ‘N’ space-separated non-negative integers A[1],A[2],A[3],......A[i]…...A[n]. Where each number of the sequence represents the height of the line drawn at point 'i'. Hence on the cartesian plane, each line is drawn from coordinate ('i',0) to coordinate ('i', 'A[i]'), here ‘i’ ranges from 1 to ‘N’. Find two lines, which, together with the x-axis forms a container, such that the container contains the most area of water.

Note :

1. You can not slant the container i.e. the height of the water is equal to the minimum height of the two lines which define the container.

2. Do not print anything, you just need to return the area of the container with maximum water.

Example

For the above Diagram, the first red marked line is formed between coordinates (2,0) and (2,10), and the second red-marked line is formed between coordinates (5,0) and (5,9). The area of water contained between these two lines is (height* width) = (5-2)* 9 = 27, which is the maximum area contained between any two lines present on the plane. So in this case, we will return 3* 9=27.

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 two strings 'S' and 'T' of lengths 'N' and 'M' respectively. Find the "Edit Distance" between the strings.

Edit Distance of two strings is the minimum number of steps required to make one string equal to the other. In order to do so, you can perform the following three operations:

1. Delete a character
2. Replace a character with another one
3. Insert a character

Note:

Strings don't contain spaces in between.

He put me in different scenarios to get to know how did I reach and also know how I handled things.

Create a stack data structure that allows operations such as push (adding an element), pop (removing the top element), top (retrieving the top element), and also provides a way to retrieve the minimum element in constant time.

Implement the following public functions :

1. push(data) :
This function should take one argument of type integer. It pushes the element into the stack and returns nothing.

2. pop() :
It pops the element from the top of the stack and returns nothing.

3. top() :
It returns the element being kept at the top of the stack.

4.  getMin() :
It returns the smallest element present in the stack.

Operations Performed on the Stack:

Query-1(Denoted by an integer 1): Pushes integer data to the stack. (push function)

Query-2(Denoted by an integer 2): Pops the data kept at the top of the stack. (pop function)

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack. (top function)

Query-4(Denoted by an integer 4): Returns the smallest element present in the stack. (getMin() function)