SDE - Intern

You have been given a square chessboard of size ‘N x N’. The position coordinates of the Knight and the position coordinates of the target are also given.

Your task is to find out the minimum steps a Knight will take to reach the target position.

Example:

knightPosition: {3,4}
targetPosition: {2,1}

The knight can move from position (3,4) to positions (1,3), (2,2) and (4,2). Position (4,2) is selected and the ‘stepCount’ becomes 1. From position (4,2), the knight can directly jump to the position (2,1) which is the target point and ‘stepCount’ becomes 2 which is the final answer. 

Note:

1. The coordinates are 1 indexed. So, the bottom left square is (1,1) and the top right square is (N, N).

2. The knight can make 8 possible moves as given in figure 1.

3. A Knight moves 2 squares in one direction and 1 square in the perpendicular direction (or vice-versa).

You have been given a string ‘A’ consisting of lower case English letters. Your task is to find the length of the longest palindromic subsequence in ‘A’.

A subsequence is a sequence generated from a string after deleting some or no characters of the string without changing the order of the remaining string characters. (i.e. “ace” is a subsequence of “abcde” while “aec” is not).

A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.

You have been given a binary tree of integers with N number of nodes. Your task is to check if that input tree is a BST (Binary Search Tree) or not.

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.

Example :

Answer :

Level 1: 

All the nodes in the left subtree of 4 (2, 1, 3) are smaller 
than 4, all the nodes in the right subtree of the 4 (5) are 
larger than 4.

Level 2 :

For node 2:
All the nodes in the left subtree of 2 (1) are smaller than 
2, all the nodes in the right subtree of the 2 (3) are larger than 2.
For node 5:
The left and right subtrees for node 5 are empty.

Level 3:

For node 1:
The left and right subtrees for node 1 are empty.
For node 3:
The left and right subtrees for node 3 are empty.

Because all the nodes follow the property of a binary search tree, the above tree is a binary search tree.

Given a complete binary tree, you are supposed to return the number of nodes in the given tree.

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

For example:

For the binary trees in the image below.

The left tree in the image is not a complete binary tree that’s why it is invalid and the right tree in the image is a valid complete binary tree which contains total 6 nodes.

Implement a Stack Data Structure specifically to store integer data using two Queues.

There should be two data members, both being Queues to store the data internally. You may use the inbuilt Queue.

Implement the following public functions :

1. Constructor:
It initializes the data members(queues) as required.

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

3. pop() :
It pops the element from the top of the stack and, in turn, returns the element being popped or deleted. In case the stack is empty, it returns -1.

4. top :
It returns the element being kept at the top of the stack. In case the stack is empty, it returns -1.

5. size() :
It returns the size of the stack at any given instance of time.

6. isEmpty() :
It returns a boolean value indicating whether the stack is empty or not.

Operations Performed on the Stack:

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

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

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack but doesn't remove it, unlike the pop function. (top function)

Query-4(Denoted by an integer 4): Returns the current size of the stack. (size function)

Query-5(Denoted by an integer 5): Returns a boolean value denoting whether the stack is empty or not. (isEmpty function)

Example

Operations: 
1 5
1 10
2
3
4

Enqueue operation 1 5: We insert 5 at the back of the queue.
  Queue: [5]

Enqueue operation 1 10: We insert 10 at the back of the queue.
  Queue: [5, 10]

Dequeue operation 2: We remove the element from the front of the queue, which is 5, and print it.
  Output: 5
  Queue: [10]

Peek operation 3: We return the element present at the front of the queue, which is 10, without removing it.
  Output: 10
  Queue: [10]

IsEmpty operation 4: We check if the queue is empty.
  Output: False
  Queue: [10]