SDE - Intern

Given two strings, 'S' and 'T' with lengths 'M' and 'N', find the length of the 'Longest Common Subsequence'.

For a string 'str'(per se) of length K, the subsequences are the strings containing characters in the same relative order as they are present in 'str,' but not necessarily contiguous. Subsequences contain all the strings of length varying from 0 to K.

Example :

Subsequences of string "abc" are:  ""(empty string), a, b, c, ab, bc, ac, abc.

You have been given the start and end times of 'N' intervals. Write a function to check if any two intervals overlap with each other.

Note :

If an interval ends at time T and another interval starts at the same time, they are not considered overlapping intervals.

You have been given a sorted (lexical order) dictionary of an alien language.

Write a function that returns the order of characters as a string in the alien language. This dictionary will be given to you as an array of strings called 'dictionary', of size 'N'.

Example :

If the dictionary consists of the following words:-
["caa", "aaa", "aab"], and 'K' is 3.

Then, the order of the alphabet is -
['c', 'a', 'b']

Note:

If the language consists of four letters, the four letters should be the starting four letters of the English language. 

However, their order might differ in the alien language.

Given a string (STR) of length N, you have to create a new string by performing the following operation:

Take the smallest character from the first 'K' characters of STR, remove it from STR and append it to the new string.

You have to perform this operation until STR is empty.

 Note:

The input string(STR) will not contain any spaces.

Assume that all characters in STR are lower case letters.

If characters less than 'K' remain, then append them in a sorted way to the new string.

Example:

Let the input string be "edcba" with K = 4.

Let the new string to be formed is initially empty, newString = "".
The first set of 4 characters are, ('e', 'd', 'c', 'b')
Out of these 4 characters, the smallest one is 'b' and hence we add it to the newString and it becomes, 
newString = "b"

The next set of 4 characters are, ('e', 'd', 'c', 'a')
Out of these 4 characters, the smallest one is 'a' and hence we add it to the newString and it becomes, 
newString = "ba"

Now we are left with "edc" and since we can't get a window of size 4, we sort them in the increasing order and append them to the newString.

Hence, newString thus formed will be "bacde".

Consider a pipe of length L. The pipe has N water droplets at N different positions within it. Each water droplet is moving towards the end of the pipe(x=L) at different rates.

When a water droplet mixes with another water droplet, it assumes the speed of the water droplet it is mixing with. Determine the no of droplets that come out of the end of the pipe.

Discussion on project.

What is black box and white box testing?
Bubble sort ?
Linear sorting ?