SDE - 1

You are given a string “str”. Find the maximum number of non-empty substrings of “str” such that no two substrings overlap with each other and each substring that you select containing a letter ‘t’ must contain all the occurrences of ‘t’ in that substring.

A string ‘a’ is a substring of a string ‘b’ if ‘a’ can be obtained from ‘b’ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Note:

If there are multiple solutions of a string, return the string with minimum total length.

For Example :

Let str = abaccce

Now In this example, we can make a maximum of three substrings i.e. {‘b’, ‘ccc’, ‘e’}.

Note:

There can be one more solution with maximum substrings equal to three i.e. {‘aba’, ‘ccc’, ‘e’} but we have to select the substrings with minimum total length. So the final answer is  {‘b’, ‘ccc’, ‘e’}.

You are given an integer ‘N’. You need to find an array of size 2*N that satisfies the following two conditions.

1. All numbers from 1 to N should appear exactly twice in the array.

2. The distance between the second occurrence and the first occurrence of any number should exactly be equal to the value of that number.

The distance between two numbers at indices ‘i’ and ‘j’ is defined as (j-i-1) where i < j.

If no such array exists, then you should return an empty array.

For example :

For N = 3 one valid array is [3,1,2,1,3,2].

You are given a two-dimensional grid having 'N' rows and 'M' columns, consisting of upper case characters. You are also given a word 'WORD'. You have to find the number of occurrences of that word in the grid.

Starting from a given cell, a word can be formed by moving in all eight directions: horizontally left, horizontally right, vertically up, vertically down, and four diagonal directions.

Example :

There are three occurrences of the word 'NINJA' in the following grid:

Note :

1) Given word will not be a single character.

2) If occurrences of the given word start from two different cells, then these two occurrences are considered to be different.

Consider the word 'XYX' to be searched in the string 'AXYXB'. Here, we find an occurrence of 'XYX' at index 2 going in the right direction, and another occurrence at index 4 going in the left direction.

Although these two words correspond to the same word, they will be considered as different occurrences.

Design a flight booking system (low level + High level)