SDE - Intern

You have been given 3 integers 'A', 'B', 'C' which are the coefficients of the quadratic equation (AX^2 + BX + C = 0). Your task is to find the real roots of the quadratic equation or report if no real roots exist (return a pair of -1).

For example:

Let’s consider the equation X^2 + 2X + 1 = 0 . We can see that the quadratic equation has no real roots. So we return a pair of -1 i.e. [-1, -1].

We can consider the equation X^2 - 5X - 6 = 0. As depicted from the equation the value of 'A' would be 1, 'B' would be -5 and 'C' would be -6. We can see that this equation has two distinct roots -2 and -3. Hence we return an array/sequence containing -2 and-3.

Note:

1. If the equation has repeated roots, return the roots twice.
2. If there are imaginary roots, return -1 twice.
3. If the root is not an integer, return the greatest integer value less 
than the root.

You are given two strings 'str1' and 'str2'. Find the minimum operations required to convert str1 into str2.

An Operation is defined as:

A character from an index of a string(str1) is put at the end of it, is defined as a single operation.

 Note :

You cannot perform any operation on the string, str2.

This problem was also revolved around some story but soul idea was there were several intervals given in form l to r. We need to merge the intersecting intervals and tell the number of intervals left after merging. Eg. (1, 5), (9, 15), (2, 6), (7, 8) answer will be 3 as we will have (1, 6), (7, 8), (9, 15).

You have been given a binary tree of integers. You have to return all the diagonal paths of the binary tree. A diagonal path is one in which all the nodes pass through -1 slope line.

A binary tree is a tree in which each parent node has at most two children.

Note:

Order of return of diagonal path’s array/vector: The rightmost diagonal path must come first, and so on.
Every parent node comes first then the child node. In other words, return the diagonal element from top to bottom.

Example

Consider the given binary tree.

There are 4 diagonal paths:
1 3 6
2 5 9
4 8
7
You need to return ‘1 3 6 2 5 9 4 8 7’.

Let's consider this example

Diagonal paths are:
1 3 6
2 5
4

You need to return ‘1 3 6 2 5 4’.

You are given a sequence array 'ARR' of ‘N’ integers. For each ARR[i] where 0 <= ‘i’ < 'N' , your task is to find the number of Binary search trees(BST) possible with elements of sequence ARR as nodes and ARR[i] as the root node.

The answer could be very large,so output your answer modulo (10 ^ 9 + 7). Also, use modular division when required.

For Example:

Let the sequence be 1, 4, 5, 6, 7 then return 14 5 4 5 14 i.e when 1 is the root node the number of BSTs possible is 14. Similarly, when 4 is the root node the number of BST’s possible is 5. In a similar way, we calculate the number of BST’s possible for the remaining elements of the sequence.

Note:

1. Consider 0 based Indexing.

2. A Binary Search Tree is a special kind of tree in which each node of the tree has at most 2 children and for every node, the value of nodes of the left subtree of any node is less than the current node and value of nodes of the right subtree are greater than the current node. 

Given two variables ‘X’ and ‘Y’. Your task is to swap the number without using a temporary variable or third variable.

Swap means the value of ‘X’ and ‘Y’ must be interchanged. Take an example ‘X’ is 10 and ‘Y’ is 20 so your function must return ‘X’ as a 20 and ‘Y’ as a 10.

Next, she jumped to my very small project of Line Following Bot and we discussed it’s working.

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).

She said I think it’s already been 40 minutes, So I should leave you and she asked me to ask questions to her. I asked her that we learn these DS and Algo. How we are going to use these in real-life projects. She said now you have raised problems for yourself, I will ask you 2 more questions. The whole conversion was very light and friendly. She asked problems related to developing products.
She asked me to make an ATM, that was a simple implementation taking care of some constraints. Then she asked me to design an algorithm for TinyURL conversion from normal URLs and vice-versa. I explained solutions using a polynomial hash. PS. she just wanted to hear the solution. I don’t have to code these problems.
She directed these solutions and said she this is how you use DS Algo in developing products and that’s All.