SDE - Intern

You are given string S of length N, and an integer K. Your task is to find the length of the longest substring that contains at most K distinct characters.

You have been given an integer array/list(ARR) of size N which contains numbers from 0 to (N - 2). Each number is present at least once. That is, if N = 5, the array/list constitutes values ranging from 0 to 3 and among these, there is a single integer value that is present twice. You need to find and return that duplicate number present in the array.

Note :

Duplicate number is always present in the given array/list.

Ninja is given a binary string ‘S’ of size ‘N’ by his friend, the task is to check if the binary string ‘S’ can be sorted in decreasing order by removing any number of the non-adjacent characters. Since Ninja is busy with some work he is asking for your help. Can you help him?

Note:

A binary string is a string in which all characters are either ‘1’ or ‘0’.

The order is not strictly decreasing.

You are given a string ‘str’ of ‘N’ lowercase alphabets. Your task is to check whether it is possible to split the given string into three non-empty substrings such that one of them is a substring of another two.

For example:

‘str’ = 'abcabab', we can split this string into 3 string a, b, c as a = 'abc', b = 'ab',  c = 'abc', we can clearly see that b is a substring of both a and c.

Note:

A substring is a contiguous sequence of characters within a string. For example 'ab', 'b' and 'abc' are the substring of string 'abc', but 'ac' is not a substring of 'abc'. 

A non-empty substring means a substring with a size greater than 0.

This puzzle usually seems like a tough one to answer, but solving it once makes one realize that the procedure was actually simple. If the candidate pulls out 2 red balls, he replaces them with a blue ball. 
On the other hand, if he draws one red and one blue, it is replaced with a red one. This implies that the red ball would always be in odd numbers, whether the candidate removes 2 together, or removes 1 while adding 1. This also indicates that the last ball to stay in the bag would be a red one. The interviewer is merely testing the approach the candidate applies in solving this common analytics puzzle.

The approach here is to initially fill the 5L jug with water and empty the same into the 4L jug. The 5L jug will be left with 1L of water, which is poured into the bucket. Meanwhile, empty the 4L jug.

The above step is repeated, so that the bucket now is filled with 2L of water. Finally, fill the 5L jug with water and empty the same into the bucket. The bucket will now have 7L of water, as you add % L directly to the previously collected 2L of water in the bucket.