SDE - 1

You have been given a Binary Tree of distinct integers and two nodes ‘X’ and ‘Y’. You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y’.

The LCA of ‘X’ and ‘Y’ in the binary tree is the shared ancestor of ‘X’ and ‘Y’ that is located farthest from the root.

Note :

You may assume that given ‘X’ and ‘Y’ definitely exist in the given binary tree.

For example :

For the given binary tree

LCA of ‘X’ and ‘Y’ is highlighted in yellow colour.

You are given a Multilevel Linked List of integers, where in addition to the next pointer each node has a child pointer, which may or may not point to a separate list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the below figure. You are given the head of the first level of the list. Flatten the list so that all the nodes appear in a single-level linked list. You need to flatten the list in a way that all nodes at first level should come first, then nodes of the second level, and so on.

                FIGURE 1

Input for the above list is:
10 5 12 7 11 -1 4 20 13 -1 -1 -1 17 6 -1 -1 -1  2 -1 16 -1 9 8 -1 -1 -1 3 -1 19 15 -1 -1 -1 -1 -1

You are given an array of binary strings ‘arr’ of size ‘N’. Your task is to find out the maximum distance between the pair of strings.

The distance between two binary strings is defined as the sum of their lengths after removing the common prefix.

For example:

You are given ‘arr’ = [ “01011”,  “010110”, “0111”], Here the strings with the maximum distance between them are “010110” and  “0111”, where the prefix is “01”,  hence the maximum distance is  4 + 2 = 6. Hence the answer is 6.

You are given a 'Nx3' 2-D array 'Jobs' describing 'N' jobs where 'Jobs[i][0]' denotes the id of 'i-th' job, 'Jobs[i][1]' denotes the deadline of 'i-th' job, and 'Jobs[i][2]' denotes the profit associated with 'i-th job'.

You will make a particular profit if you complete the job within the deadline associated with it. Each job takes 1 unit of time to be completed, and you can schedule only one job at a particular time.

Return the number of jobs to be done to get maximum profit.

Note :

If a particular job has a deadline 'x', it means that it needs to be completed at any time before 'x'.

Assume that the start time is 0.

For Example :

'N' = 3, Jobs = [[1, 1, 30], [2, 3, 40], [3, 2, 10]].

All the jobs have different deadlines. So we can complete all the jobs.

At time 0-1, Job 1 will complete.
At time 1-2, Job 3 will complete.
At time 2-3, Job 2 will complete.

So our answer is [3 80].

Explain demand paging?

What do you mean by RTOS?

Design a data structure that satisfies the constraints of a Least Recently Used (LRU).

1. Get(int num): If the key exists, it will return the value of the key stored. Else, return -1.    
2. Put(int key, int value): If the key already exists, update the value of the key. Else add the key-value pair to the cache. If the number of keys is more than the capacity for this operation, delete the least recently key used. 

Example:

For the following input: 

4 2
2 1 4
1 1
1 4

We will initialize an empty LRU cache for the first operation with a maximum capacity of 2.
For the first operation, we need to add a key-value pair (1,4) to the cache.
For the second operation, we need to return the value stored for key 1, i.e., 4
For the third operation, we need to return -1, as we don't have any key 4 in the cache.

So, the final output will be: 
4  -1

A binary tree is a tree where each node has at most two children i.e left child and right child.

You are given a binary tree, where the structure of the node is as follow -:

class BinaryTreeNode {
 int data;      // Value of the node.
 BinaryTreeNode *left;  // Pointer to left child node.
 BinaryTreeNode *right; // Pointer to right child node.
 BinaryTreeNode *next;  // Pointer to next right node at same level. 
}

Your task is to connect all the adjacent nodes at the same level in the given binary tree. You can do this by populating each 'next' pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all the next pointers are set to NULL.

For Example:

Consider the figure shown below. The left part represents the initial binary tree and right part represents the binary tree after connecting adjacent nodes at the same level.

In the tree shown in the picture above -:
The ‘next’ pointer of the node having value 2 is connected to the node having value 3.
The ‘next’ pointer of the node having value 4 is connected to the node having value 5.
The ‘next’ pointer of the node having value 5 is connected to the node having value 6.
The ‘next’ pointer of nodes having value 1, 3, 6 will have a value NULL as there are no next right nodes in their cases.

Note:

1. The structure of the ‘Node’ of a binary tree is already defined. You should not change it.   
2. The root of the binary tree is known to you.  
3. There is at least one node in the given binary tree.
4. You may only use constant extra space.

You are given a string ‘st’, Your task is to find the length of the longest repeating subsequence such that two subsequences don’t have the same character at the same position.

For Example :

The given string st = AABCBDC.

As you can see there are two repeating longest subsequences “ABC” with the same character but different position. Therefore the required answer is ‘3’ as the length of “ABC” is 3.