SDE - 2

You are given an array of ‘N’ integers and your task is to sort the array using the following operations.

In one operation you can select a sub-array of the array and sort it. The cost of performing such an operation will be the square of the length of the sub-array you are sorting.

You task is to find the minimum cost of sorting the whole array.

Example:-

You are given,
array ARR=[4,3,2,1] 

So, the output is 16 as we can take the sub-array [4,3,2,1](from index 0 to index 4) and sort it. So the total cost is 4*4 (16).    

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.

Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

For example:

[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.

You are given two strings BEGIN and END and an array of strings DICT. Your task is to find the length of the shortest transformation sequence from BEGIN to END such that in every transformation you can change exactly one alphabet and the word formed after each transformation must exist in DICT.

Note:

1. If there is no possible path to change BEGIN to END then just return -1.
2. All the words have the same length and contain only lowercase english alphabets.
3. The beginning word i.e. BEGIN will always be different from the end word i.e. END (BEGIN != END).

You are given a string 'STR' consisting of lowercase English letters. Your task is to return all permutations of the given string in lexicographically increasing order.

String A is lexicographically less than string B, if either A is a prefix of B (and A ≠ B), or there exists such i (1 <= i <= min(|A|, |B|)), that A[i] < B[i], and for any j (1 <= j < i) A[i] = B[i]. Here |A| denotes the length of the string A.

For example :

If the string is “bca”, then its permutations in lexicographically increasing order are { “abc”, “acb”, “bac”, “bca”, “cab”, “cba” }.

Note:

Given string contains unique characters.

Design Instagram type of app for photosharing. Mostly focussed on LLD

How does locking take place when multiple application stry to book same tickets in a movie show..Discussed similar techincal tradeoffs in modern applications.