SDE - Intern

You are given an array/list ARR consisting of N integers. Your task is to find the length of the longest decreasing subsequence.

A subsequence is a sequence of numbers obtained by deleting zero or more elements from the array/list, keeping the relative positions of elements same as it was in the initial sequence. A decreasing subsequence is a subsequence in which every element is strictly less than the previous number.

Note:

There can be more than one subsequences with the longest length.

For example:-

For the given array [5, 0, 3, 2, 9], the longest decreasing subsequence is of length 3, i.e. [5, 3, 2]

Note:

Try to solve the problem in O(N log N) time complexity.

Sushant is learning about palindromes. One day his teacher gave him a string ‘STR’ consisting of only the lowercase letters and asked him to modify the string in such a way that the string doesn’t contain any palindromic substring by replacing the minimum characters present in the given string. Sushant, although a brilliant student, needs your help.

Note:

A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as “madam” or “racecar”.

Example:

Given an ‘STR’: ‘aaaaaaa’ The minimum characters that will be replaced are 4. The string can be converted into ‘abcabca’.

Note:

Here are multiple possible answers, for example changing all the elements, but we have to find the minimum replacements possible.

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change for value V using coins of denominations from D. Print 0, if a change isn't possible.

There are 3 mislabeled jars, with apple and oranges in the first and second jar respectively. The third jar contains a mixture of apples and oranges. You can pick as many fruits as required to precisely label each jar. Determine the minimum number of fruits to be picked up in the process of labeling the jars.