Matrix Exponentiation algorithm

Related studies: Here Problem Link Problem description: The laboratory of Microbiology department has been attacked by several robbers recently. They robbed and stole many valuable samples of viruses, bacteria, microorganisms. While being in hurry, they broke a tube. The tube contained sample of one of the most dangerous germs called Dangerm. The tube contained exactly

Count of n digit numbers whose sum of digits equals to given sum [ Amazon ]

Problem: Given two integers ‘n’ and ‘sum’, find count of all n digit numbers with sum of digits as ‘sum’. Leading 0’s are not counted as digits. Print your output % 10^9+7.


Word Break [ IBM – Google ]

Problem: Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details. Consider the following dictionary { i, like, sam, sung, samsung, mobile, ice,cream, icecream, man, go, mango} Input:  ilike Output: Yes The string can be

Edit Distance of Two Given String [ Amazon ]

Problem:Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1′ into ‘str2′. a.Insert b.Remove c.Replace All of the above operations are of cost=1.Both the strings are of lowercase. Hint: Use DP to solve the problem. This problema also can be solved using

Find K-Palindrome of a string [ Amazon]

Problem:A string is k pallindrome if it can be transformed into a palindrome on removing at most k characters from it. Link