SDE - Intern

You have been given an N*M matrix filled with integer numbers, find the maximum sum that can be obtained from a path starting from any cell in the first row to any cell in the last row.

From a cell in a row, you can move to another cell directly below that row, or diagonally below left or right. So from a particular cell (row, col), we can move in three directions i.e.

Down: (row+1,col)
Down left diagonal: (row+1,col-1)
Down right diagonal: (row+1, col+1)

You are given D dice, each having F faces numbered 1 to F, both inclusive. The task is to find the possible number of ways to roll the dice together such that the sum of face-up numbers equal the given target S.

Note :

As the answer can be large, return your answer modulo 10^9  + 7.

Follow Up :

Can you solve this using not more than O(S) extra space?

You are given a string 'S', check if there exists any permutation of the given string that is a palindrome.

Note :

1. A palindrome is a word or phrase that reads the same from forward and backward e.g. “aba”, it reads the same from forward and backward.
2. A permutation is a rearrangement of letters.
3. The palindrome does not need to be limited to just dictionary words.

Example :

Given string S : aab
The output should be "True" as "aba" (permutation of string S) is a palindrome. 

You have been given two Strings “STR1” and “STR2” of characters. Your task is to find the length of the longest common subsequence.

A String ‘a’ is a subsequence of a String ‘b’ if ‘a’ can be obtained from ‘b’ by deletion of several (possibly, zero or all) characters. A common subsequence of two Strings is a subsequence that is common to both Strings.