SDE - 1

Gary has a sequence 'ARR', consisting of 'N' integers.

We'll call a sequence ARR[i],  ARR[i+1], ..., ARR[j] where 1  ≤  i  ≤  j  ≤  N a subsegment of the sequence ARR. The value (j - i + 1) denotes the length of the subsegment.

Your task is to find the longest subsegment of ARR, such that it is possible to change at most one number (change one number to any integer you want) from the subsegment to make the subsegment strictly increasing.

You need to return the length of the maximum subsegment that you can find by changing only one integer in the given sequence.

You are given a string 'STR' containing lowercase English letters from a to z inclusive. Your task is to find all non-empty possible subsequences of 'STR'.

A Subsequence of a string is the one which is generated by deleting 0 or more letters from the string and keeping the rest of the letters in the same order.

You are the HR of the Ninja team and planning to hire ‘M’ candidates out of ‘N’ candidates to form a paid group. The candidates have been evaluated on the basis of their skills and have been asked for their minimum salary expectations. So, you are given two arrays, ‘SKILL’ and ‘EXPECTED_SALARY’, where ‘SKILL[i]’ and ‘EXPECTED_SALARY[i]’ represent the skill and minimum salary expectation of ‘i-th’ candidate, respectively. You have to consider the following two rules for hiring a group of ‘M’ candidates:

1) Every candidate in the paid group should be paid in the ratio of their skill compared to other candidates in the paid group.
2) The minimum salary expectation of every candidate in the paid group should be fulfilled.

You have to return the minimum amount of money required to hire ‘M’ candidates as per the above-mentioned rules.

Note:

Answers which are within the range 10^-6 of the correct answer will be considered correct.

You are given a binary search tree of integers with N nodes. You are also given references to two nodes 'P' and 'Q' from this BST.

Your task is to find the lowest common ancestor(LCA) of these two given nodes.

The lowest common ancestor for two nodes P and Q is defined as the lowest node that has both P and Q as descendants (where we allow a node to be a descendant of itself)

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.

For example:

'P' = 1, 'Q' = 3
tree = 2 1 4 -1 -1 3 -1 -1 -1,

The BST corresponding will be- 

Here, we can clearly see that LCA of node 1 and node 3 is 2.

You have given a URL id – 'N' consisting of only digits. Your task is to generate a short URL for the given URL id.

To generate a short URL, you need to convert the given URL id to 62 base number where digits of the number are:[“0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ”] i.e “0” corresponds to 0, “a” corresponds to 10, “Z” corresponds to 61, and “10” corresponds to 62, “11” corresponds to 63, and so on….

Follow Up:

Can you solve this in logarithmic time and space complexity?