SDE - 1

Divyansh is in Dhanbad and wants to travel to different places. He can take one, two or three steps at max while travelling. He knows the distance and wants to find the number of ways to reach his destination. He is weak at calculations and wants your help in this. Given the distance from Dhanbad to his destination, count the total number of ways to cover the distance with 1, 2 and 3 steps.

You have been given a MATRIX of non-negative integers of size N x M where 'N' and 'M' denote the number of rows and columns, respectively.

Your task is to find the length of the longest increasing path when you can move to either four directions: left, right, up or down from each cell. Moving diagonally or outside the boundary is not allowed.

Note: A sequence of integers is said to form an increasing path in the matrix if the integers when traversed along the allowed directions can be arranged in strictly increasing order. The length of an increasing path is the number of integers in that path.

For example :

3 2 2
5 6 6
9 5 11 

In the given matrix, 3 →  5 →  6 and 3 →  5 →  9 form increasing paths of length 3 each.

You are given a list of “N” strings A. Your task is to check whether you can form a given target string using a combination of one or more strings of A.

Note :

You can use any string of A multiple times.

Examples :

A =[“coding”, ”ninjas”, “is”, “awesome”]  target = “codingninjas”
Ans = true as we use “coding” and “ninjas” to form “codingninjas”

You are given an array ‘Arr’ consisting of ‘N’ distinct integers and a positive integer ‘K’. Find out Kth smallest and Kth largest element of the array. It is guaranteed that K is not greater than the size of the array.

Example:

Let ‘N’ = 4,  ‘Arr’ be [1, 2, 5, 4] and ‘K’ = 3.  
then the elements of this array in ascending order is [1, 2, 4, 5].  Clearly, the 3rd smallest and largest element of this array is 4 and 2 respectively.

You are given an array 'arr' of length 'n', consisting of integers.

A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning and 0 or more integers from the end of an array.

Find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.

The sum of an empty subarray is 0.

Example :

Input: 'arr' = [1, 2, 7, -4, 3, 2, -10, 9, 1]

Output: 11

Explanation: The subarray yielding the maximum sum is [1, 2, 7, -4, 3, 2].

Write a SQL query to output all records , names starting with a.

You are given a string ‘S’. Your task is to find the number of subsequences in string ‘S’ which are in the form of “a^p + b^q + c^r”, i.e., it consists of ‘p’ “a” characters, followed by ‘q’ “b” characters, and ‘r’ “c” characters, where ‘p’, ‘q’, and ‘r’ are greater than equal to 1. As the result can be large, return that number modulo 10^9 + 7.

Note :

1. A string ‘A’ is a subsequence of a string ‘B’ if ‘A’ can be obtained from ‘B’ by deleting several (possibly, zero or all) characters. 
2. Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different.

Example :

Let the string be: ababc
The subsequence which can be of form “a^p * b^q * c^r” are: “abc” (p = 1, q = 1, r = 1), “abbc” (p = 1, q = 2, r = 1), “aabc” (p = 2, q = 1, r = 1)
So the count is 5 (“abc” can occur thrice).