SDE - 1

You are given a string ‘str’, you need to find the longest repeating and non-overlapping substring in the given string.

A substring of a string can be defined as a contiguous subsequence of that string. In other words, a string X is said to be a substring of the string S if X = S[a...b] = S[a]S[a+1]…..S[b] and 0 <= a <= b <= len(S) (0-based indexing).

You can return any such substring if more than one such substring exists in the string. If there is no such substring, return -1.

Note:

1. Repeating substrings in a string means those substrings which occur more than once in a string. For example, in the string “abaaba”, substrings “a”, “b”, “ab”, “ba”, “aba” are repeating.

2. Two substrings are called Non-overlapping substrings, if the intersection of all the indices of first substring i.e. [L1, R1] where L1 and R1 are the starting and ending index of the first substring respectively, and indices of the second substring i.e. [L2, R2] where L2 and R2 are the starting and ending indices respectively of the second substring, is NULL.

3. For example, in the string “abaaba”, two non-overlapping strings are “ab” lying in the interval [0, 1] (0-based indexing) and “aba” lying in the interval [3, 5] (0-based indexing). 

You are given a tree(root 0) with N vertex having N - 1 edges. You are also given an array ‘QUERY’ of size ‘Q’, where each query consists of an integer that denotes a node. You have to print the xor of all the values of nodes in the sub-tree of the given node.

Note:

Here XOR denotes the bitwise operator (^).

You have been given weights and values of ‘N’ items. You are also given a knapsack of size ‘W’.

Your task is to put the items in the knapsack such that the total value of items in the knapsack is maximum.

Note:

You are allowed to break the items.

Example:

If 'N = 4' and 'W = 10'. The weights and values of items are weights = [6, 1, 5, 3] and values = [3, 6, 1, 4]. 
Then the best way to fill the knapsack is to choose items with weight 6, 1 and  3. The total value of knapsack = 3 + 6 + 4 = 13.00