SDE - 1

You are appointed a critical role to infiltrate the enemy base and steal the information. The enemy base is in the form of a BST and has ‘N’ rooms, where each room denotes a node in BST. All the rooms have a distinct number assigned, say ‘X’. Your task is to raid all the rooms whose number lies in the range [L, R]. After the raid, you have to report the number of rooms you raided.

A BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

                         Example of a BST

You have been given an array 'ARR' of ‘N’ integers. You have to return the minimum number of jumps needed to reach the last index of the array i.e ‘N - 1’.

From index ‘i’, we can jump to an index ‘i + k’ such that 1<= ‘k’ <= ARR[i] .

'ARR[i]' represents the maximum distance you can jump from the current index.

If it is not possible to reach the last index, return -1.

Note:

Consider 0-based indexing.

Example:

Consider the array 1, 2, 3, 4, 5, 6 
We can Jump from index 0 to index 1
Then we jump from index 1 to index 2
Then finally make a jump of 3 to reach index N-1

There is also another path where
We can Jump from index 0 to index 1
Then we jump from index 1 to index 3
Then finally make a jump of 2 to reach index N-1

So multiple paths may exist but we need to return the minimum number of jumps in a path to end which here is 3.

You are given an arbitrary binary tree, a node of the tree, and an integer 'K'. You need to find all such nodes which have a distance K from the given node and return the list of these nodes.

Distance between two nodes in a binary tree is defined as the number of connections/edges in the path between the two nodes.

Note:

1. A binary tree is a tree in which each node has at most two children. 
2. The given tree will be non-empty.
3. The given tree can have multiple nodes with the same value.
4. If there are no nodes in the tree which are at distance = K from the given node, return an empty list.
5. You can return the list of values of valid nodes in any order. For example if the valid nodes have values 1,2,3, then you can return {1,2,3} or {3,1,2} etc.

Example :

Consider this tree above. The target node is 5 and K = 3. The nodes at distance 1 from node 5 are {2}, nodes at distance 2 from node 5 are {1, 4} and nodes at distance 3 from node 5 are {6, 3}.

You are given a non-decreasing array 'arr' consisting of 'n' integers and an integer 'x'. You need to find the first and last position of 'x' in the array.

Note:

1. The array follows 0-based indexing, so you need to return 0-based indices.
2. If 'x' is not present in the array, return {-1 -1}.
3. If 'x' is only present once in the array, the first and last position of its occurrence will be the same.

Example:

Input:  arr = [1, 2, 4, 4, 5],  x = 4

Output: 2 3

Explanation: The given array’s 0-based indexing is as follows:
 1      2     4     4     5
 ↓      ↓     ↓     ↓     ↓
 0      1     2     3     4

So, the first occurrence of 4 is at index 2, and the last occurrence of 4 is at index 3.

You have been given a string 'S' which only consists of lowercase English-Alphabet letters. Your task is to find the shortest (minimum length) substring from 'S' which contains all the characters of 'S' at least once.

Note:

If there are more than one substring with the shortest length, then find one which appears earlier in the string ‘S’ i.e. substring whose starting index is lowest.

For example:

If the given string ‘S’ = "abcba", then the possible substrings having all the characters of ‘S’ at least once and of minimum length are "abc" and "cba". 

As "abc" starts with a lower index (i.e. 0, "cba" starts with index 2), we will return the string "abc" as our shortest substring that contains all characters of 'S'.

Design a data structure to implement ‘N’ stacks using a single array of size ‘S’. It should support the following operations:

push(X, M): Pushes an element X into the Mth stack. Returns true if the element is pushed into the stack, otherwise false.

pop(M): Pops the top element from Mth Stack. Returns -1 if the stack is empty, otherwise, returns the popped element.

Two types of queries denote these operations :

Type 1: for push(X, M) operation.
Type 2: for pop(M) operation.

Given a DAG(direct acyclic graph), return the Topological Sorting of a given graph.

Asked about scheduling algorithms, then he said we have to implement portal for covid vaccination, which scheduling algorithm should you use? I told him first come first serve. Then he said the vaccination is based on age group I should give first priority to 60+ then 45 to 60 and last priority to 18 to 45 people. What algorithm should we use now?

He asked me to write one SQL query.
Given an Employee table with employeeid departmentid and salary
Department table with departmentid and DepartmentName
Write a quey to list the sum of salary paid by each department (Result should have DepartmentName and Salary columns)

He asked me some situation based questions like have you ever done something extraordinary in your current org.

Tell me a situation where you went extra miles in order to meet the client requirements

Given a string, representing a chemical formula, return the count of each atom.

An atomic element always starts with an uppercase character, then zero or more lowercase letters follow, representing the name.

One or more digits representing that element's count may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.

Two formulas can be concatenated together to produce another formula. For example, H2O2He3Mg4 is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas.

Given a formula, return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

Note :

The given formula consists of English alphabets, digits, ‘(‘ and ’)’.

The given formula is always valid.