SDE - 2

Your friends gifted you a lot of things on your birthday, and now it's your turn to give some return gifts to them. You went to a gift store and decided to buy some Binary Search Trees (BST).

There is no salesperson in the store. So you are supposed to guess the price of a given BST, which is the minimum value in its nodes.

You are given a Binary Tree ‘root’. The given Binary Tree may or may not be a Binary Search Tree(BST) itself. Your task is to find the maximum sum of node values of any subtree that is a Binary Search Tree(BST).

Binary Search Tree is defined as follows:

1) If the left subtree exists it should contain only nodes with values less than the current node's value.

2) If the right subtree exists it should contain only nodes with values greater than the current node's value.

3) Both the left and right subtrees should also be Binary Search Tree.

Example :

For the above binary tree, the BST with the maximum possible sum is marked with RED colour, the sum of this BST is equal to 6.

You are given an integer array ‘arr’ of size ‘N’. Your task is to find the maximum difference between two consecutive elements in the sorted form of the array ‘arr’.

If the ‘arr’ contains less than two elements, return 0.

For example:

You are given arr = {1, 3, 8, 6, 7}, then our answer will be 3. 
Sorted form of arr = {1, 3, 6, 7, 8}. The maximum absolute difference between two consecutive elements is 6 - 3 = 3, which is the correct answer.

You are given a 2D matrix 'ARR' (containing either ‘0’ or ‘1’) of size 'N' x 'M', where each row is in sorted order.

Find the 0-based index of the first row with the maximum number of 1's.

Note :

If two rows have the same number of 1’s, return the row with a lower index.

If no row exists where at-least one '1' is present, return -1.

Example:

Input: ‘N’ = 3, 'M' = 3
'ARR' = 
[     [ 1,  1,  1 ],
      [ 0,  0,  1 ],
      [ 0,  0,  0 ]   ]

Output: 0

Explanation: The 0th row of the given matrix has the maximum number of ones.

You are given an array/list 'prices' where the elements of the array represent the prices of the stock as they were yesterday and indices of the array represent minutes. Your task is to find and return the maximum profit you can make by buying and selling the stock. You can buy and sell the stock only once.

Note:

You can’t sell without buying first.

For Example:

For the given array [ 2, 100, 150, 120],
The maximum profit can be achieved by buying the stock at minute 0 when its price is Rs. 2 and selling it at minute 2 when its price is Rs. 150.
So, the output will be 148.

After years of research, Ninja is finally able to invent the time machine, and now he is back to the good old days when T9 keypads were being used in mobile phones.

Being a curious person, Ninja wants to find out all possible strings that can be formed by pressing the keys of the phone.

Formally, you are given a string S, that consists of digits from 2-9 (both inclusive), your task is to find out all the possible strings that can be formed from the input string by mapping the digits to the letters as in a T9 keypad. Then, print the strings in a lexicographically sorted order.

For Example:

If S = “34”, then all the possible letters that can be formed from string S are {“dg”, “dh”, “di”, “eg”, “eh”, “ei”, “fg”, “fh”, “fi”}.

The goal of this exercise is to design a system like Google Search, which accepts a query string and returns a set of documents to the user. We are given the following: a UI that accepts the query and can make an RPC out to another server, which will accept a query and return a list of the top 10 documents related to it. The goal is to focus on the overall system architecture, not any specifics of ranking or information retrieval.