SDE - Intern

You have been given a string ‘A’ consisting of lower case English letters. Your task is to find the length of the longest palindromic subsequence in ‘A’.

A subsequence is a sequence generated from a string after deleting some or no characters of the string without changing the order of the remaining string characters. (i.e. “ace” is a subsequence of “abcde” while “aec” is not).

A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.

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.

You have been given a binary tree with an integer value associated to each node. You are supposed to choose a subset of these nodes such that the sum of these chosen nodes is maximum. Keep in mind that no two of the chosen nodes must be adjacent to each other.

Note :

Two nodes are said to be adjacent to each other if they are directly connected to each other. This means that if a node is taken as part of the sum, then none of its children can be considered for the same and vice versa.

For example :

For the given binary tree

Nodes used in consideration for maximum sum such that no two of them are adjacent are highlighted. Maximum sum of nodes = 1 + 1 + 1 + 4 + 5 = 12.

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.