anupamkumar

// Searching for Patterns | Set 1 (Naive Pattern Searching)

// Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[])
 // that prints all occurrences of pat[] in txt[]. You may assume that n > m.

// Examples:
// 1) Input:

//   txt[] =  "THIS IS A TEST TEXT"

anupamkumar

// Longest Common Extension / LCE | Set 1 (Introduction and Naive Method)

// The Longest Common Extension (LCE) problem considers a string s and computes, for each pair (L , R), the longest sub string 
// of s that starts at both L and R. In LCE, in each of the query we have to answer the length of the longest common prefix 
// starting at indexes L and R.


// example
// String : “abbababba”

anupamkumar

// Calculate sum of all numbers present in a string

// Given a string containing alphanumeric characters, calculate sum of all numbers present in the string.

// Examples:

// Input:  1abc23
// Output: 24

anupamkumar

// Find longest palindrome formed by removing or shuffling chars from string

// Given a string, find the longest palindrome that can be constructed by removing or shuffling characters from the string. 
// Return only one palindrome if there are multiple palindrome strings of longest length.

// Examples:

// Input:  abc
// Output: a OR b OR c

anupamkumar

// Find k’th character of decrypted string

// Given an encoded string where repetitions of substrings are represented as substring followed by count of substrings. For example, if encrypted string is “ab2cd2″ and k=4 , so output will be ‘b’ because decrypted string is “ababcdcd” and 4th character is ‘b’.

// Note: Frequency of encrypted substring can be of more than one digit. For example, in “ab12c3″, ab is repeated 12 times. No leading 0 is present in frequency of substring.

// Examples:

// Input: "a2b2c3", k = 5

anupamkumar

// Check if string follows order of characters defined by a pattern or not | Set 2

// Given an input string and a pattern, check if characters in the input string follows the same order as determined by characters present in the pattern.
 // Assume there won’t be any duplicate characters in the pattern.

// Another solution to the same problem is posted here.

// Examples:

anupamkumar

// Maximize value of (arr[i] – i) – (arr[j] – j) in an array

// Given an array, arr[] find the maximum value of (arr[i] – i) – (arr[j] – j) where i is not equal to j. 
// Where i and j vary from 0 to n-1 and n is size of input array arr[].

// Examples:

// Input : arr[] = {9, 15, 4, 12, 13}
// Output : 12

anupamkumar

// Maximize number of 0s by flipping a subarray

// Given a binary array, find the maximum number zeros in an array with one flip of a subarray allowed. 
// A flip operation switches all 0s to 1s and 1s to 0s.

// Examples:

// Input :  arr[] = {0, 1, 0, 0, 1, 1, 0}
// Output : 6

anupamkumar

def numOfWaysToTgt(target,allowedUnits)
	scores = Array.new(target+1,0)
	scores[0] = 1
	allowedUnits.each do |allowedScore|
		(allowedScore..target).each do |k|
			scores[k] += scores[k-allowedScore]
		end	
	end
	puts "#{target} can be reached in #{scores[target]} ways"
end

anupamkumar

import sys

def minCost(cost,N):
	best_way_to_reach = [0]*N
	for k in range(1,N):
		minimum_cost_to_get_from_0_to_k = sys.maxint
		for i in range(k,0,-1):
			if(minimum_cost_to_get_from_0_to_k > best_way_to_reach[k-i]+cost[k-i][k]):
				minimum_cost_to_get_from_0_to_k = best_way_to_reach[k-i]+cost[k-i][k]
			best_way_to_reach[k] = min(minimum_cost_to_get_from_0_to_k,cost[0][k])